trang chủ / đề bài / icpcwf20_h

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 100%, 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ô n 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 n 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 A được dùng để kiểm định máy B nhiều lần thì lần nào nó cũng trả về cùng một kết quả, kể cả khi A 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 100% rằng trong mỗi lô có nhiều hơn một nửa trong n máy QC hoạt động tốt, nhưng đêm chỉ dài 12 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 1, 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 3 máy khác sẽ báo như vậy. Với máy 4, chỉ có một máy khác báo nó tốt, suy ra máy 2 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 4 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 b (1≤b≤500), 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 n (1≤n≤100), 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 i chạy kiểm định máy xi. Nếu xi=0 thì máy i 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 n: ký tự thứ i là 1 nếu máy i báo máy xi hoạt động tốt, 0 nếu máy i báo máy xi bị hỏng, và - (dấu gạch ngang) nếu máy i 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 12 lượt kiểm định, chương trình phải in một dòng dạng answer S, trong đó S là xâu nhị phân độ dài n, ký tự thứ i là 1 nếu máy i hoạt động tốt và 0 nếu máy i 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ố n của lô đó. Khi đã xử lý xong cả b 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

  • 1≤b≤500, 1≤n≤100.
  • Trong mỗi lô, số máy tốt lớn hơn n/2.
  • Mỗi lô được dùng tối đa 12 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 2 và 4 bị hỏng. Lượt 1: máy 3 báo máy 4 hỏng, máy 4 báo máy 3 tốt, nên máy 4 chắc chắn hỏng (nếu máy 4 tốt thì máy 3 tốt và lời báo của máy 3 phải đúng). Máy 1 và 2 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 3 máy tốt, máy 3 và 5 đều tốt. Lượt 2 hai máy tốt này kiểm định máy 1 và 2. Bản ghi tương tác của đề gốc dùng 4 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ó 4 máy đều tốt. Lô thứ hai có 7 máy, máy 2, 4, 5, 6 tốt. Bản ghi tương tác của đề gốc: lô 1 in test 2 3 4 1, đọc 1111, rồi answer 1111; lô 2 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0