Ánh xạ hoán vị
Đề bài
Mô tả
Trong một vũ trụ được nối với nhau bằng các đường hầm vũ trụ, hệ thống Ống Liên Sao Tương Lai (FIT) chào đón các nhà thám hiểm du hành giữa các hành tinh. Để lên đường, mỗi người phải giải các thử thách về hoán vị của các số nguyên dương.
Xét tập các hoán vị của số nguyên dương có các tính chất sau:
- Dãy tăng dần.
- Dãy tăng dần.
- Với mọi (): .
Tất cả các hoán vị này được sắp xếp theo thứ tự từ điển và đánh số liên tiếp bắt đầu từ . Như vậy mỗi hoán vị có một số thứ tự, gọi là chỉ số của hoán vị.
Ví dụ, với có tất cả hoán vị, sau khi sắp xếp chúng được đánh số như sau:
| Chỉ số | Hoán vị |
|---|---|
| 1 | 1 2 3 4 5 6 |
| 2 | 1 2 4 3 5 6 |
| 3 | 1 2 5 3 4 6 |
| 4 | 1 3 4 2 5 6 |
| 5 | 1 3 5 2 4 6 |
Cho số , bạn cần giải hai bài toán sau:
- Cho chỉ số , tìm hoán vị có chỉ số .
- Cho hoán vị , tìm chỉ số của hoán vị này.
Dữ liệu vào
Dữ liệu vào gồm không quá bộ test, mỗi bộ test nằm trên một dòng, bắt đầu bằng số hoặc cho biết bài toán cần giải:
- Nếu số đầu tiên là , tiếp theo là hai số nguyên và .
- Nếu số đầu tiên là , tiếp theo là số nguyên và số nguyên .
Dữ liệu vào đảm bảo đúng và lời giải luôn tồn tại: không vượt quá số hoán vị có tính chất trên, và hoán vị cho trong bài toán có đủ các tính chất trên.
Dữ liệu ra
In ra kết quả của từng bộ test theo thứ tự trong dữ liệu vào, mỗi kết quả trên một dòng: với bài toán in ra số của hoán vị, với bài toán in ra chỉ số của hoán vị. Lưu ý chỉ số có thể rất lớn và phải được in ra chính xác.
Ràng buộc
- Không quá bộ test.
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 3 4 2 3 1 3 5 2 4 6 1 4 2 2 4 1 2 3 6 4 5 7 8 |
1 3 4 2 5 6 5 1 2 3 5 4 6 7 8 3 |
Hai bộ test đầu ứng với bảng ở trên. Với , ba hoán vị đầu tiên là 1 2 3 4 5 6 7 8, 1 2 3 5 4 6 7 8 và 1 2 3 6 4 5 7 8. |
| 1 1 1 2 1 1 2 |
1 2 1 |
Với chỉ có một hoán vị là 1 2. |
Bình luận