Kiểm định máy kiểm định
Đề bài
Mô tả
Đây là bài toán tương tác.
Công ty Kiểm định Chất lượng Tính toán Sáng tạo (ICQC) vừa chế tạo một cỗ máy đột phá dùng để kiểm định chất lượng. Nhờ công nghệ Trí tuệ Sâu mới lạ, một máy kiểm định (máy QC) của ICQC có thể tự động phát hiện, với độ chính xác , lỗi sản xuất của bất kỳ cỗ máy nào đang tồn tại, dù đó là máy pha cà phê, tàu vũ trụ liên thiên hà hay máy tính lượng tử.
ICQC đang xây dựng nhà máy để sản xuất các máy QC này. Như mọi quy trình sản xuất khác, một phần số máy làm ra sẽ bị hỏng, và cần tìm ra để loại bỏ chúng. May thay, ICQC có đúng sản phẩm để phát hiện máy hỏng! Hiển nhiên ICQC không thể dùng một máy QC để tự kiểm định chính nó, vì một máy hỏng có thể tự nhận là mình hoạt động tốt. Thay vào đó, mỗi lô máy sản xuất trong một ngày sẽ được cho kiểm định lẫn nhau suốt đêm. Cụ thể, trong mỗi giờ của đêm, mỗi máy trong máy QC có thể chạy kiểm định một máy QC khác, đồng thời được một máy QC khác kiểm định.
Nếu máy chạy kiểm định là máy tốt, nó sẽ báo đúng máy được kiểm định là tốt hay hỏng; còn nếu máy chạy kiểm định bị hỏng, nó có thể báo kết quả bất kỳ. Nếu máy được dùng để kiểm định máy nhiều lần thì lần nào nó cũng trả về cùng một kết quả, kể cả khi bị hỏng. Lịch kiểm định không cần cố định từ trước: việc chọn máy nào kiểm định máy nào trong giờ thứ hai có thể dựa vào kết quả của giờ thứ nhất, và cứ thế.
ICQC chắc chắn rằng trong mỗi lô có nhiều hơn một nửa trong máy QC hoạt động tốt, nhưng đêm chỉ dài giờ, nên chỉ đủ thời gian cho một số ít lượt kiểm định. Bạn hãy giúp ICQC xác định những máy QC nào bị hỏng.
Ví dụ, xét bản ghi tương tác ví dụ 1 của đề gốc (xem cột Giải thích bên dưới): sau giờ thứ tư, mọi máy đã kiểm định mọi máy khác. Với máy , chỉ có một máy khác báo nó hỏng, trong khi nếu nó hỏng thật thì ít nhất máy khác sẽ báo như vậy. Với máy , chỉ có một máy khác báo nó tốt, suy ra máy phải hỏng vì số máy tốt nhiều hơn một nửa. Lưu ý rằng dù máy bị hỏng, nó vẫn tình cờ đưa ra các kết quả đúng trong những lượt kiểm định cụ thể này.
Tương tác
Dòng đầu tiên của dữ liệu vào chứa một số nguyên (), số lô. Các lô độc lập với nhau. Bạn phải xử lý từng lô theo kiểu tương tác, nghĩa là dữ liệu bạn nhận được phụ thuộc vào những gì chương trình của bạn đã in ra trước đó.
Dòng đầu tiên của mỗi lô chứa một số nguyên (), số máy QC trong lô.
Sau đó tương tác diễn ra theo các lượt. Trong mỗi lượt, chương trình có thể xếp lịch kiểm định cho giờ tiếp theo bằng cách in một dòng dạng test x1 x2 ... xn, nghĩa là máy chạy kiểm định máy . Nếu thì máy nghỉ trong lượt đó và không kiểm định máy nào. Mọi số dương trong dãy phải đôi một khác nhau.
Sau khi in dòng này, bạn đọc kết quả là một dòng gồm một xâu độ dài : ký tự thứ là 1 nếu máy báo máy hoạt động tốt, 0 nếu máy báo máy bị hỏng, và - (dấu gạch ngang) nếu máy nghỉ trong lượt đó.
Khi đã xác định được những máy nào bị hỏng, nhưng không muộn hơn sau lượt kiểm định, chương trình phải in một dòng dạng answer S, trong đó là xâu nhị phân độ dài , ký tự thứ là 1 nếu máy hoạt động tốt và 0 nếu máy bị hỏng.
Sau khi in dòng trả lời, chương trình bắt đầu xử lý lô tiếp theo bằng cách đọc số của lô đó. Khi đã xử lý xong cả lô, tương tác kết thúc và chương trình phải dừng.
Trình chấm không đối kháng: kết quả mỗi lần một máy kiểm định một máy khác đã được chọn từ trước, không phụ thuộc vào các truy vấn của bạn.
Nhớ flush bộ đệm đầu ra sau mỗi dòng in ra (ví dụ cout << endl trong C++, sys.stdout.flush() trong Python).
Ràng buộc
- , .
- Trong mỗi lô, số máy tốt lớn hơn .
- Mỗi lô được dùng tối đa lượt
test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 5 0001- --1-0 |
test 2 1 4 3 0 test 0 0 1 0 2 answer 10101 |
Cột Input là những gì chương trình đọc được, cột Output là những gì chương trình in ra. Máy và bị hỏng. Lượt : máy báo máy hỏng, máy báo máy tốt, nên máy chắc chắn hỏng (nếu máy tốt thì máy tốt và lời báo của máy phải đúng). Máy và báo nhau hỏng nên ít nhất một trong hai máy hỏng; vì phải có ít nhất máy tốt, máy và đều tốt. Lượt hai máy tốt này kiểm định máy và . Bản ghi tương tác của đề gốc dùng lượt: đọc 11011, 00110, 01011, 10100 sau các lệnh test 5 4 2 1 3, test 4 5 1 3 2, test 2 3 4 5 1, test 3 1 5 2 4, rồi answer 10101. |
| 2 4 1111 1-1- 7 000011- ----00- ----11- -0----- |
test 2 1 4 3 test 3 0 1 0 answer 1111 test 2 1 4 3 6 5 0 test 0 0 0 0 1 3 0 test 0 0 0 0 2 4 0 test 0 7 0 0 0 0 0 answer 0101110 |
Hai lô. Lô thứ nhất có máy đều tốt. Lô thứ hai có máy, máy , , , tốt. Bản ghi tương tác của đề gốc: lô in test 2 3 4 1, đọc 1111, rồi answer 1111; lô in test 2 3 4 5 6 7 1, đọc 0001100, in test 0 0 0 0 2 4 0, đọc ----11-, rồi answer 0101110. |
Bình luận