Đếm nghịch thế bất khả thi
Đề bài
Mô tả
Thầy Hành rất thích các con số. Hôm nay, trong giờ giảng thuật toán, thầy viết lên bảng một dãy số nguyên . Vì thầy Hành ghét sự lặp lại, dãy của thầy có một tính chất đặc biệt: không có giá trị nào xuất hiện trong dãy quá mười lần.
Vì bài giảng hôm nay nói về thứ tự từ điển, thầy Hành lần lượt gọi sinh viên lên bảng. Mỗi sinh viên phải tạo một dãy số nguyên mới dựa trên dãy do sinh viên trước đó tạo ra (sinh viên đầu tiên dùng dãy của thầy Hành). Cụ thể, sinh viên thứ () phải tạo một dãy số nguyên thỏa mãn các điều kiện sau:
- là một hoán vị của ;
- lớn hơn theo thứ tự từ điển;
- là dãy nhỏ nhất theo thứ tự từ điển trong tất cả các dãy thỏa mãn hai điều kiện trên.
Cả sinh viên đều lên bảng và tìm ra dãy cần tìm chỉ trong vài giây, khiến thầy Hành bực mình. Có lẽ bạn đã biết, trong tiếng Việt, "hành" vừa là củ hành vừa là hành hạ. Vì vậy thầy Hành quyết định "hành" thêm một sinh viên nữa: thầy yêu cầu bạn ấy tính tổng số nghịch thế của cả dãy đang có trên bảng.
Bảng giờ đã kín số, cậu sinh viên kém may mắn nhanh chóng thấy chóng mặt. Bạn hãy giúp cậu ấy tìm kết quả.
Trong đề bài này:
- Dãy là một hoán vị của dãy khi và chỉ khi tồn tại số nguyên đôi một khác nhau sao cho và với mọi .
- Dãy nhỏ hơn dãy theo thứ tự từ điển khi và chỉ khi một trong hai điều sau xảy ra: là tiền tố của và ; hoặc tại vị trí đầu tiên mà và khác nhau, phần tử của nhỏ hơn phần tử tương ứng của .
- Một nghịch thế của dãy là một cặp số nguyên sao cho và .
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa hai số nguyên và (; ).
- Dòng thứ hai chứa số nguyên ().
Dữ liệu đảm bảo:
- Không có giá trị nào xuất hiện trong dãy quá mười lần.
- không vượt quá số hoán vị của lớn hơn theo thứ tự từ điển.
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên trên một dòng: tổng số nghịch thế của cả dãy đã được tạo ra.
Ràng buộc
- .
- , , .
- Mỗi giá trị xuất hiện trong dãy ban đầu không quá mười lần.
- không vượt quá số hoán vị lớn hơn dãy ban đầu theo thứ tự từ điển.
- Tổng không vượt quá , tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 7 2 5 6 2 1 3 7 4 6 1 2 2 1 3 3 1 |
31 12 |
Bộ dữ liệu thứ nhất: có nghịch thế, có nghịch thế, có nghịch thế; tổng là . Bộ dữ liệu thứ hai: có nghịch thế, có nghịch thế; tổng là . |
| 3 1 0 1 3 5 1 2 3 5 4 1 1 2 2 1 |
0 9 14 |
Ví dụ bổ sung (không có trong đề gốc). Bộ dữ liệu thứ hai đi qua cả sáu hoán vị của với số nghịch thế . Bộ dữ liệu thứ ba: , , , , có số nghịch thế . |
Bình luận