Nghịch thế
Đề bài
Mô tả
Hoán vị là một chủ đề quan trọng và thú vị trong toán học. Một trong những khái niệm nổi tiếng nhất liên quan đến hoán vị là nghịch thế.
Nhắc lại, dãy số nguyên được gọi là một hoán vị của các số nguyên khi và chỉ khi:
- Với mọi , .
- Với mọi , .
Một nghịch thế của hoán vị là một cặp sao cho và .
Trong bài toán này, có một hoán vị bí mật của các số nguyên . Bạn được cho một mảng hai chiều , trong đó bằng số nghịch thế của nếu ta đổi chỗ và . Nhiệm vụ của bạn là tìm hoán vị bí mật này.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên (), độ dài của hoán vị.
- Dòng thứ trong dòng tiếp theo chứa số nguyên ().
Dữ liệu vào đảm bảo có ít nhất một hoán vị bí mật hợp lệ.
Dữ liệu ra
In ra một dòng gồm số nguyên là hoán vị bí mật. Nếu có nhiều hoán vị thỏa mãn, in ra một hoán vị bất kỳ.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0 1 1 0 |
1 2 | Hoán vị không có nghịch thế; đổi chỗ hai phần tử được có nghịch thế. |
| 3 2 3 1 3 2 1 1 1 2 |
2 3 1 | Hoán vị có nghịch thế. Ví dụ, đổi chỗ và được có nghịch thế, nên . |
Bình luận