Lịch thi đấu bóng đá

View as PDF

Submit solution

Points: 0.59 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Thầy Nguyễn Thanh Hùng - PTNK
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một giải thi đấu bóng đá được tổ chức theo thể thức thi đấu vòng tròn, ở đó hai đội bóng bất kỳ sẽ được thi đấu với nhau đúng một trận.

Trong mỗi trận đấu, đội thắng được ~3~ điểm, còn đội thua được ~0~ điểm. Không có kết quả hòa (nếu hòa trong hai hiệp chính thì hai đội sẽ phải thi đấu luân lưu để phân định thắng thua).

Kết thúc mùa giải, đội vô địch là đội có số điểm cao nhất. Trong trường hợp có nhiều hơn một đội được điểm cao nhất thì các đội này đồng đoạt chức vô địch.

Giải đã diễn ra được một thời gian. Lúc này một bài toán nảy sinh: người ta cần biết mỗi đội bóng còn có khả năng đoạt chức vô địch nữa hay không?

Yêu cầu: Biết kết quả các trận đấu đã diễn ra, bạn hãy cho biết mỗi đội bóng còn có khả năng đoạt chức vô địch mùa giải nữa hay không?

Input

  • Dòng ~1~: chứa số nguyên dương ~N~ là số đội bóng tham gia giải đấu. Các đội bóng được đánh số thứ tự từ ~1~ đến ~N~.

  • ~N~ dòng tiếp theo, dòng ~i~ chứa ~N~ số nguyên dương ~a_{i1}, a_{i2}, \ldots, a_{iN}~, trong đó ~a_{ij}~ cho biết trạng thái của trận đấu giữa đội ~i~ và đội ~j~:

    • ~a_{ij} = 0~ nếu đội ~j~ thắng.
    • ~a_{ij} = 1~ nếu đội ~i~ thắng.
    • ~a_{ij} = 2~ nếu trận đấu chưa diễn ra.
    • Nếu ~i \ne j~, dữ liệu vào đảm bảo ~a_{ij} = a_{ji} = 2~ hoặc ~a_{ij} + a_{ji} = 1~. Dữ liệu vào đảm bảo ~a_{ii} = 0~ với mọi ~i~.

Output

  • Gồm ~1~ dòng duy nhất, là một dãy nhị phân độ dài ~N~, ở đó bit thứ ~i~ bằng ~1~ nếu đội bóng ~i~ còn khả năng vô địch mùa giải, và bằng ~0~ nếu đội bóng ~i~ không còn khả năng vô địch mùa giải.

Giới hạn

  • ~N~ là số nguyên dương trong phạm vi ~\left[1, 30\right]~

Sample Input

5
0 2 0 2 1
2 0 0 1 0
1 1 0 2 1
2 0 2 0 2
0 1 0 2 0

Sample Output

10110

Comments

Please read the guidelines before commenting.


There are no comments at the moment.