P

R

O

G

R

A

M

M

I

N

G

 

C

O

M

P

E

T

I

T

I

O

N

 

Double Knockout Competition

Task #12

Advanced

12 Points

Task Description
In a number of sports, a championship may be determined by a double knockout competition.  A team is eliminated on its second loss, so the winner is the last remaining team with one or fewer losses.  The competition is played in a series of rounds: in each round, teams that have not been eliminated are paired subject to the constraint that an undefeated team never plays a team with one loss.  As many teams as possible are paired in each round.  After a number of rounds only two teams remain.  These teams play in a round by themselves, although one is undefeated and the other is not.  If neither is eliminated, they play again in a final round.  For our analysis we assume that this extra round is always necessary.

Write a program to report on a Double Knockout Competition.

Program Input
The first line of the input file contains one positive integer n (which is the number of test cases that follow it). The next n lines each contain one positive integer t (where t < 32768), which is the number of teams in the competition for this test case.

5
2
6
32
64
512

Program Output
For each case print a summary of the competition to a file.  The summary must detail each round as follows:
Round 0: 2 undefeated, 0 one-loss, 0 eliminated, 0 games played

This is followed by a similar line for each round of the competition, followed by a single line saying how my rounds and the total number of games played. The output for each different test case is to be separated by a single blank line.

Number of Teams: 2
Round: 0, 2 undefeated, 0 one-loss, 0 eliminated, 0 games played
Round: 1, 1 undefeated, 1 one-loss, 0 eliminated, 1 games played
Round: 2, 0 undefeated, 2 one-loss, 0 eliminated, 1 games played
Round: 3, 0 undefeated, 1 one-loss, 1 eliminated, 1 games played
There are 3 rounds and a total of 3 games were played.

Number of Teams: 6
Round: 0, 6 undefeated, 0 one-loss, 0 eliminated, 0 games played
Round: 1, 3 undefeated, 3 one-loss, 0 eliminated, 3 games played
Round: 2, 2 undefeated, 3 one-loss, 1 eliminated, 2 games played
Round: 3, 1 undefeated, 3 one-loss, 2 eliminated, 2 games played
Round: 4, 1 undefeated, 2 one-loss, 3 eliminated, 1 games played
Round: 5, 1 undefeated, 1 one-loss, 4 eliminated, 1 games played
Round: 6, 0 undefeated, 2 one-loss, 4 eliminated, 1 games played
Round: 7, 0 undefeated, 1 one-loss, 5 eliminated, 1 games played
There are 7 rounds and a total of 11 games were played.

Number of Teams: 32
Round: 0, 32 undefeated, 0 one-loss, 0 eliminated, 0 games played
Round: 1, 16 undefeated, 16 one-loss, 0 eliminated, 16 games played
Round: 2, 8 undefeated, 16 one-loss, 8 eliminated, 16 games played
Round: 3, 4 undefeated, 12 one-loss, 16 eliminated, 12 games played
Round: 4, 2 undefeated, 8 one-loss, 22 eliminated, 8 games played
Round: 5, 1 undefeated, 5 one-loss, 26 eliminated, 5 games played
Round: 6, 1 undefeated, 3 one-loss, 28 eliminated, 2 games played
Round: 7, 1 undefeated, 2 one-loss, 29 eliminated, 1 games played
Round: 8, 1 undefeated, 1 one-loss, 30 eliminated, 1 games played
Round: 9, 0 undefeated, 2 one-loss, 30 eliminated, 1 games played
Round: 10, 0 undefeated, 1 one-loss, 31 eliminated, 1 games played
There are 10 rounds and a total of 63 games were played.

Number of Teams: 64
Round: 0, 64 undefeated, 0 one-loss, 0 eliminated, 0 games played
Round: 1, 32 undefeated, 32 one-loss, 0 eliminated, 32 games played
Round: 2, 16 undefeated, 32 one-loss, 16 eliminated, 32 games played
Round: 3, 8 undefeated, 24 one-loss, 32 eliminated, 24 games played
Round: 4, 4 undefeated, 16 one-loss, 44 eliminated, 16 games played
Round: 5, 2 undefeated, 10 one-loss, 52 eliminated, 10 games played
Round: 6, 1 undefeated, 6 one-loss, 57 eliminated, 6 games played
Round: 7, 1 undefeated, 3 one-loss, 60 eliminated, 3 games played
Round: 8, 1 undefeated, 2 one-loss, 61 eliminated, 1 games played
Round: 9, 1 undefeated, 1 one-loss, 62 eliminated, 1 games played
Round: 10, 0 undefeated, 2 one-loss, 62 eliminated, 1 games played
Round: 11, 0 undefeated, 1 one-loss, 63 eliminated, 1 games played
There are 11 rounds and a total of 127 games were played.

Number of Teams: 512
Round: 0, 512 undefeated, 0 one-loss, 0 eliminated, 0 games played
Round: 1, 256 undefeated, 256 one-loss, 0 eliminated, 256 games played
Round: 2, 128 undefeated, 256 one-loss, 128 eliminated, 256 games played
Round: 3, 64 undefeated, 192 one-loss, 256 eliminated, 192 games played
Round: 4, 32 undefeated, 128 one-loss, 352 eliminated, 128 games played
Round: 5, 16 undefeated, 80 one-loss, 416 eliminated, 80 games played
Round: 6, 8 undefeated, 48 one-loss, 456 eliminated, 48 games played
Round: 7, 4 undefeated, 28 one-loss, 480 eliminated, 28 games played
Round: 8, 2 undefeated, 16 one-loss, 494 eliminated, 16 games played
Round: 9, 1 undefeated, 9 one-loss, 502 eliminated, 9 games played
Round: 10, 1 undefeated, 5 one-loss, 506 eliminated, 4 games played
Round: 11, 1 undefeated, 3 one-loss, 508 eliminated, 2 games played
Round: 12, 1 undefeated, 2 one-loss, 509 eliminated, 1 games played
Round: 13, 1 undefeated, 1 one-loss, 510 eliminated, 1 games played
Round: 14, 0 undefeated, 2 one-loss, 510 eliminated, 1 games played
Round: 15, 0 undefeated, 1 one-loss, 511 eliminated, 1 games played
There are 15 rounds and a total of 1023 games were played.