Đầu năm nay, đội Code Jam trồng một vườn cây với sự giúp đỡ của một chú chuột túi má cần mẫn. Hẳn nó đã kể cho đồng loại, vì giờ trong vườn có từ \(2\) đến \(25\) chú. Rất khó biết chính xác có bao nhiêu: chúng chỉ chui khỏi hang ngầm để ăn vào ban đêm, còn sau một ngày tỉa cây vất vả chúng tôi quá mệt để thức quan sát. Tuy nhiên, mỗi ngày chúng tôi làm được đúng một “món ăn cho chuột”, để ngoài trời ban đêm rồi sáng hôm sau xem có bị ăn hay không. Chúng tôi nghĩ có thể dùng thông tin này để xác định số chuột.

Đây là những gì đã biết về cách chúng ăn. Ban ngày, \(N\) chú chuột họp hội đồng để quyết định thứ tự xuất hiện trong \(N\) đêm tiếp theo, mỗi đêm một chú. Đêm thứ \(i\), chú thứ \(i\) trong thứ tự chui lên và tìm món ăn. Mỗi chú có một ngưỡng khẩu vị riêng, không bao giờ thay đổi; nó ăn khi và chỉ khi chất lượng món ăn ít nhất bằng ngưỡng của nó. Ban ngày sau khi chú thứ \(N\) xuất hiện, hội đồng chọn thứ tự mới và quá trình tiếp tục. Dù một chú không ăn món nó tìm thấy, nó vẫn không xuất hiện lại cho đến lượt của mình trong thứ tự kế tiếp.

Mỗi ngày phải làm đúng một món mới. Món không bị ăn cũng hỏng và không thể dùng lại đêm sau. Mỗi sáng, bạn biết món của đêm trước có bị lấy hay không.

Hôm nay, bạn biết chúng đang họp để chọn thứ tự kế tiếp, nên tối nay là đầu một thứ tự mới. Bạn sẵn lòng dành rất nhiều thời gian cho cuộc điều tra — tới \(10^5\) đêm. Dùng không quá \(S\) món, hãy xác định số chuột.

Dữ liệu vào

Đây là bài tương tác, nên khái niệm dữ liệu vào và dữ liệu ra khác các bài Code Jam thông thường. Chương trình tương tác với một tiến trình riêng vừa cung cấp thông tin vừa đánh giá phản hồi. Mọi thông tin đi vào chương trình qua đầu vào chuẩn; mọi điều cần truyền cho bộ chấm phải gửi qua đầu ra chuẩn.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\). Ở đầu mỗi bộ test, đọc một dòng chứa số nguyên \(S\), số món tối đa có thể dùng.

Dữ liệu ra

Chương trình gửi từng truy vấn chất lượng món ăn hoặc câu trả lời cuối cùng qua đầu ra chuẩn theo giao thức bên dưới. Nhiều ngôn ngữ mặc định lưu đầu ra trong bộ đệm, nên phải bảo đảm dữ liệu thật sự được gửi — chẳng hạn bằng cách flush — trước khi chặn để chờ phản hồi. FAQ về bài tương tác của Code Jam giải thích chi tiết thao tác flush. Dữ liệu gửi qua lỗi chuẩn bị bỏ qua, nhưng vẫn có thể tiêu thụ bộ nhớ.

Để hỗ trợ gỡ lỗi, cuối đề chính thức có một công cụ kiểm thử cục bộ viết bằng Python. Phần phân tích bài tương tác Number Guessing của Code Jam trước đó cũng cung cấp lời giải mẫu bằng mọi ngôn ngữ được hỗ trợ.

Giao thức tương tác

Với mỗi bộ test, chương trình thực hiện nhiều nhất \(S+1\) lượt trao đổi; lượt cuối bắt buộc là một lần đoán đáp án. Ở lượt thứ \(i\), in một dòng chứa số nguyên \(Q_i\):

• Nếu \(1\le Q_i\le10^6\), bạn để ra một món chất lượng \(Q_i\). Bộ chấm trả một dòng chứa 1 nếu chuột ăn, hoặc 0 nếu không. Chương trình phải đọc phản hồi rồi mới tiếp tục.
• Nếu \(-25\le Q_i\le-2\), câu trả lời của bạn là có \(-Q_i\) chú chuột. Nếu đúng, bộ chấm chuyển sang bộ test tiếp theo, nếu còn.

Bộ chấm in -1 trên một dòng rồi ngừng gửi dữ liệu nếu xảy ra bất kỳ điều nào sau đây:

1. Chương trình gửi giá trị sai định dạng, vượt biên — chẳng hạn 1000001, -1, GO_IS_THE_BEST_LANGUAGE — hoặc gửi quá nhiều giá trị trên một dòng, chẳng hạn 1 2.
2. Sau khi đã gửi \(S\) chất lượng món cho bộ test hiện tại, chương trình lại gửi giá trị ngoài đoạn \([-25,-2]\).
3. Chương trình gửi một giá trị trong \([-25,-2]\) nhưng đoán sai. Mỗi bộ test chỉ được đoán một lần.

Sau khi nhận -1, chương trình phải thoát ngay; nếu tiếp tục chờ bộ chấm, nó sẽ bị Time Limit Exceeded thay vì nhận đúng phán quyết như Wrong Answer hay Runtime Error. Chương trình cũng không được gửi thêm bất kỳ thông tin nào sau khi giải xong tất cả bộ test; tiếp tục in sau câu trả lời của test cuối sẽ bị Wrong Answer.

Để tham khảo hiệu năng, nhóm tác giả chạy \(S=10^5\) lượt, chia thành các lô kích thước \(B\): in \(B\) chất lượng, đọc \(B\) phản hồi, rồi lặp lại \(S/B\) lần. Cả Python và C++ đều ghép \(B\) chất lượng vào một biến chuỗi rồi mới in, bảo đảm bộ đệm không bị flush giữa lô. Bảng dưới là số giây, làm tròn lên nửa giây kế tiếp và lấy trường hợp xấu nhất qua nhiều lần chạy:

Với kích thước lô tương đối nhỏ, thời gian chuyển ngữ cảnh giảm xuống dưới \(5\) giây mỗi test, tức dưới một phút cho cả Test Set.

Ràng buộc

• \(1\le T\le10\).
• Số chuột nằm trong \([2,25]\).
• Ngưỡng khẩu vị của mỗi chú nằm trong \([1,10^6]\).
• \(S=10^5\).
• Với mỗi bộ test, đa tập ngưỡng khẩu vị và hạt giống sinh số ngẫu nhiên được ban tổ chức tạo trước cuộc thi, giống nhau cho mọi thí sinh và mọi lần nộp. Vì thế hai bài nộp cung cấp cùng số món \(s_i\) cho test \(i\) sẽ thấy cùng thứ tự xuất hiện.

Phân nhóm

Test Set 1 (Visible): Không có hai chú chuột cùng ngưỡng khẩu vị. Mỗi thứ tự xuất hiện được chọn đều ngẫu nhiên trong mọi hoán vị và độc lập với mọi thứ tự khác.

Test Set 2 (Hidden):

Thứ tự chuột xuất hiện độc lập với các món được đưa ra.

Ví dụ, hai chú có ngưỡng lần lượt \(1\) và \(2\) có thể xuất hiện ở cả hai Test Set. Ba chú với ngưỡng \(1,1,2\) có thể xuất hiện ở Test Set 2 nhưng không ở Test Set 1. Sáu chú với ngưỡng \(1,1,1,1,2,2\) không thể xuất hiện ở Test Set 2 vì các bội số là \(4\) và \(2\), có gcd bằng \(2\); cũng không thể ở Test Set 1 vì có ngưỡng trùng. Hai chú cùng ngưỡng \(7\) cũng không thể xuất hiện ở bất kỳ Test Set nào.

Ví dụ

  // In this example, the problem setters have already determined that the first
  // test case has two gophers with taste levels 1 and 2 (we will call them A
  // and B, respectively), and that the second test case has four gophers with
  // taste levels 1, 999, 123, and 4567 (we will call them C, D, E, and F,
  // respectively).
  // The judge randomly generates the first order: A, B.
  t = readline_int()           // Code reads 2 into t.
  s = readline_int()           // Code reads 100000 into s.
  printline 1 to stdout        // Code sends a snack with quality level 1.
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate the
                               //   snack).
  printline 1 to stdout
  flush stdout
  resp = readline_srt()        // Code reads 0 into resp (gopher B did not eat
                               //   the snack).
                               // Judge randomly generates B, A as the next
                               //   order.
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher B ate the
                               //   snack).
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate the
                               //   snack).
                               // Judge randomly generates B, A as the next
                               //   order.
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher B ate the
                               //   snack).
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate the
                               //   snack).
  printline -2 to stdout       // Code correctly determines that the only
  flush stdout                 //   scenario consistent with the information
                               //   given so far is two gophers with taste
                               //   levels 1 and 2.
                               // Judge rules that the answer is correct, and
                               //   prepares the next test case...
                               // Judge randomly generates C, E, F, D as the
                               //   first order.
  s = readline_int()           // Code reads 100000 into s. (This also shows
                               //   that the answer to the first test case was
                               //   correct.)
  printline 0 to stdout        // Code sends an invalid value.
  flush stdout
  resp = readline_str()        // Code reads -1 into resp.
  exit                         // Code exits to avoid an ambiguous TLE error.

  // In this example, the problem setters have already determined that the first
  // test case has three gophers with taste levels 1, 2, and 1; we will call
  // them A, B, and C, respectively, and they will be ordered ABCCBAABCCBA...
  t = readline_int()           // Code reads 1 into t.
  s = readline_int()           // Code reads 100000 into s.
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher A ate
                               //   the snack).
  printline 1 to stdout
  flush stdout
  resp = readline_srt()        // Code reads 0 into resp (gopher B did not eat
                               //   the snack).
  printline 1 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher C ate the
                               //   snack).
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher C ate the
                               //   snack).
  printline 2 to stdout
  flush stdout
  resp = readline_str()        // Code reads 1 into resp (gopher B ate the
                               //   snack).
  printline -2 to stdout       // Code erroneously decides that there
                               //   are two gophers A and B with taste levels
                               //   1 and 2; this is consistent with the
                               //   information given so far for the order
                               //   A,B,A,B,A, but the true number of gophers
  flush stdout                 //   is different, so judge rules it is wrong.
  s = readline_str()           // Code tries to read s but gets -1, meaning
                               //   that the answer to the last test case was
                               //   wrong.
  exit                         // Code exits to avoid an ambiguous TLE error.

Công cụ kiểm thử

Có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng. Khi chạy cục bộ, cần chạy công cụ song song với chương trình, chẳng hạn qua interactive runner chính thức của Code Jam, và làm theo hướng dẫn trong các chú thích của tệp runner cũng như mục Interactive Problems trong FAQ.

Hướng dẫn dùng công cụ nằm trong chú thích của chính công cụ. Nhóm tác giả khuyến khích bổ sung test riêng. Công cụ chỉ mô phỏng hệ thống chấm, không phải hệ thống chấm thật và có thể hành xử khác. Nếu chương trình qua công cụ nhưng trượt hệ thống thật, cần kiểm tra rằng đang dùng cùng trình biên dịch với hệ thống Code Jam.

Tệp công cụ cục bộ chính thức là local_testing_tool.py trong gói bài toán.

Nguồn

Google Code Jam 2018, Chung kết thế giới, bài Go, Gophers!.

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