LSFIGHT - Đấu trường VM08
Giới hạn- Thời gian: 0.6s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Trong kỳ thi Marathon 08 năm nay các vCoders phải tham gia một môn thi đấu đối kháng giữa 2 người. Sau vòng loại, ban tổ chức sẽ chọn ra N thí sinh có số điểm cao nhất và đánh số từ 1 đến N. Các thí sinh này phải xếp lần lượt theo thứ tự thành 1 vòng tròn (người thứ N đứng cạnh người thứ 1). Sau đó sẽ chọn ra 2 thí sinh bất kì đang đứng cạnh nhau trong vòng tròn để thi đấu, thí sinh nào thua sẽ bị loại và buộc phải đi ra vòng tròn, trở về hàng ghế khán giả. Cuộc đấu cứ tiếp tục như thế đến khi chỉ còn một người ở lại và cũng chính là người thắng cuộc.
Tuy nhiên ban tổ chức muốn biết trước xem có bao nhiêu người có khả năng thắng cuộc và đó là những người nào. Biết trước ai sẽ thắng trong mỗi trận đấu, bạn hãy giúp ban tổ chức nhé ^^
Dữ liệu
- Dòng đầu là số nguyên dương N (3 <= N <= 500)
- N dòng sau là ma trận A[i, j], A[i, j] = 0 nếu thí sinh i thua thí sinh j và A[i, j] = 1 nếu ngược lại. Biết rằng luôn đảm bảo A[i, i]=1 với mọi i và A[i, j] + A[j, i] = 1 với i <> j. Các số viết cách nhau ít nhất 1 dấu cách.
Kết quả
- Dòng đầu là số nguyên dương M - số lượng thí sinh có khả năng thắng cuộc
- M dòng sau mỗi dòng ghi một số là chỉ số của thí sinh có khả năng thắng cuộc theo thứ tự tăng dần của chỉ số.
Ví dụ
Dữ liệu 7 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 0 1 Kết quả 3 1 3 6
- Người up: tikiupi
- Nguồn bài: VNOI Marathon '08 - Round 9/DivBProblem Setter: Tô Quang PhúcOrigin:POI6