Đề bài

Pottery Palace sắp tổ chức một cuộc xổ số với phần thưởng là những chiếc bình quý giá của nghệ sĩ Cody-Jamal. Cuộc xổ số diễn ra như sau:

• Có 100 người tham gia xổ số. Mỗi người chơi có một số hiệu riêng biệt từ 1 đến 100 và được phát đúng một thẻ mang số hiệu đó.
• Trên bàn có 20 chiếc bình đất sét rỗng, được đánh số từ 1 đến 20. Miệng bình hẹp, đủ rộng để bỏ một thẻ vào nhưng đủ nhỏ để người chơi không thể nhìn vào bên trong xem bình chứa gì.
• Vào ngày thứ \(i\) của cuộc xổ số, người chơi có thẻ số \(i\) chọn một chiếc bình rồi bỏ thẻ của mình vào đó. Vì tất cả các bình đều giống hệt nhau (ngoại trừ nhãn số), mỗi người chơi sẽ chọn một bình ngẫu nhiên đều và độc lập với lựa chọn của tất cả người chơi khác.
• Vào ngày thứ 100, sau khi người chơi số 100 đã bỏ thẻ vào bình, ban tổ chức lắc các bình để xác định số thẻ trong mỗi bình. Nếu có đúng một chiếc bình chứa ít thẻ hơn mọi chiếc bình khác thì đó là "bình chiến thắng". Sau đó, ban tổ chức đổ tất cả thẻ trong bình ấy ra, và mỗi người chơi có số hiệu ghi trên một trong các thẻ vừa được đổ ra sẽ thắng một chiếc bình! Nếu nhiều bình cùng có số thẻ ít nhất thì không ai nhận được gì.

Bạn được thuê để kiểm tra tính bảo mật của cuộc xổ số và sẽ tham gia một số lượt chạy thử. Công ty luôn gán cho bạn số 100 — tức là bạn thay thế người chơi số 100.

Bạn đã tìm ra một số cách can thiệp vào cuộc xổ số vào ban đêm, nhưng an ninh rất nghiêm ngặt nên khả năng của bạn có hạn! Cụ thể, sau mỗi ngày trong 99 ngày đầu tiên của cuộc xổ số, bạn được thực hiện đúng một trong hai hành động sau:

• Làm giả một thẻ mang số hiệu người chơi do bạn chọn (từ 1 đến 100, kể cả hai đầu) và thêm thẻ đó vào một bình do bạn chọn. Bạn làm giả rất khéo: nếu có bình chiến thắng, mọi thẻ giả trong bình đó vẫn khiến những người chơi mang số hiệu tương ứng chiến thắng (ngoại trừ một trường hợp được nêu bên dưới).
• Dùng một camera đặc biệt để xem số hiệu trên tất cả các thẻ trong một bình do bạn chọn.

Bạn có thể thực hiện các hành động khác nhau vào những đêm khác nhau và có thể lựa chọn một cách linh hoạt: bạn không cần quyết định trước toàn bộ các hành động.

Vào ngày thứ 100, đến lượt bạn bỏ thẻ của mình vào một bình do bạn chọn (bạn không bắt buộc phải chọn ngẫu nhiên đều). Bạn không thể thực hiện hành động nào khác trong ngày đó.

Bạn biết rằng nếu bình chiến thắng chứa nhiều hơn một thẻ của cùng một người chơi thì việc gian lận sẽ bị phát hiện rõ ràng và không ai chiến thắng. Tuy nhiên, việc những bình khác chứa nhiều hơn một thẻ của cùng một người chơi không quan trọng, vì ban tổ chức không bao giờ nhìn thấy các thẻ đó.

Mục tiêu của bạn là trở thành người chiến thắng trong ít nhất 90% số trường hợp kiểm thử.

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 phần Bài toán tương tác trong FAQ.

Ban đầu, chương trình phải đọc một dòng chứa một số nguyên \(T\), cho biết số lượng trường hợp kiểm thử. Sau đó, bạn cần xử lý \(T\) trường hợp kiểm thử.

Ở đầu mỗi trường hợp kiểm thử, bộ chấm xuất một dòng chứa một số nguyên: số hiệu của ngày hiện tại. (Bộ chấm bắt đầu ở ngày 1 và vào ngày thứ \(i\), bộ chấm in ra \(i\).) Sau khi đọc số nguyên này, chương trình phải xuất một dòng chứa hai số nguyên \(V\) và \(P\), với \(1 \le V \le 20\) và \(0 \le P \le 100\). Bộ chấm diễn giải chúng như sau:

• Nếu \(1 \le P \le 100\), bạn bỏ một thẻ của người chơi \(P\) vào bình \(V\). Bộ chấm không xuất lại bất cứ nội dung phản hồi nào.
• Nếu \(P = 0\), bạn kiểm tra nội dung của bình \(V\). Bộ chấm xuất một dòng gồm các số nguyên. Số nguyên đầu tiên là \(N\), số thẻ trong bình \(V\); tiếp theo là \(N\) số nguyên nữa: số hiệu người chơi trên từng thẻ, theo thứ tự không giảm.

Lưu ý rằng ở lượt 100, bạn phải bỏ thẻ của chính mình vào, nên \(P\) bắt buộc phải bằng 100.

Hãy nhớ rằng vào ngày thứ \(i\), với \(1 \le i \le 99\), bộ chấm mô phỏng hành động của người chơi thứ \(i\) như mô tả trong đề bài. Việc này xảy ra trước hành động của chính bạn trong ngày đó.

Sau khi gửi nước đi cho lượt 100, chương trình phải kết thúc nếu đó là trường hợp kiểm thử cuối cùng; nếu không, chương trình phải bắt đầu đọc dữ liệu cho trường hợp kiểm thử tiếp theo. (Lưu ý rằng bộ chấm không cho bạn biết bạn đã xử lý đúng hay sai từng trường hợp.) Bộ chấm chỉ kiểm tra xem bạn có đủ số câu trả lời đúng hay không sau khi bạn đã thử toàn bộ \(T\) trường hợp kiểm thử, vì vậy bạn không được dừng sớm! Chẳng hạn, nếu bạn trả lời đúng 225 trong 250 trường hợp đầu tiên rồi thoát hoặc cung cấp dữ liệu sai định dạng, lời giải của bạn sẽ không được coi là đúng.

Nếu chương trình xuất nội dung không hợp lệ (ví dụ: đưa ra giá trị \(P\) hoặc \(V\) không hợp lệ, hoặc cố kiểm tra một bình ở lượt 100), bộ chấm sẽ gửi một dòng chứa -1 vào luồng vào của chương trình và không gửi thêm bất cứ dữ liệu nào sau đó. 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 phán quyết Time Limit Exceeded. Bạn có trách nhiệm làm cho chương trình thoát kịp thời để nhận phán quyết Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình vượt quá tổng bộ nhớ cho phép hoặc gặp lỗi khi chạy, bạn sẽ nhận phán quyết tương ứng.

Phân nhóm

Test Set 1 (Hiển thị)

\(T = 250\).

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 ấy và xem thêm phần Bài toán tương tác trong FAQ.

Hướng dẫn sử dụng công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn tự bổ sung các trường hợp kiểm thử. Xin lưu ý rằng mặc dù công cụ kiểm thử được thiết kế để 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 mã của bạn vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy kiểm tra phần Lập trình trong FAQ để 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 = readline_int()           // đọc 250 vào t
  curr_day = readline_int()    // đọc 1 (ngày 1)
  printline 8 100 to stdout    // bỏ một thẻ của người chơi 100 vào bình 8
  flush stdout
  curr_day = readline_int()    // đọc 2 (ngày 2)
  printline 8 99 to stdout     // bỏ một thẻ của người chơi 99 vào bình 8
  flush stdout
  curr_day = readline_int()    // đọc 3 (ngày 3)
  printline 8 100 to stdout    // bỏ một thẻ của người chơi 100 vào bình 8
  flush stdout
  curr_day = readline_int()    // đọc 4 (ngày 4)
  printline 20 7 to stdout     // bỏ một thẻ của người chơi 7 vào bình 20
  flush stdout
  curr_day = readline_int()    // đọc 5 (ngày 5)
  printline 8 0 to stdout      // kiểm tra bình 8
  flush stdout
  tokens = readline_int_list() // đọc 5 2 5 99 100 100 (người chơi 2 và 5
                               //   tình cờ đã chọn bình 8)
  curr_day = readline_int()    // đọc 6 (ngày 6)
  printline 8 101 to stdout    // cố thêm một thẻ mang số hiệu người chơi không hợp lệ
  flush stdout
  curr_day = readline_int()    // đọc -1 (bộ chấm đã xác định lời giải của ta
                               //   không chính xác)
  exit                         // thoát để tránh lỗi TLE không rõ nguyên nhân

Ràng buộc

Nguồn

Google Code Jam 2019, Vòng 2, bài Pottery Lottery.

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