Tennis Club

Time limit1sMemory limit128 MB

Summary
Given each player's required match count, decide if a simple graph (no self loops, no repeated edges) with that exact degree sequence exists, typically via the Erdős–Gallai theorem.
Level

Medium6 of 10

Topics
Greedy, Math, Combinatorics
Solved
No attempts yet

Problem

The Matchball tennis club is holding a "game interest week" to recruit new members. To draw attention, its star players play exhibition matches, and each player decides in advance how many matches they will play. For variety, the organizers want to build a schedule in which no two players ever meet more than once.

Write a program that decides whether a schedule satisfying all of the following conditions can be built.

  • Each player plays exactly the number of matches they chose.
  • Any two players meet at most once.
  • No player can play against themselves.

Input

The first line contains the number of players N (2 ≤ N ≤ 1000).

Each of the next N lines contains one integer Gi, the number of matches player i has decided to play (1 ≤ Gi < N).

Players are numbered from 1 to N in the order given in the input.

Output

Print SCHEDULE on the first line if a schedule satisfying all of the conditions above exists, or NO SCHEDULE if it does not.

Examples2

  1. Example 1

    Input
    3
1
2
1
    Expected output
    SCHEDULE

  2. Example 2

    Input
    3
2
2
1
    Expected output
    NO SCHEDULE