1138 - Bầy kiến xây tổ
Tạo bởi: CLB Olympic Tin học HUTECH
Mô tả yêu cầu
Ở một vùng đất xa xôi, có một bầy kiến đang xây tổ. Theo như bản thiết kế của kiến kĩ sư, các kiến thợ phải đào N - 1 đường hầm sao cho từ một khu vực có thể đi đến tất cả các khu vực còn lại. Mặt khác, theo phong thủy, mỗi khu vực u phải cách khu vực v xa nó nhất đúng bằng khoảng A_u. liệu có thể xây dựng được tổ đảm bảo những yêu cầu trên hay không? Bạn hãy giúp kiến kĩ sư kiểm tra nhé.
Dữ liệu vào
- Dòng đầu gồm một số nguyên dương N.
- Dòng tiếp theo, gồm N số A_u - khoảng cách giữa đỉnh u và đỉnh xa u nhất.
Dữ liệu ra
In ra Possible nếu tồn tại cách xây. Ngược lại, in ra Impossible.
Giới hạn
- 1 \leq N \leq 10^5
- 1 \leq A_i < N
Ví dụ
| Dữ liệu vào Sao chép |
5 3 2 2 3 3 |
| Dữ liệu ra Sao chép |
Possible |
| Dữ liệu vào Sao chép |
3 1 1 2 |
| Dữ liệu ra Sao chép |
Impossible |
Gợi ý/Hướng dẫn
Ở ví dụ 1:
Đăng nhập để làm bài