Schedule of Taiwan Baseball League
Taiwan baseball league and the sport division of the ministry of education of Taiwan are planning to organize a major event with world baseball championship. After several rounds of discussions among the members of the organizing committee, the details of the game plan are as follows.
- There will be N teams invited to the competition, and N will be a power of 2. (N will also be less than or equal to 128 and, of course, greater than 2.)
- A round-robin competition and game schedule will be used. It means every team will play every other team exactly once.
- Two cities will collectively host the games. Kaohsiung and Taipei will be the two cities to host the game, and Taipei Baseball Stadium and Kaohsiung Baseball Stadium (Lee-Der Stadium) will be used as the game fields.
Please write a program to produce a schedule for the games. The schedule needs to satisfy the following criteria.
a) The game schedule is round-robin. Suppose there are N teams to participate in the competition, you need to schedule games to be played in exactly N − 1 days. In each day of the competition, every team will have to play exactly one game.
b) The games have to be scheduled evenly between Taipei and Kaohsiung. There will be equal number of games to be played each day between Taipei and Kaohsiung in your produced schedule.
c) The organizing committee also hopes to reduce the total number of travellings for the teams. Therefore, your schedule has to be the one with the minimum travellings for teams to travel between Taipei and Kaohsiung. For example, if a team plays in Taipei in Day 1, and then the same team plays in Kaohsiung in Day 2, we say that the travelling total is one. Your goal is to produce a schedule so that the total travelling combined with all the teams is the minimum. The fairness with the amount of travellings for each team is not required by the organizing committee. We assume no travelling accounts in the first day of the game. The travelling total will be counted from day 2 of the games.
Input
The input file is formated as follows
K N1 N2 ... Nk
where K is the number of testing data. Ni, i = 1, . . . , K, are the total number of teams invited for the competitions.
2/2 Output
For each testing case Ni, you must report a schedule of travellings for the all the teams. The amount of travellings has to be minimum to be able to be correct. Format your output as shown in the sample below. In case no teams have to travel between two consecutive days, print ‘No teams travelling between day n and day n+1.’
The order in the report has to follow the input order with each testing case. Print a blank line between cases.
Sample Input
1 8
Sample Output
Day 1:
Taipei: (1-2) (3-4).
Kaohsiung: (5-6) (7-8).
No teams travelling between day 1 and day 2.
Day 2:
Taipei: (1-3) (2-4).
Kaohsiung: (5-7) (6-8).
No teams travelling between day 2 and day 3.
Day 3:
Taipei: (1-4) (2-3).
Kaohsiung: (5-8) (6-7).
Teams travelling between day 3 and day 4: 3,5,4,6.
Day 4:
Taipei: (1-5) (2-6).
Kaohsiung: (3-7) (4-8).
No teams travelling between day 4 and day 5.
Day 5:
Taipei: (1-6) (2-5).
Kaohsiung: (3-8) (4-7).
Teams travelling between day 5 and day 6: 5,7,6,8.
Day 6:
Taipei: (1-7) (2-8).
Kaohsiung: (3-5) (4-6).
No teams travelling between day 6 and day 7.
Day 7:
Taipei: (1-8) (2-7).
Kaohsiung: (3-6) (4-5).
Total number of travels: 8