Problem C
Shogi
Tournament
Input: standard input
Output: standard output
Time Limit: 25 seconds
Memory Limit: 32 MB
You are to compute, given a partially played Shogi tournament (Japanese chess), whether or not a particular player can still theoretically win the tournament and if so, the maximum number of points the player can be ahead of the player in second place. A tie is possible if two (or more) players get the same number of points; for this problem this is considered as a win with 0 points (no tiebreakers are used).
The tournament is a double round robin (everyone plays everyone else twice), and the only possible result in a game is either a win or a loss (draws very rarely occurs, and when they do, a new game is played to determine the winner). Any number of games may have been played so far in the tournament, and in any order.
Input
The input will contain several tournaments. The first line of the input contains an integer n (n ≤ 20) which is the number of tournament.
Each tournament description starts with a blank line followed by a line containing two integers m (2 ≤ m ≤ 50) and p (1 ≤ p ≤ m) describing the number of players in the tournament and for which player we want to determine if a win is possible.
Then follows m lines describing a cross table of the tournament, each line containing m entries. The entry on line y column x in the cross table contains the result in the two games played between player y and x. A '1' means that y won the game, '0' that y lost the game and '-' that the game has not yet been played. Of course, since a player doesn't play against himself, the elements in the diagonal are always '--'.
You may assume that the cross table is "complete" in the sense that if player y won his first game against player x, the opposite result can be found for player x in his first game against player y.
Output
If the player can't win the tournament, output only "Player p can't win!".
Otherwise output "Player p can with d point(s)." where d is the maximum amount of points ahead of second place player p can get. You should also assign results to all remaining games in the tournament so this is achieved, and print out a cross table with these results. The cross table should have the same format as the input, except that you should also print the final score for each player, see the sample output for the exact format. There should be a blank line before each cross table.
Separate each tournament in the output with a blank line.
Sample Input
3 2 2-- -1-0 -- 4 1-- -0 0- 0--1 -- 11 --1- 00 -- -01- -- -1 -- 3 2-- -- ---- -- ---- -- --
Sample Output
Player 2 can win with 0 point(s). -- 01 : 110 -- : 1 Player 1 can't win! Player 2 can win with 3 point(s). -- 00 10 : 111 -- 11 : 401 00 -- : 1