Trong bài này, khi một đối tượng được nói là chọn ngẫu nhiên, nghĩa là nó được chọn đều trong mọi khả năng hợp lệ và độc lập với mọi lựa chọn khác.

Các thí sinh Code Jam từng giúp Goro hùng mạnh sắp xếp một mảng số nguyên. Bạn không cần đọc bài đó để giải bài này. Một lần nữa, Goro cần bạn giúp. Goro có \(N\) chiếc hộp đặt thành một hàng trên bàn, đánh số từ \(1\) tới \(N\) theo chiều trái sang phải. Mỗi hộp chứa đúng một quả bóng; các bóng cũng được đánh số từ \(1\) tới \(N\). Goro muốn bóng \(i\) nằm trong hộp \(i\) với mọi \(i\), tức muốn các bóng ở thứ tự đã sắp xếp. Tiếc rằng ban đầu chúng không ở thứ tự đó.

Khi Goro đập chiếc bàn bằng nắm đấm đầy uy lực, các quả bóng bật lên rồi rơi trở lại vào hộp. Goro có thể làm chính xác tới mức mỗi hộp nhận đúng một bóng. Một quả bóng có thể rơi lại hộp cũ hoặc sang hộp khác.

Tuyệt hơn nữa, trước mỗi lần đập, Goro có thể gán màu cho các hộp. Sau đó, anh đập bàn sao cho bóng bay ra từ hộp màu \(c\) luôn rơi vào một hộp màu \(c\). Dù khả năng này rất ấn tượng, Goro không điều khiển được gì thêm: bên trong mỗi nhóm màu, các bóng được gán ngẫu nhiên vào các hộp.

Chẳng hạn, giả sử bóng xuất hiện theo thứ tự \(1,4,3,6,5,2\) như hình. Goro có thể chọn — không nhất thiết tối ưu — tô hộp thứ nhất màu đỏ, hộp thứ hai và thứ sáu màu xanh lá, hộp thứ ba tới thứ năm màu xanh dương. Sau khi Goro đập bàn:

• Bóng \(1\) trong hộp thứ nhất rơi lại chính hộp đó vì đây là hộp đỏ duy nhất.
• Hai bóng \(4\) và \(2\) trong hộp thứ hai và thứ sáu giữ nguyên vị trí với xác suất \(1/2\), và đổi chỗ với xác suất \(1/2\).
• Ba bóng \(3,6,5\) trong hộp thứ ba, tư, năm nhận một trong sáu thứ tự sau, mỗi thứ tự có xác suất \(1/6\): \(3,6,5\); \(3,5,6\); \(6,3,5\); \(6,5,3\); \(5,3,6\); \(5,6,3\).

Vì thế, chẳng hạn, xác suất một lần đập để lại thứ tự \(1,2,3,5,6,4\) là \(1/12\). Nếu Goro nhận kết quả này hoặc một kết quả chưa sắp xếp khác, anh phải chỉ định một bộ màu hộp cho lượt kế tiếp, rồi tiếp tục cho tới khi cuối cùng đạt \(1,2,3,4,5,6\). Trước mỗi lần đập, Goro có thể gán màu theo bất kỳ cách nào, không phụ thuộc những lần gán trước.

Hãy giúp Goro cài đặt một chiến lược tốt hơn để sắp xếp bóng hiệu quả. Dữ liệu bảo đảm thứ tự ban đầu của bóng là một hoán vị chưa sắp được chọn ngẫu nhiên.

Dữ liệu vào

Đây là bài tương tác. Hãy bảo đảm bạn đã đọc phần Interactive Problems trong FAQ của Google Code Jam.

Ban đầu, chương trình đọc một dòng chứa ba số nguyên \(T,N,K\): số bộ test, số hộp trong mỗi bộ test và tổng số lần đập được phép trên tất cả bộ test. Sau đó phải xử lý \(T\) bộ test.

Dữ liệu ra

Chương trình phải gửi các phép gán màu theo giao thức tương tác bên dưới và kết thúc đúng thời điểm. Sau mỗi lần in dữ liệu, phải đẩy bộ đệm đầu ra.

Giao thức tương tác

Mỗi bộ test bắt đầu khi bộ chấm gửi một dòng gồm \(N\) số nguyên, trong đó mỗi số từ \(1\) tới \(N\) xuất hiện đúng một lần. Danh sách được chọn ngẫu nhiên trong tất cả danh sách chưa sắp. Sau đó, chương trình thực hiện một chuỗi lượt tương tác với bộ chấm.

Trong mỗi lượt tương tác:

• Chương trình gửi một dòng gồm \(N\) số nguyên \(C_1,C_2,\ldots,C_N\), mỗi số thuộc \([1,N]\). \(C_i\) nghĩa là gán màu \(C_i\) cho hộp \(i\) trong lần đập tiếp theo. Bạn được tự chọn số màu và cách đánh số màu, nhưng phải gán màu cho mọi hộp.
• Bộ chấm mô phỏng lần đập như đề mô tả. Nếu kết quả đã sắp xếp:
• Nếu đây là lượt tương tác thứ \(K\) tính trên tất cả bộ test và chưa phải bộ test cuối, bộ chấm gửi một dòng chứa \(-1\) rồi không xuất gì thêm.
• Nếu không, bộ chấm gửi một dòng chứa \(1\), rồi lập tức bắt đầu bộ test kế tiếp nếu còn. Nếu đây là bộ test cuối, chương trình phải kết thúc không lỗi và không gửi thêm gì.
• Nếu bóng vẫn chưa được sắp:
• Nếu đây là lượt tương tác thứ \(K\) trên tất cả bộ test, hoặc chương trình gửi dòng không hợp lệ, chẳng hạn thiếu số hoặc màu ngoài miền, bộ chấm gửi một dòng chứa \(-1\) rồi không xuất gì thêm.
• Nếu chưa phải lượt thứ \(K\), bộ chấm gửi một dòng chứa \(0\), sau đó một dòng gồm \(N\) số nguyên tạo thành một hoán vị chưa sắp của \(1,\ldots,N\). Số thứ \(i\) là quả bóng vừa rơi vào hộp \(i\). Chương trình tiếp tục lượt tương tác kế.

Như thường lệ, nếu vượt giới hạn bộ nhớ hoặc chương trình gặp lỗi chạy, bài sẽ nhận phán quyết tương ứng. Nếu chương trình tiếp tục chờ sau khi nhận \(-1\), nó sẽ hết thời gian. Bạn có trách nhiệm cho chương trình thoát kịp để nhận Wrong Answer thay vì Time Limit Exceeded.

Bộ chấm sử dụng cùng một nguồn ngẫu nhiên ở mỗi lần chạy. Vì vậy, nếu không có lỗi khác như quá thời gian hay quá bộ nhớ, nộp đúng cùng một mã nguồn hai lần sẽ cho đúng cùng một kết quả hai lần.

Ràng buộc

• \(T=1000\).
• \(N=100\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): tổng số lượt cho phép \(K=16500\).
• Test Set 2 (phán quyết hiển thị): tổng số lượt cho phép \(K=12500\).
• Test Set 3 (phán quyết hiển thị): tổng số lượt cho phép \(K=11500\).

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử để 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; có thể dùng interactive runner. Hãy đọc hướng dẫn trong phần chú thích của tệp đó và phần Interactive Problems trong FAQ.

Hướng dẫn cho công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Bạn được khuyến khích thêm test riêng. Dù công cụ nhằm mô phỏng hệ thống chấm, nó không phải hệ thống chấm thật và có thể hành xử khác. Nếu mã vượt qua công cụ nhưng trượt bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm dùng cùng trình biên dịch với hệ thống chính thức.

Ví dụ

2 4 8

1 4 3 2

1 2 3 2

0
1 4 3 2

1 2 3 2

1

2 1 4 3

4 4 4 4

1

Nguồn

Google Code Jam 2022, Vòng 3, bài Revenge of GoroSort.

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