Problem G
Bangladesh Premier League
Input: Standard Input

Output: Standard Output

So, here comes another cricket tournament – Bangladesh Premier League aka BPL. In this tournament, N teams play against each other in a round-robin league fashion for a total of R rounds. Team with highest number of wins is announced the winner of the tournament. If there are multiple teams with highest number of wins, then all of them are winners. Now, we are in the middle of a tournament and would like to determine which of the teams are mathematically out of the league race. In other words, we would like to determine which teams cannot win the tournament even if they win all of their remaining matches.

You are given the current league table of the tournament. For example, let’s say there 4 teams in the tournament – Dhaka, Chittagong, Rajshahi and Khulna. A sample table can be like this –

Team Wins Loss Left Dhk Ctg Raj Khl

-----------------------------------------------------------------------------------------

Dhaka 6 7 5 0 0 0 5

Chittagong 10 4 4 0 0 4 0

Rajshahi 10 4 4 0 4 0 0

Khulna 1 12 5 5 0 0 0

From the table, you can see that Khulna is definitely not in the league race. They have won 1 match and can only win 5 more which would be insufficient to pass Chittagong or Rajshahi. On the other hand, Dhaka is also eliminated though it may not be evident from the table. Dhaka has won 6 matches and can win 5 more making a total of 11. Now Chittagong and Rajshahi have won a total of 10+10 = 20 matches and they will play each other 4 more times. So, on the average, they will win (20+4) / 2 = 12 matches. So, one team would definitely win more than 11 matches thereby eliminating Dhaka.

Input

Input will consist of less than 30 test cases. First line of each test case will contain no of teams in the tournament, N (1<N<51). Then there will be a table in the format mentioned above except for the headers. It will consist of N rows and N+4 columns. Each row will represent a team. Team names don’t have any spaces in them and they will be at most 30 characters in length. Last N columns of the table constitute the ‘Remaining Game Matrix’ which is symmetrical and its diagonal entries are always zero. No. of rounds, R (0<R<31) will not be explicitly mentioned in the statement. The last test case will be followed by a -1 in a line by itself, denoting the end of input file.

Output

For each test case, you should print “Case C:” in the first line where C is replaced by the case number starting from 1. Then, for each team eliminated, you should output a block of 5 lines which should be in the following format –

Team X is eliminated.

They can win at most a + b = c games.

T₁, T₂, … and T_n have won a total of G games.

They play each other M times.

So, on average, each of the teams wins (G+M)/n = p games which is greater than c.

Here,

X is the name of the team which is eliminated.

a, b and c are the no. of games team X has already won, no. of remaining games and their total wins optimistically respectively.

T₁, T₂, … and T_n are the n team names you think will mathematically beat team X as a combination. G is their total match won already. There will be M matches between these n teams.

Print a blank line after each such block. Print an extra blank line after each test case.

If there are multiple groups that satisfy the condition, you can output any one. Also you can output teams in any order. Output will be checked by a special judge program. For floating point number (only p), you can print any number of digits after the decimal point provided it does not differ by more than 1E-6 from the original value.

Sample Input Output for Sample Input

4 A 6 7 5 0 0 0 5 B 10 4 4 0 0 4 0 C 10 4 4 0 4 0 0 D 1 12 5 5 0 0 0 2 A 1 1 1 0 1 B 1 1 1 1 0 -1

Case 1: Team A is eliminated. They can win at most 6 + 5 = 11 games. B and C have won a total of 20 games. They play each other 4 times. So, on average, each of the teams wins (20+4)/2 = 12.000000 games which is greater than 11. Team D is eliminated. They can win at most 1 + 5 = 6 games. B have won a total of 10 games. They play each other 0 times. So, on average, each of the teams wins (10+0)/1 = 10.000000 games which is greater than 6. Case 2: [the line above is blank]

Note: Though the output blocks are supposed to be of 5 lines, you see in the sample output to span them to 7 lines which is due to formatting in word. You should output in 5 lines on your output.