Google Code Jam 2021 - Minimum Sort
Xem PDFMinimum Sort
Trong bài này, bạn phải sắp xếp một danh sách gồm \(N=100\) số nguyên phân biệt theo thứ tự tăng nghiêm ngặt. Bạn có thể hoán đổi nội dung của hai vị trí bất kỳ; chúng không cần kề nhau. Tuy nhiên, bạn không thể đọc trực tiếp các nội dung đó.
Bạn lấy thông tin về danh sách bằng truy vấn giá trị nhỏ nhất của một đoạn. Truy vấn trả về vị trí của giá trị nhỏ nhất trong một đoạn vị trí liên tiếp. Ví dụ, trong danh sách \([51,33,100,11]\), giá trị nhỏ nhất trên đoạn vị trí \(2\) đến \(4\) (đánh số từ \(1\)) nằm ở vị trí \(4\); còn giá trị nhỏ nhất trên đoạn \(1\) đến \(3\) nằm ở vị trí \(2\).
Các truy vấn này bị giới hạn bởi ngân sách xu của từng bộ dữ liệu. Đoạn càng dài thì càng rẻ: hỏi vị trí nhỏ nhất giữa \(i\) và \(j\) với \(i<j\) tốn
xu, trong đó \(\lceil x\rceil\) là số nguyên nhỏ nhất không nhỏ hơn \(x\). Trái lại, thao tác hoán đổi không tốn xu.
Hãy viết chương trình sắp xếp danh sách bằng số lần hoán đổi tùy ý và tổng chi phí không quá \(6\times10^8\) xu cho các truy vấn giá trị nhỏ nhất trong mỗi bộ dữ liệu.
Giao thức tương tác
Các mục Dữ liệu vào và Dữ liệu ra dưới đây quy định đầy đủ cuộc đối thoại giữa chương trình và bộ chấm.
Dữ liệu vào
Đây là bài tương tác. Ban đầu, bộ chấm gửi một dòng chứa hai số nguyên \(T,N\): số bộ dữ liệu và số phần tử cần sắp xếp trong mỗi bộ. Bộ chấm đã cố định các danh sách trước khi nhận đầu vào từ chương trình; trong quá trình trao đổi, chúng chỉ thay đổi bởi những phép hoán đổi bạn yêu cầu.
Sau đó, bạn phải xử lý \(T\) bộ dữ liệu. Mỗi bộ gồm một chuỗi lượt trao đổi và một dòng bổ sung để báo đã hoàn tất. Trong mỗi lượt, chương trình in một dòng, rồi bộ chấm in một dòng phản hồi.
Dữ liệu ra
Ở mỗi lượt, chương trình phải in đúng một trong các lệnh sau:
M i j, với \(i<j\), biểu diễn truy vấn giá trị nhỏ nhất. Bộ chấm trả về một số nguyên là vị trí của giá trị nhỏ nhất trong đoạn vị trí \([i,j]\), đánh số từ \(1\).S i j, với \(i<j\), biểu diễn thao tác hoán đổi. Bộ chấm đổi hai phần tử tại vị trí \(i,j\) và trả về1.D, báo rằng bạn đã sắp xếp xong danh sách. Bộ chấm kiểm tra danh sách và trả1nếu nó tăng nghiêm ngặt, hoặc-1nếu không.
Sau khi bộ chấm trả 1 cho lệnh D, nếu đây là bộ cuối thì phiên làm việc kết thúc; nếu không, bộ chấm lập tức chờ lệnh đầu tiên của bộ tiếp theo. Sau khi nhận phản hồi cho bộ dữ liệu thứ \(T\), chương trình phải kết thúc.
Nếu tại bất cứ lúc nào bộ chấm nhận một dòng sai định dạng, một giá trị không hợp lệ, hoặc một truy vấn M làm vượt ngân sách còn lại, nó in -1 và không in thêm gì nữa. Sau khi nhận -1, chương trình phải thoát ngay; nếu tiếp tục chờ, chương trình sẽ bị treo. Hãy nhớ xả bộ đệm đầu ra sau mỗi lệnh.
Ràng buộc
- \(T=100\).
- \(N=100\).
Phân nhóm
- Test Set 1 (Visible Verdict): các ràng buộc như trên.
Ví dụ
Ví dụ tương tác
Ví dụ sau dùng \(T=2,N=4\) chỉ để minh họa và không thỏa ràng buộc chính thức.
| Bộ chấm | Chương trình | Diễn giải |
|---|---|---|
2 4 |
Bộ chấm cung cấp \(T,N\). Bộ 1 có danh sách \([51,33,100,11]\). | |
M 2 4 |
Hỏi min trên \([2,4]\), tốn \(\lceil10^8/3\rceil=33333334\) xu. | |
4 |
Min của đoạn nằm ở vị trí \(4\). | |
M 1 3 |
Hỏi min trên \([1,3]\), tốn \(33333334\) xu. | |
2 |
Min của đoạn nằm ở vị trí \(2\). | |
S 1 4 |
Đổi vị trí \(1,4\). | |
1 |
Danh sách thành \([11,33,100,51]\). | |
M 3 4 |
Hỏi min trên \([3,4]\), tốn \(50000000\) xu. | |
4 |
Min của đoạn nằm ở vị trí \(4\). | |
S 3 4 |
Đổi vị trí \(3,4\). | |
1 |
Danh sách thành \([11,33,51,100]\). | |
D |
Báo hoàn tất; tổng chi phí \(116666668\) xu. | |
1 |
Danh sách đã tăng nghiêm ngặt. Bộ 2 có danh sách \([30,20,10,40]\). | |
M 1 4 |
Hỏi min trên \([1,4]\), tốn \(25000000\) xu. | |
3 |
Min nằm ở vị trí \(3\). | |
S 1 3 |
Đổi vị trí \(1,3\). | |
1 |
Danh sách thành \([10,20,30,40]\). | |
M 3 4 |
Hỏi min trên \([3,4]\), tốn \(50000000\) xu. | |
3 |
Min nằm ở vị trí \(3\). | |
M 2 4 |
Hỏi min trên \([2,4]\), tốn \(33333334\) xu. | |
2 |
Min nằm ở vị trí \(2\). | |
D |
Báo hoàn tất; tổng chi phí \(108333334\) xu. | |
1 |
Danh sách đã tăng nghiêm ngặt; cả hai bộ hoàn tất. |
Công cụ kiểm thử
Kho bài gốc cung cấp công cụ để kiểm thử cục bộ hoặc trên nền tảng Code Jam. Khi chạy cục bộ, cần chạy công cụ song song với lời giải, chẳng hạn qua interactive runner. Hướng dẫn sử dụng nằm trong phần chú thích của công cụ; bạn được khuyến khích tự thêm bộ dữ liệu.
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. Việc vượt qua công cụ không bảo đảm vượt qua bộ chấm. Bản chuyển thể LQDOJ dùng interactor đi kèm gói bài thay cho công cụ tải xuống này.
Nguồn
Google Code Jam 2021, Vòng 2, bài Minimum Sort.
Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.
Kỳ thi:
- Google Code Jam 2021 - Round 2 (15 Tháng năm, 2021)
Bình luận