Baltic Olympiad in Informatics: 2002 Day 1, Problem 2
The Matchball tennis club is organizing a "game interest week" to attract new players to the club. As one of the attractions, they have asked some star players to play a few demo games. Each star has indicated the number of games he or she is willing to play. The organizers want the stars to have some fun as well, thus they want to schedule the games so that no two players meet more than once with each other.
Your task is to write a program to help them match the players into pairs so that each player plays his or her desired number of games and does not play twice or more against any other player. Of course, no player may play against himself or herself.
Constraints
Input Specification
On the first line of input is the number of players .
On the following lines is the desired number of games to play for each player. Assume that the players are numbered from to in the order of their wishes.
Output Specification
On the first line of output write NO SCHEDULE
if it is not possible to create a schedule so that the wishes of all players are satisfied, or SCHEDULE
if it is possible.
If a schedule exists, write it out on the following lines. On each line, write the indices of opponents for the player whose desired number of games was indicated on the corresponding input line. On each line, the indices should be by spaces.
If multiple solutions exist, output any one of them.
Sample Input 1
3
1
2
1
Sample Output 1
SCHEDULE
2
1 3
2
Sample Input 2
3
2
2
1
Sample Output 2
NO SCHEDULE
Comments