Xây dựng hoán vị
Đề bài
Mô tả
Cho ba số nguyên , , . Hãy xác định xem có tồn tại một hoán vị của các số nguyên từ đến thỏa mãn đồng thời hai điều kiện sau hay không:
- Có đúng chỉ số với sao cho (nói cách khác, có đúng cực đại địa phương).
- Có đúng chỉ số với sao cho (nói cách khác, có đúng cực tiểu địa phương).
Lưu ý rằng hai vị trí đầu mút và không bao giờ được tính là cực trị địa phương.
Nếu tồn tại hoán vị như vậy, hãy in ra một hoán vị bất kỳ thỏa mãn.
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên () là số lượng bộ dữ liệu.
- Mỗi bộ dữ liệu gồm một dòng chứa ba số nguyên , , (, ).
Tổng trên 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:
- Nếu không tồn tại hoán vị thỏa mãn, in ra .
- Ngược lại, in ra số nguyên là một hoán vị thỏa mãn. Nếu có nhiều đáp án, in ra đáp án bất kỳ.
Ràng buộc
- Tổng trên tất cả các bộ dữ liệu không vượt quá
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 1 1 6 1 2 6 4 0 |
1 4 2 3 6 1 5 2 3 4 -1 |
Bộ 1: với hoán vị ta có nên là cực đại, và nên là cực tiểu; đúng , . Bộ 2: có cực đại tại , cực tiểu tại và . Bộ 3: cần cực đại nhưng cực tiểu, không thể vì hai loại cực trị luôn xen kẽ nhau. |
| 4 2 0 0 3 1 0 5 1 1 5 3 0 |
1 2 1 3 2 1 5 2 3 4 -1 |
Bộ 1: không có vị trí trong nên bắt buộc . Bộ 2: có duy nhất cực đại tại . Bộ 3: có cực đại tại , cực tiểu tại . Bộ 4: nên vô nghiệm. |
Bình luận