Baltic OI '02 P2 - Tennis Club

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types
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

1 \le G_i < N \le 1\,000

Input Specification

On the first line of input is the number of players N.

On the following N lines is the desired number of games to play G_i for each player. Assume that the players are numbered from 1 to N 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 N 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

There are no comments at the moment.