Điện tâm đồ

Đề bài

Mô tả

n người xếp hàng chờ khám, đánh số từ 1 đến 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ứ i cho biết số ai: nếu ai0 thì người ai đứng ngay trước người i trong hàng; nếu ai=0 thì người i không biết ai đứng ngay trước mình.

Dữ liệu đảm bảo các giá trị ai 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ả n 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ứ x trong hàng.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên nx: số người trong hàng và số hiệu của người cần xét.
  • Dòng thứ hai chứa n số nguyên a1,a2,,an.

Dữ liệu ra

In ra tất cả các vị trí có thể của người thứ x theo thứ tự tăng dần, mỗi vị trí trên một dòng.

Ràng buộc

  • 1n103
  • 1xn
  • 0ain
  • Số lượng phần tử ai bằng 0 không vượt quá 20.

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 2 đứng thứ hai trong đoạn của mình, nên vị trí của họ là 2 nếu đoạn của họ xếp trước, hoặc 2+3=5 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 2 đứ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 0,2,3,5.
4 1
0 0 0 0
1
2
3
4
Không ai biết gì, nên người 1 có thể đứng ở bất kỳ vị trí nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0