SQRT Contest #04 - Tìm hai số
Xem dạng PDFĐây là bài toán tương tác với máy chấm
Bạn cần tìm hai số nguyên dương ~u, v~ ~(1 \le u \le v \le n)~. Bạn được phép hỏi máy chấm một số câu hỏi. Với mỗi câu hỏi, bạn được đưa ra một tập ~S~ gồm một số (~k~) tập hợp ~S_1, S_2, ..., S_k~, mỗi tập hợp ~S_i~ gồm một số (~x~) vị trí ~a_{i_1}, a_{i_2}, ..., a_{i_x}~. Máy chấm sẽ trả lời bạn bằng một chuỗi nhị phân cho biết trong tập ~S_i~ có ít nhất một trong hai số ~u~ hoặc ~v~ hay không.
Bạn cần giải quyết bài toán với càng ít lần hỏi và tổng ~k~ trong các lần hỏi càng nhỏ càng tốt. Tổng ~k~ tối đa không được phép vượt quá ~180~. Tuy nhiên, để đạt điểm tối đa, tổng ~k~ trong các lần hỏi của bạn không được phép vượt quá ~20~.
Tương tác
- Đầu tiên, chương trình của bạn cần nhập vào hai số nguyên dương ~n~ và ~\theta~, với ~\theta~ là thứ tự subtask của test hiện tại ~(2 \le n \le 1000, 1 \le \theta \le 4)~.
- Tiếp theo, quy trình hỏi đáp bắt đầu. Chương trình của bạn cần hỏi trước.
- Với truy vấn hỏi, chương trình của bạn cần in ra output có dạng như sau:
- Dòng đầu tiên có dạng ~?\ k~.
- ~k~ dòng tiếp theo, mỗi dòng gồm một xâu nhị phân có độ dài ~n~. Ký tự thứ ~i~ trong dòng thứ ~j~ là
1khi và chỉ khi trong tập ~S_i~ có chứa số ~j~.
- Sau mỗi truy vấn hỏi, chương trình của bạn cần nhập vào một xâu nhị phân độ dài ~k~ là câu trả lời của máy chấm. Ký tự thứ ~i~ trong xâu là
1khi và chỉ khi trong tập ~S_i~ có chứa ~u~ hoặc ~v~ (hoặc cả hai). - Với truy vấn trả lời, chương trình của bạn cần in ra output có dạng như sau:
- Một dòng duy nhất có dạng ~!\ u\ v~ ~(1 \le u \le v \le n)~.
- Chương trình của bạn cần ngắt ngay khi tổng các giá trị ~k~ trong các truy vấn hỏi vượt quá ~180~.
- Với truy vấn hỏi, chương trình của bạn cần in ra output có dạng như sau:
Lưu ý rằng máy chấm có thể thích nghi theo câu hỏi của bạn, nghĩa là cặp số ~u, v~ bạn cần tìm có thể sẽ không được cố định từ trước.
Chấm điểm
Giả sử điểm tối đa của mỗi test là ~100~. Chương trình của bạn sẽ được ~0~ điểm nếu đoán sai một trong hai số. Gọi ~A~ là số lần bạn thực hiện truy vấn hỏi, ~B~ là tổng ~k~ trong tất cả các truy vấn hỏi. Điểm của bạn sẽ được tính theo công thức:
$$S = \frac{1}{log_2(A + 1)} \times C$$
với công thức tính ~C~ được cho trong bảng sau:
| ~B~ | ~C~ |
|---|---|
| ~B \le 20~ | ~C = 100~ |
| ~20 < B \le 30~ | ~C = 90 + (30 - B)~ |
| ~30 < B \le 55~ | ~C = 70 + \frac{4}{5} \times (55 - B)~ |
| ~55 < B \le 155~ | ~C = 10 + \frac{3}{5} \times (155 - B)~ |
| ~155 < B \le 180~ | ~C = \frac{2}{5} \times (180 - B)~ |
| ~B > 180~ | ~0~ |
Subtask
| Tỉ lệ điểm | Ràng buộc bổ sung |
|---|---|
| ~10\%~ | ~n \le 20~ |
| ~20\%~ | ~u = v~ |
| ~30\%~ | ~v \oplus u = 2^k~, với ~\oplus~ là phép toán XOR |
| ~40\%~ | Không có giới hạn gì thêm |
Ví dụ
| Chương trình | Máy chấm | Giải thích |
|---|---|---|
4 1 |
Bạn cần tìm ra hai trong ~4~ số. Trong test này, hai số cần tìm là ~u = 1, v = 3~. Test này thuộc subtask 1. | |
? 1 |
Chương trình của bạn đặt câu hỏi với ~1~ tập hợp ~(k = 1)~. | |
1000 |
Tập hợp ~S_1 = \{1\}~. | |
1 |
Máy chấm cho biết có ít nhất một trong hai số ~u~ hoặc ~v~ thuộc tập hợp đã cho. | |
? 2 |
Chương trình của bạn đặt câu hỏi với ~2~ tập hợp ~(k = 2)~. | |
0101 |
Tập hợp ~S_1 = \{2; 4\}~. | |
0010 |
Tập hợp ~S_2 = \{3\}~. | |
01 |
Máy chấm cho biết không có số nào trong tập ~S_1~ và có it nhất một số trong tập ~S_2~. | |
! 1 3 |
Chương trình của bạn đưa ra câu trả lời chính xác. |
Với quy trình tương tác trên, ta có số lần hỏi là ~A = 2~, tổng các giá trị ~k~ là ~B = 1 + 2 = 3~. Theo bảng trên tính được ~C = 100~. Do đó điểm chương trình nhận được là: $$\frac{1}{log_2(A + 1)} \times C = \frac{1}{log_2(3)} \times 100 \approx 63.09$$
Bình luận