Một liên hiệp nghiên cứu vừa xây dựng một hệ cơ sở dữ liệu mới cho trung tâm dữ liệu của họ. Hệ thống gồm một máy tính chủ và \(N\) máy tính worker, được đánh số từ \(0\) đến \(N-1\). Mỗi worker lưu đúng một bit thông tin — có vẻ khá lãng phí, nhưng đây là dữ liệu rất quan trọng!

Máy chủ hỗ trợ lệnh TEST_STORE <bits> như sau: máy chủ đọc chuỗi <bits> gồm đúng \(N\) bit, gửi bit thứ \(i\) cho worker thứ \(i\) lưu trữ, rồi đọc các bit từ các worker và trả chúng về cho người dùng theo đúng thứ tự ban đầu.

Trong điều kiện bình thường, TEST_STORE phải trả lại chính chuỗi đã nhận. Tuy nhiên, đúng \(B\) worker đang bị hỏng. Các worker hỏng vẫn lưu được bit được gửi tới, nhưng không trả về bit nào khi máy chủ đọc dữ liệu. Vì thế, TEST_STORE chỉ trả về \(N-B\) bit của các worker không hỏng, theo thứ tự ID tăng dần.

Ví dụ, giả sử \(N=5\) và các worker \(0\) và \(3\) bị hỏng, tức \(B=2\). Khi đó:

• TEST_STORE 01101 trả về 111;
• TEST_STORE 00110 trả về 010;
• TEST_STORE 01010 trả về 100;
• TEST_STORE 11010 cũng trả về 100.

Vì lý do bảo mật, cơ sở dữ liệu được giấu trong một hầm dưới núi nên mỗi lần gọi TEST_STORE mất rất nhiều thời gian. Hãy xác định chính xác tất cả worker bị hỏng bằng không quá \(F\) lần gọi.

Dữ liệu vào

Đây là bài tương tác. Chương trình nhận dữ liệu từ bộ chấm theo giao thức bên dưới.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\), là số bộ test. Sau đó xử lý lần lượt \(T\) bộ test.

Ở đầu mỗi bộ test, chương trình đọc một dòng chứa ba số nguyên \(N\), \(B\) và \(F\): số worker, số worker hỏng và số truy vấn tối đa được phép gửi.

Dữ liệu ra

Chương trình gửi các truy vấn và đáp án tới bộ chấm theo giao thức tương tác bên dưới. Sau mỗi dòng xuất, phải flush bộ đệm chuẩn đầu ra.

Giao thức tương tác

Trong mỗi bộ test, chương trình được gửi tối đa \(F\) dòng truy vấn. Mỗi dòng phải là một chuỗi gồm đúng \(N\) ký tự, mỗi ký tự là 0 hoặc 1. Chuỗi này chính là đối số <bits> của một lệnh TEST_STORE.

Sau mỗi truy vấn hợp lệ, bộ chấm trả về một chuỗi dài đúng \(N-B\), gồm các bit do các worker không hỏng trả về theo thứ tự ID tăng dần. Nếu chương trình gửi quá \(F\) truy vấn, bộ chấm trả về một dòng chỉ chứa -1, chấm dứt toàn bộ giao tiếp và chờ chương trình thoát.

Khi đã xác định được các worker hỏng, chương trình kết thúc bộ test bằng cách in \(B\) số nguyên cách nhau bởi dấu cách: ID của các worker hỏng theo thứ tự tăng dần. Dòng đáp án này không được tính là một trong \(F\) truy vấn.

Nếu \(B\) số được in không đúng chính xác tập ID của các worker hỏng, bài làm nhận Wrong Answer; bộ chấm gửi -1 rồi không giao tiếp thêm. Nếu đáp án đúng, bộ chấm gửi 1, sau đó gửi dòng mở đầu bộ test kế tiếp, hoặc kết thúc nếu không còn bộ test.

Ngay khi đọc được -1, chương trình phải thoát; nếu tiếp tục chờ dữ liệu, chương trình có thể bị báo Time Limit Exceeded thay vì lỗi giao thức thực sự.

Ràng buộc

• \(1\le T\le100\).
• \(2\le N\le1024\).
• \(1\le B\le\min(15,N-1)\).

Phân nhóm

• Test Set 1: \(F=10\).
• Test Set 2: \(F=5\).

Ví dụ

  t = readline_int()             // đọc 2 vào t
  n, b, f = readline_int_list()  // đọc 5, 2, 10 vào n, b, f
  printline 01101 to stdout      // bốn truy vấn tiếp theo khớp ví dụ trong đề
  flush stdout
  response = readline_str()      // đọc 111; lúc này đã có thể suy ra đáp án
  printline 00110 to stdout      // các truy vấn còn lại chỉ để minh họa
  flush stdout
  response = readline_str()      // đọc 010
  printline 01010 to stdout
  flush stdout
  response = readline_str()      // đọc 100
  printline 11010 to stdout
  flush stdout
  response = readline_str()      // đọc 100
  printline 0 3 to stdout        // đoán đáp án mà không cần dùng đủ 10 truy vấn
  flush stdout
  verdict = readline_int()       // đọc 1: test này đúng
  n, b, f = readline_int_list()  // đọc 2, 1, 10 vào n, b, f
  printline 01 to stdout         // đây là truy vấn, không phải đáp án cuối
  flush stdout
  response = readline_str()      // đọc 1
  printline 1 to stdout          // đưa ra một dự đoán sai
  verdict = readline_str()       // đọc -1
  exit                           // thoát để tránh kết quả TLE khó hiểu

Nguồn

Google Code Jam 2019, Vòng loại, bài Dat Bae.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.