Power Arrangers

Đề bài

Tiến lên nào, các Power Arranger! Ai cũng yêu mến đội gồm năm siêu anh hùng đang là học sinh trung học này, mỗi người mang một trong các chữ cái A, B, C, D và E. Khi đứng cạnh nhau để đối đầu với quái vật xấu xa, họ sắp xếp đội hình theo một trong 120 thứ tự từ trái sang phải khác nhau có thể có, qua đó tạo ra nhiều siêu năng lực chiến thuật khác nhau. Họ thậm chí còn nổi tiếng hơn cả các Teenage Permutant Ninja Turtles!

Một số nhà phê bình chương trình cho rằng đội chỉ dùng mánh lới thay đổi đội hình để chủ sở hữu chương trình có thể bán 120 bộ riêng biệt, mỗi bộ gồm 5 mô hình nhân vật hành động. Trong mỗi bộ, cả đội được xếp theo một thứ tự từ trái sang phải khác nhau và được dán vào đế nên không thể sắp xếp lại. Là một người hâm mộ Power Arrangers cuồng nhiệt, bạn đã sưu tập được 119 bộ như vậy, nhưng không nhớ mình còn thiếu bộ nào. 119 bộ được xếp thành một hàng ngang trên kệ, tạo thành tổng cộng \(119 \times 5 = 595\) mô hình theo thứ tự từ trái sang phải. Bạn không nhớ các bộ được sắp xếp theo thứ tự nào, nhưng biết rằng trong mỗi test, hoán vị thứ tự của các bộ được chọn ngẫu nhiên đều trong tất cả các hoán vị có thể có và độc lập với các test khác.

Bạn không muốn tốn thời gian xác định bộ còn thiếu, nên dự định chỉ xem chữ cái trên nhiều nhất F mô hình trên kệ. Chẳng hạn, bạn có thể chọn xem chữ trên mô hình thứ tám từ trái sang; đó chính là mô hình thứ ba từ trái sang trong bộ thứ hai tính từ trái. Khi xem một mô hình, bạn chỉ biết được chữ cái của riêng mô hình đó; các chữ rất khó nhìn, còn ngoài ra các thành viên trong đội trông rất giống nhau!

Sau khi kiểm tra nhiều nhất F mô hình, bạn phải xác định được bộ nào còn thiếu để hoàn thiện bộ sưu tập và sẵn sàng đối mặt với mọi mối đe dọa xấu xa có thể xảy ra!

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. Hãy bảo đảm rằng bạn đã đọc thông tin trong phần Bài toán tương tác của trang câu hỏi thường gặp.

Ban đầu, chương trình phải đọc một dòng chứa hai số nguyên T — số lượng test — và F — số mô hình được phép kiểm tra trong mỗi test. Sau đó, bạn cần xử lý T test.

Trong mỗi test, bộ mô hình bị thiếu được chọn ngẫu nhiên đều trong tất cả các bộ có thể có; thứ tự của các bộ còn lại cũng được chọn ngẫu nhiên đều trong tất cả các thứ tự có thể có. Mọi lựa chọn đều độc lập với tất cả lựa chọn khác và với dữ liệu mà chương trình của bạn gửi ra.

Trong mỗi test, chương trình sẽ thực hiện nhiều nhất F + 1 lượt trao đổi với bộ chấm. Bạn được thực hiện nhiều nhất F lượt trao đổi theo dạng sau:

• Chương trình in một dòng chứa một số nguyên từ 1 đến 595 (kể cả hai đầu), chỉ ra mô hình mà bạn muốn xem theo thứ tự từ trái sang phải trên kệ. Thêm một ví dụ: 589 biểu thị mô hình thứ tư từ trái sang trong bộ thứ hai tính từ bên phải.
• Bộ chấm trả lời bằng một dòng chứa duy nhất một chữ cái in hoa A, B, C, D hoặc E, cho biết chữ trên mô hình đó. Nếu bạn gửi dữ liệu không hợp lệ (ví dụ: một số nằm ngoài phạm vi hoặc một dòng sai định dạng), thay vào đó bộ chấm sẽ trả lời bằng một dòng chỉ chứa chữ cái in hoa N.

Sau đó, khi đã thực hiện số lượt trao đổi nói trên mà bạn muốn (không vượt quá F), bạn phải thực hiện thêm một lượt trao đổi theo dạng sau:

• Chương trình in một dòng chứa duy nhất một xâu gồm năm chữ cái in hoa: hoán vị tương ứng với bộ bị thiếu (ví dụ: CADBE).
• Bộ chấm trả lời bằng một dòng chứa duy nhất một chữ cái in hoa: Y nếu câu trả lời đúng, và N nếu câu trả lời sai (hoặc nếu bạn gửi một dòng sai định dạng). Nếu nhận được Y, bạn phải bắt đầu test tiếp theo; nếu không còn test nào, hãy ngừng gửi dữ liệu.

Sau khi bộ chấm gửi N vào luồng dữ liệu vào của chương trình (do dữ liệu không hợp lệ hoặc câu trả lời sai), bộ chấm sẽ không gửi thêm bất kỳ dữ liệu nào. Nếu chương trình vẫn tiếp tục chờ bộ chấm sau khi nhận N, 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 kết thúc chương trình đủ sớm để nhận phán quyết Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu vượt giới hạn bộ nhớ hoặc chương trình gặp lỗi khi chạy, bạn sẽ nhận phán quyết tương ứng.

Ràng buộc

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

Bộ bị thiếu và thứ tự của các bộ còn lại được chọn ngẫu nhiên đều và độc lập với nhau.

Phân nhóm

Test 1 (Công khai)

F = 475.

Test 2 (Ẩn)

F = 150.

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 tra cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm tra 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 phần chú thích của tệp ấy, đồng thời xem phần Bài toán tương tác trong trang câu hỏi thường gặp.

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 bổ sung các test của riêng mình. Xin lưu ý rằng 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 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 trang 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, f = readline_int_list()   // Đọc 50 vào t và 475 vào f
  printline 10 to stdout       // Xem mô hình cuối cùng trong bộ thứ hai
                               // tính từ bên trái
  flush stdout
  n = readline_string()        // Đọc B vào n. Ồ, thành viên B! Có thể họ không có
                               // năng lực lãnh đạo như A hay kỹ năng kỹ thuật như C,
                               // nhưng họ giúp cả đội vui vẻ bằng những câu nói đùa
                               // thông minh!
  printline 11 to stdout       // Xem mô hình đầu tiên trong bộ thứ ba
                               // tính từ bên trái
  flush stdout
  n = readline_string()        // Đọc B vào n. Lưu ý rằng B đứng đầu bộ thứ ba,
                               // trong khi họ đứng cuối bộ thứ hai.
  printline 14 to stdout       // Xem mô hình thứ tư trong bộ thứ ba
                               // tính từ bên trái
  flush stdout
  n = readline_string()        // Đọc D vào n. Tuy ít nói và trầm tư, thành viên D
                               // vẫn chiến đấu quyết liệt để bảo vệ bạn bè...
                               // và cả thế giới!
  printline ABCDE to stdout    // Ta dại dột đoán bừa dù vẫn còn có thể xem thêm
                               // nhiều nhất 472 mô hình nữa.
  flush stdout
  verdict = readline_string()  // Đọc N vào verdict (bộ chấm đã xác đị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 1C, bài Power Arrangers.

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