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 danh sách ban đầu, hãy tính chi phí thực thi Reversort trên danh sách đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ dữ liệu, \(T\). Tiếp theo là \(T\) bộ dữ liệu.
Mỗi bộ dữ liệu gồm 2 dòng. Dòng đầu tiên chứa một số nguyên duy nhất \(N\), đại diện cho số lượng phần tử trong danh sách đầu vào. Dòng thứ hai chứa \(N\) số nguyên phân biệt \(L_1, L_2, \dots, L_N\), đại diện cho các phần tử của danh sách đầu vào \(L\), theo thứ tự.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy xuất một dòng chứa Case #$x$: $y$, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ 1) và \(y\) là tổng chi phí thực thi Reversort trên danh sách được cung cấp ở đầu vào.

Ràng buộc

• \(1 \le T \le 100\).
• \(2 \le N \le 100\).
• \(1 \le L_i \le N\), với mọi \(i\).
• \(L_i \ne L_j\), với mọi \(i \ne j\).

Phân nhóm

• Test Set 1 (Visible Verdict): Các ràng buộc như trên.

Đ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ụ

3
4
4 2 1 3
2
1 2
7
7 6 5 4 3 2 1

Case #1: 6
Case #2: 1
Case #3: 12

Nguồn

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

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