Amina có sáu đồng xu, đánh số từ \(1\) đến \(6\). Cô biết trọng lượng của chúng đôi một khác nhau và muốn sắp xếp chúng theo trọng lượng. Để làm việc này, cô đã thiết kế một loại cân mới.

Cân truyền thống có hai đĩa: đặt một đồng xu lên mỗi đĩa, cân sẽ cho biết đồng nào nặng hơn. Cân của Amina phức tạp hơn, có bốn đĩa mang nhãn \(A\), \(B\), \(C\), \(D\) và bốn chế độ hoạt động, mỗi chế độ trả lời một câu hỏi khác nhau. Khi sử dụng cân, phải đặt đúng một đồng xu lên từng đĩa \(A\), \(B\), \(C\). Riêng chế độ thứ tư còn phải đặt đúng một đồng xu lên đĩa \(D\).

Bốn chế độ trả lời các câu hỏi sau:

1. Trong các đồng xu trên \(A\), \(B\), \(C\), đồng nào nặng nhất?
2. Trong các đồng xu trên \(A\), \(B\), \(C\), đồng nào nhẹ nhất?
3. Trong các đồng xu trên \(A\), \(B\), \(C\), đồng nào có trọng lượng ở giữa, tức không nặng nhất cũng không nhẹ nhất?
4. Trong các đồng xu trên \(A\), \(B\), \(C\), chỉ xét những đồng nặng hơn đồng trên \(D\). Nếu có, trả về đồng nhẹ nhất trong số đó. Nếu không có, trả về đồng nhẹ nhất trong cả ba đồng trên \(A\), \(B\), \(C\).

Hãy viết chương trình sắp xếp sáu đồng xu của Amina theo trọng lượng bằng cách gọi các phép cân. Chương trình phải giải nhiều test; mỗi test ứng với một bộ sáu đồng xu mới.

Chi tiết cài đặt

Trong C hoặc C++, cài đặt hai hàm sau trong header dùng chung scales.h:

void init(int T);
void orderCoins();

Chương trình chấm cung cấp các hàm:

void answer(int W[]);
int getMedian(int A, int B, int C);
int getHeaviest(int A, int B, int C);
int getLightest(int A, int B, int C);
int getNextLightest(int A, int B, int C, int D);

Trong Java, cài đặt các phương thức sau trong lớp scales:

public void init(int T)
public void orderCoins()

Các phương thức do chương trình chấm Java cung cấp được gọi qua grader.lib:

public static void answer(int[] W)
public static int getMedian(int A, int B, int C)
public static int getHeaviest(int A, int B, int C)
public static int getLightest(int A, int B, int C)
public static int getNextLightest(int A, int B, int C, int D)

Trong mỗi lần chạy, chương trình chấm gọi init(T) trước tiên và đúng một lần. T là số test của lần chạy, \(1 \le T \le 18\). Bạn có thể khởi tạo các biến tại đây; hàm không trả về giá trị.

Sau đó, orderCoins() được gọi đúng một lần cho mỗi test. Hàm phải tìm thứ tự đúng bằng cách gọi getHeaviest, getLightest, getMedian và/hoặc getNextLightest. Khi biết thứ tự, gọi answer(W) để báo kết quả, rồi kết thúc orderCoins. Hàm không trả về giá trị.

• answer(W): W là mảng dài \(6\). Các phần tử W[0] đến W[5] phải là các số hiệu đồng xu từ \(1\) đến \(6\), theo thứ tự từ nhẹ nhất đến nặng nhất. Chỉ được gọi hàm này từ orderCoins, đúng một lần trong mỗi test. Hàm không trả về giá trị.
• getHeaviest(A, B, C), getLightest(A, B, C), getMedian(A, B, C) tương ứng với các chế độ \(1\), \(2\), \(3\). Các đối số là số hiệu đồng xu đặt trên các đĩa tương ứng, phải là ba số nguyên phân biệt trong đoạn \([1,6]\). Mỗi hàm trả về một trong A, B, C, là số hiệu đồng xu được chọn. Chẳng hạn, getHeaviest trả về số hiệu đồng nặng nhất trong ba đồng.
• getNextLightest(A, B, C, D) tương ứng với chế độ \(4\). Bốn đối số phải là các số nguyên đôi một khác nhau trong đoạn \([1,6]\). Hàm trả về một trong A, B, C: đồng nhẹ nhất trong số những đồng nặng hơn đồng D; nếu không đồng nào nặng hơn D, trả về đồng nhẹ nhất trong cả ba.

Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "scales.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp scales, không viết phương thức main. Không đọc trực tiếp dữ liệu bí mật; chỉ lấy thông tin qua các hàm cân được cung cấp.

Cách tính điểm chính thức

Bài này không chia subtask. Điểm phụ thuộc vào số lần cân, tức tổng số lần gọi getLightest, getHeaviest, getMedian và getNextLightest.

Chương trình được chạy nhiều lần, mỗi lần có nhiều test. Gọi \(r\) là số lần chạy; \(r\) cố định bởi bộ dữ liệu. Nếu chương trình sắp xếp sai các đồng xu trong bất kỳ test nào của bất kỳ lần chạy nào thì được \(0\) điểm toàn bài. Nếu mọi kết quả đều đúng, mỗi lần chạy được tính điểm riêng như sau.

Gọi \(Q\) là số nhỏ nhất sao cho có thể sắp xếp mọi bộ sáu đồng xu bằng \(Q\) lần cân trên cân của Amina. Đề thi chính thức không công bố giá trị \(Q\) để tăng tính thử thách.

Giả sử số lần cân lớn nhất trong tất cả các test của tất cả các lần chạy là \(Q+y\), với \(y\) nguyên. Xét một lần chạy cụ thể: số lần cân lớn nhất trong các test của lần chạy này là \(Q+x\), với \(x\) nguyên không âm. Nếu mọi test trong lần chạy đều dùng ít hơn \(Q\) lần cân thì đặt \(x=0\). Điểm của lần chạy là

làm tròn xuống đến hai chữ số sau dấu thập phân. Điểm toàn bài là tổng điểm các lần chạy. Đặc biệt, nếu chương trình dùng không quá \(Q\) lần cân cho mỗi test của mọi lần chạy, bạn được \(100\) điểm.

Cách tính điểm trên LQDOJ

LQDOJ chấm từng tệp độc lập và lấy điểm nhỏ nhất trong batch; checker của một tệp không biết số lần cân ở các tệp khác. Vì thế không thể tái hiện đúng phần thưởng theo từng lần chạy của công thức chính thức ở trên.

Bộ dữ liệu chính thức có \(r=40\) lần chạy tính điểm; giá trị tối ưu là \(Q=6\). Với một tệp có số lần cân lớn nhất là \(q\), đặt \(x=\max(0,q-6)\). Checker cho tệp đó hệ số

Điểm LQDOJ là \(100\) nhân hệ số nhỏ nhất trong \(40\) tệp. Nếu có bất kỳ thứ tự sai, lời gọi không hợp lệ, thiếu hoặc thừa lần gọi answer, thì toàn bài được \(0\) điểm. Các mẫu là pretest \(0\) điểm, không tham gia batch tính điểm.

Nếu mọi kết quả đúng và \(y=\max x\) trên tất cả các tệp, điểm LQDOJ bằng \(100f(y)\). Đây là cận dưới của điểm chính thức: công thức chính thức còn thưởng những lần chạy có \(x<y\), trong khi bản này dùng trường hợp xấu nhất cho tất cả các lần chạy. Hai cách cho cùng điểm khi mọi lần chạy có cùng \(x\); đặc biệt, hành vi đạt trọn \(100\) điểm là chính xác: mọi test phải đúng và dùng không quá \(6\) lần cân. Khi thực hiện lần cân thứ \(629\) trong một test, điểm theo bản điều chỉnh đã bằng \(0\), nên grader dừng ngay. Các giới hạn thời gian và bộ nhớ vẫn áp dụng.

Ví dụ

Giả sử thứ tự từ nhẹ nhất đến nặng nhất là \(3,4,6,2,1,5\).

Chương trình chấm mẫu

• Dòng \(1\): số test T.
• Mỗi dòng từ \(2\) đến \(T+1\): sáu số phân biệt từ \(1\) đến \(6\), là thứ tự các đồng xu từ nhẹ nhất đến nặng nhất.

Ví dụ với hai test có thứ tự \(1,2,3,4,5,6\) và \(3,4,6,2,1,5\):

2
1 2 3 4 5 6
3 4 6 2 1 5

Đề chính thức mô tả chương trình chấm mẫu in mảng được truyền cho answer. Mã grader trong gói chính thức còn in số lần cân sau mỗi mảng. Grader trên LQDOJ giữ định dạng gồm sáu số hiệu đồng xu, rồi số lần cân, và dùng đầu vào/đầu ra chuẩn thay cho các tệp scales.in, scales.out.