All submissions for this problem are available.
The new season of the Bytelandian Premier League (BPL) has started!
In the BPL, any two soccer teams play with each other exactly once. In each match, the winner earns 3 points and the loser earns no point. There is no draw (if the match is level after the two halves, two teams will take part in a penalty shootout to decide the winner).
At the end of the league, the winner is the team having the largest number of points. In case there are more than one team which has the largest number of points, these teams will be co-champions of the league.
The league has been running for some time. Now, the following problem has arisen: we would like to know if a specific team still has a chance of winning the league.
The first line contains T (about 20), the number of test cases. Then T test cases follow. Each test case has the following form.
The first line of the test case contains a number N (1 <= N <= 140), the number of teams in the league.
The i-th line in the next N lines contains N numbers ai1, ai2, ..., ain. The number aij gives the status of the match between the i-th team and the j-th team:
- aij = 1 if the i-th team wins,
- aij = 0 if the i-th team loses,
- aij = 2 if the match has not taken place yet.
The input data is such that if i!=j, then aij + aji = 1 or aij = aji = 2. Moreover, aii = 0 for all i.
For each test case, print a binary string of length N, in which the i-th character is 1 if the i-th team still has a chance to be a champion of the league, and 0 otherwise.
Input: 3 3 0 0 0 1 0 1 1 0 0 4 0 1 1 0 0 0 2 0 0 2 0 0 1 1 1 0 5 0 2 2 1 0 2 0 1 1 0 2 0 0 1 0 0 0 0 0 1 1 1 1 0 0 Output: 010 0001 11001
|Time Limit:||0.753968 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, C, C99 strict, CAML, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, GO, HASK, ICON, JAVA, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PHP, PIKE, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST|
Fetching successful submissions
If you are still having problems, see a sample solution here.