Điện tâm đồ
Đề bài
Mô tả
Có người xếp hàng chờ khám, đánh số từ đến . Hàng đợi rất lộn xộn nên không phải ai cũng nhớ mình đứng sau ai.
Người thứ cho biết số : nếu thì người đứng ngay trước người trong hàng; nếu thì người không biết ai đứng ngay trước mình.
Dữ liệu đảm bảo các giá trị hợp lệ: không có chu trình trong quan hệ "đứng ngay trước", và mỗi người có nhiều nhất một người đứng ngay sau mình.
Hàng đợi thực tế là một cách xếp cả người thành một dãy thỏa mãn mọi thông tin đã biết. Hãy tìm tất cả các vị trí có thể của người thứ trong hàng.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên và : số người trong hàng và số hiệu của người cần xét.
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
In ra tất cả các vị trí có thể của người thứ theo thứ tự tăng dần, mỗi vị trí trên một dòng.
Ràng buộc
- Số lượng phần tử bằng không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 6 2 2 3 0 5 6 0 |
2 5 |
Hai đoạn xác định là 3-2-1 và 6-5-4. Người đứng thứ hai trong đoạn của mình, nên vị trí của họ là nếu đoạn của họ xếp trước, hoặc nếu đoạn 6-5-4 xếp trước. |
| 6 2 0 0 1 0 4 5 |
1 3 4 6 |
Ba đoạn: 1-3, 2, 4-5-6. Người đứng đầu đoạn của mình, phía trước là một tập con bất kỳ của hai đoạn còn lại, cho tổng độ dài . |
| 4 1 0 0 0 0 |
1 2 3 4 |
Không ai biết gì, nên người có thể đứng ở bất kỳ vị trí nào. |
Bình luận