Đấu Trường Bitmask Tối Thượng
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Có $N$ chiến binh tham gia giải đấu. Giải đấu diễn ra theo từng vòng: mỗi vòng, bạn chọn đúng $2$ chiến binh còn lại để đấu, người thua bị loại. Kết quả đối đầu trực tiếp giữa mọi cặp chiến binh được cho trước dưới dạng ma trận thắng/thua.
Bạn được quyền sắp xếp thứ tự các trận đấu. Với mỗi chiến binh $i$, hãy xác định xem liệu tồn tại một cách sắp xếp các trận đấu sao cho chiến binh $i$ là người chiến thắng cuối cùng hay không.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- Tiếp theo là $N$ dòng, mỗi dòng chứa $N$ ký tự (
YhoặcN). Ký tự thứ $j$ trên dòng thứ $i$ làYnếu chiến binh $i$ thắng chiến binh $j$ khi đấu trực tiếp,Nnếu ngược lại. Đảm bảo rằng ma trận kết quả nhất quán (nếu $i$ thắng $j$ thì $j$ thua $i$ với $i \ne j$) và ô chéo chính làN.
Dữ liệu ra
- In ra một dòng gồm $N$ ký tự. Ký tự thứ $i$ là
1nếu chiến binh $i$ có thể là người chiến thắng, ngược lại là0.
Ví dụ
| Input | Output |
|---|---|
| 3 NYY NNY NNN |
100 |
Giới hạn
- $2 \le N \le 14$
Community Discussion