Hoán vị đặc biệt
Đề bài
Mô tả
Một mảng độ dài được gọi là một hoán vị nếu nó gồm số nguyên phân biệt từ đến theo thứ tự bất kỳ. Ví dụ, là một hoán vị, nhưng không phải hoán vị (số xuất hiện hai lần), và cũng không phải hoán vị ( nhưng mảng có số ).
Với một hoán vị , định nghĩa là số mảng con liên tiếp của là hoán vị. Ví dụ, với , các mảng con liên tiếp là hoán vị gồm:
- ,
- ,
- .
Do đó .
Một hoán vị độ dài được gọi là đặc biệt nếu lớn nhất trong số mọi hoán vị độ dài .
Cho và . Xét tất cả các hoán vị đặc biệt độ dài , hãy tìm hoán vị nhỏ thứ theo thứ tự từ điển.
Hoán vị nhỏ hơn hoán vị (cùng độ dài) theo thứ tự từ điển khi và chỉ khi ở 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 .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (): số bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên và (, ).
Dữ liệu đảm bảo:
- không vượt quá số hoán vị đặc biệt độ dài ;
- tổng trên tất cả các bộ test không vượt quá .
Dữ liệu ra
Với mỗi bộ test, in ra một dòng gồm số nguyên: hoán vị đặc biệt nhỏ thứ theo thứ tự từ điển.
Ràng buộc
- ,
- không vượt quá số hoán vị đặc biệt độ dài .
- Tổng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 4 2 |
2 1 3 4 | Với , các hoán vị nhỏ nhất theo thứ tự từ điển là với ; và với ; , , với ; rồi với . Giá trị lớn nhất của là , nên hoán vị đặc biệt thứ hai là . |
| 3 4 1 4 8 1 1 |
1 2 3 4 4 3 2 1 1 |
Với , hoán vị đặc biệt nhỏ nhất là và lớn nhất là . |
Bình luận