Lưu ý: Các phần chính của đề bài cho các bài "Reversort" và "Reversort Engineering" là giống hệt nhau, ngoại trừ đoạn cuối cùng. Ngoài ra, hai bài toán có thể được giải độc lập.

Reversort là một thuật toán để sắp xếp một danh sách các số nguyên phân biệt theo thứ tự tăng dần. Thuật toán dựa trên thao tác "Reverse" (đảo ngược). Mỗi lần áp dụng thao tác này sẽ đảo ngược thứ tự của một phần liên tiếp trong danh sách.

Mã giả của thuật toán như sau:

Reversort(L):
  for i := 1 to length(L) - 1
    j := position with the minimum value in L between i and length(L), inclusive
    Reverse(L[i..j])

Sau \(i-1\) lần lặp, các vị trí \(1, 2, \dots, i-1\) của danh sách chứa \(i-1\) phần tử nhỏ nhất của \(L\), theo thứ tự tăng dần. Trong lần lặp thứ \(i\), quá trình này đảo ngược danh sách con đi từ vị trí thứ \(i\) đến vị trí hiện tại của phần tử nhỏ thứ \(i\). Điều đó làm cho phần tử nhỏ thứ \(i\) kết thúc ở vị trí thứ \(i\).

Ví dụ, đối với một danh sách có \(4\) phần tử, thuật toán sẽ thực hiện \(3\) lần lặp. Đây là cách nó xử lý \(L = [4, 2, 1, 3]\):

1. \(i = 1, j = 3 \longrightarrow L = [1, 2, 4, 3]\)
2. \(i = 2, j = 2 \longrightarrow L = [1, 2, 4, 3]\)
3. \(i = 3, j = 4 \longrightarrow L = [1, 2, 3, 4]\)

Phần tốn kém nhất khi thực thi thuật toán trên kiến trúc của chúng tôi là thao tác Reverse. Do đó, thước đo chi phí của mỗi lần lặp đơn giản là độ dài của danh sách con được truyền vào Reverse, tức là giá trị \(j - i + 1\). Chi phí của toàn bộ thuật toán là tổng chi phí của mỗi lần lặp.

Trong ví dụ trên, các lần lặp có chi phí lần lượt là \(3, 1\) và \(2\), tổng cộng là \(6\).

Cho kích thước \(N\) và chi phí \(C\). Hãy tìm một danh sách gồm \(N\) số nguyên phân biệt từ \(1\) đến \(N\) sao cho chi phí áp dụng Reversort lên nó đúng bằng \(C\), hoặc cho biết không tồn tại danh sách như vậy.

Dữ liệu vào

Dòng đầu chứa số lượng bộ dữ liệu \(T\). Tiếp theo là \(T\) dòng; mỗi dòng mô tả một bộ dữ liệu bằng hai số nguyên \(N\) và \(C\), lần lượt là kích thước danh sách cần tìm và chi phí mong muốn.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu không có danh sách kích thước \(N\) mà Reversort có chi phí đúng bằng \(C\), in Case #x: IMPOSSIBLE, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)).

Nếu có, in Case #x: y_1 y_2 ... y_N, trong đó mỗi \(y_i\) là một số nguyên phân biệt từ \(1\) đến \(N\), biểu diễn phần tử thứ \(i\) của một danh sách hợp lệ. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào. Quy ước về nhiều đáp án này sẽ không được nhắc lại trong phần còn lại của Code Jam 2021.

Ràng buộc

• \(1\le T\le100\).
• \(1\le C\le1000\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(2\le N\le7\).
• Test Set 2 (Visible Verdict): \(2\le N\le100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
4 6
2 1
7 12
7 2
2 1000

Case #1: 4 2 1 3
Case #2: 1 2
Case #3: 7 6 5 4 3 2 1
Case #4: IMPOSSIBLE
Case #5: IMPOSSIBLE

Nguồn

Google Code Jam 2021, Vòng loại, bài Reversort Engineering.

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