Đề bài

Năm ngoái, một lũ chuột túi má phiền phức đã đến cư trú trong vườn cây ăn quả của chúng tôi. Chúng tôi đã thử đổi nghề bằng cách mở một sân golf thu nhỏ, nhưng có vẻ như lũ chuột cũng theo chúng tôi đến đây! Một lần nữa, chúng tôi cần xác định có bao nhiêu con chuột, nhưng không thể quan sát trực tiếp vì chúng kín đáo và hoạt động về đêm, trong khi chúng tôi lại thích ngủ vào ban đêm. Chúng tôi biết số chuột nằm trong khoảng từ \(1\) đến M, tính cả hai đầu.

Sân golf thu nhỏ của chúng tôi nổi tiếng vì có một cối xay gió điện tử nhỏ trên mỗi lỗ trong số 18 lỗ. Cối xay thứ \(i\) có \(2 \leq \mathbf{B}_i \leq 18\) cánh, được đánh số theo chiều kim đồng hồ từ \(0\) đến \(\mathbf{B}_i-1\). Mỗi đêm, trước khi đi ngủ, chúng tôi tắt các cối xay và đặt tất cả sao cho cánh số \(0\) hướng xuống dưới; điều này rất quan trọng để các cối xay có thể sạc đúng cách cho ngày hôm sau. Tuy nhiên, chúng tôi nhận thấy rằng khi thức dậy, các cối xay đã bị tác động. Vì sân golf thu nhỏ nằm ở một khu vực không có gió, chúng tôi cho rằng chính lũ chuột nghịch ngợm là thủ phạm!

Chúng tôi biết rằng mỗi đêm, tất cả chuột lần lượt chui ra; mỗi con chọn độc lập và ngẫu nhiên đều một trong các cối xay, rồi xoay cối đó ngược chiều kim đồng hồ một cánh. Chẳng hạn, với một cối xay có 3 cánh và cánh số 0 đang hướng xuống, con chuột đầu tiên tác động vào nó sẽ xoay để cánh số 1 hướng xuống; những con tiếp theo tác động vào cối xay đó sẽ lần lượt làm cho cánh hướng xuống mang số 2, rồi 0, rồi 1, và cứ tiếp tục như vậy.

Chúng tôi đã nghĩ ra một kế hoạch. Các cối xay được thiết kế sao cho có thể dễ dàng thay đổi số cánh (để điều chỉnh độ khó của sân), và giờ chúng tôi sẽ tận dụng điều đó! Mỗi đêm, trước khi đi ngủ, chúng tôi có thể chọn số cánh cho từng cối xay trong số 18 cối, miễn là nằm trong giới hạn đã cho; không bắt buộc mọi cối xay phải có cùng số cánh, cũng không bắt buộc phải đưa ra cùng lựa chọn vào mỗi đêm. Vào buổi sáng, chúng tôi sẽ quan sát số ghi trên cánh đang hướng xuống của từng cối xay.

Chúng tôi có N đêm để xác định \(G\), số lượng chuột. Bạn có thể giúp chúng tôi không?

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là một bài toán tương tác. Bạn cần bảo đảm rằng mình đã đọc thông tin trong phần Bài toán tương tác của mục Câu hỏi thường gặp.

Ban đầu, chương trình phải đọc một dòng chứa ba số nguyên T, N và M, lần lượt là số lượng bộ test, số đêm được phép sử dụng trong mỗi bộ test và số chuột tối đa. Sau đó, bạn cần xử lý T bộ test.

Trong mỗi bộ test, chương trình thực hiện tối đa N + 1 lượt trao đổi với bộ chấm. Bạn có thể thực hiện tối đa N lượt trao đổi có dạng sau:

• Chương trình in một dòng gồm mười tám số nguyên từ 2 đến 18, tính cả hai đầu; số thứ \(i\) biểu thị số cánh mà bạn muốn cối xay thứ \(i\) có trong đêm đó.
• Bộ chấm trả lời bằng một dòng gồm mười tám số nguyên; số thứ \(i\) biểu thị số ghi trên cánh đang hướng xuống của cối xay thứ \(i\) vào buổi sáng, sau khi lũ chuột đã nghịch phá. Nếu bạn gửi dữ liệu không hợp lệ (chẳng hạn một số nằm ngoài phạm vi hoặc một dòng sai định dạng), bộ chấm sẽ trả lời -1 thay vào đó.

Trong mỗi đêm, đối với mỗi con chuột, cối xay mà nó chọn để xoay được chọn ngẫu nhiên (giả ngẫu nhiên) và đều; lựa chọn này độc lập với mọi lựa chọn khác của bất kỳ con chuột nào (kể cả chính nó) trong bất kỳ đêm nào.

Sau khi thực hiện từ 0 đến N lượt trao đổi như mô tả ở trên, bạn phải thực hiện thêm một lượt trao đổi có dạng sau:

• Chương trình in một số nguyên: dự đoán của bạn cho \(G\), số lượng chuột.
• Bộ chấm trả lời bằng một dòng chứa duy nhất một số nguyên: 1 nếu đáp án của bạn đúng, và -1 nếu đáp án sai (hoặc nếu bạn đã cung cấp một dòng sai định dạng).

Sau khi bộ chấm gửi -1 vào luồng đầu vào của chương trình (do dữ liệu không hợp lệ hoặc đáp án không đúng), nó sẽ không gửi thêm bất kỳ dữ liệu nào. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận kết quả Time Limit Exceeded. Bạn có trách nhiệm để chương trình kết thúc đủ sớm nhằm nhận kết quả Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình dùng quá giới hạn bộ nhớ hoặc gặp lỗi khi chạy, bạn sẽ nhận kết quả tương ứng.

Ràng buộc

\(1 \leq \mathbf{T} \leq 20\).

Phân nhóm

Test set 1 (Công khai)

\(\mathbf{N} = 365\).
\(\mathbf{M} = 100\).

Test set 2 (Ẩn)

\(\mathbf{N} = 7\).
\(\mathbf{M} = 10^6\).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm thử cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm thử cục bộ, bạn cần chạy công cụ song song với chương trình của mình; bạn có thể dùng trình chạy tương tác của chúng tôi cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong các chú thích của tệp đó và xem thêm phần Bài toán tương tác trong mục Câu hỏi thường gặp.

Hướng dẫn dành cho công cụ kiểm thử được viết trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn bổ sung các bộ test của riêng mình. Xin lưu ý rằng mặc dù công cụ kiểm thử được xây dựng để mô phỏng hệ thống chấm, nó KHÔNG PHẢI là hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy xem phần Lập trình trong mục Câu hỏi thường gặp để bảo đảm rằng bạn đang dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Ví dụ

  t, n, m = readline_int_list()   // Đọc 20 vào t, 365 vào n và 100 vào m.
  // Chọn số cánh cho đêm thứ nhất.
  printline 2 2 2 2 18 3 3 3 3 3 3 4 4 4 4 5 2 2 to stdout
  flush stdout
  // Đọc 0 0 0 0 0 0 1 2 1 0 1 2 0 0 0 0 1 0 vào res.
  res = readline_int_list()
  // Chọn số cánh cho đêm thứ hai.
  printline 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 to stdout
  flush stdout
  // Đọc 0 1 1 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 vào res.
  res = readline_int_list()
  printline 8 to stdout        // Ta đưa ra dự đoán sai dù vẫn có thể
  flush stdout                 // điều tra thêm tối đa 363 đêm nữa.
  verdict = readline_int()     // Đọc -1 vào verdict (bộ chấm đã quyết định rằng
                               //   lời giải của ta không đúng)
  exit                         // Thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2019, Vòng 1A, bài Golf 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.