Football Marathon
Time limit1sMemory limit128 MB
Simulate a huge round-robin elimination marathon with up to 10^14 matches and output each team's total match count, requiring cycle detection to skip the brute-force simulation.
- Level
Hard8 of 10
- Topics
- Simulation, Math, Implementation
- Solved
- No attempts yet
Problem
N teams are participating in a football marathon. Exactly K matches will be played, one match at a time.
The first match is between teams 1 and 2. After each match, the losing team leaves the field, while the winning team stays and plays the next team in order.
After team N has had its turn to enter, the order starts again from team 1. If the team whose turn it is to enter is already on the field as the current winner, or if that team has just lost and left the field, skip it and take the next team in the cyclic order.
The result of every possible match is known in advance. Whenever the same two teams play, the same team always wins.
For every team, determine the total number of matches it plays.
Input
The first line contains two integers N and K. (3 <= N <= 1000, 0 <= K <= 10^14)
Each of the next N lines contains a length-N string consisting only of 0 and 1. These strings describe the N x N win matrix A.
If Aij is 1, team i always defeats team j. If Aij is 0, team j always defeats team i. For every pair of different teams i and j, Aij and Aji are different.
Output
Print N integers on one line, separated by spaces. The i-th integer is the total number of matches played by team i.
The answers fit in a signed 64-bit integer type.