테니스 클럽
시간 제한1초메모리 제한128 MB
각 선수가 정한 경기 수를 차수로 갖는 단순 그래프가 존재하는지, 즉 에르되시-갈라이 정리 등을 이용해 유효한 대회 일정을 만들 수 있는지 판별합니다.
문제
Matchball 테니스 클럽에서 새 회원을 모집하기 위해 "게임 관심 주간(game interest week)"을 연다. 관심을 끌기 위해 스타 플레이어들이 시범 경기를 하는데, 각 플레이어는 자신이 치를 경기 수를 미리 정한다. 주최 측은 재미를 위해 어떤 두 플레이어도 서로 두 번 이상 맞붙지 않도록 대진표를 짜려고 한다.
다음 조건을 모두 만족하는 대진표를 만들 수 있는지 판별하는 프로그램을 작성하시오.
- 각 플레이어는 자신이 정한 횟수만큼 정확히 경기를 치른다.
- 같은 두 플레이어는 서로 최대 한 번만 맞붙는다.
- 어떤 플레이어도 자기 자신과는 경기할 수 없다.
입력
첫째 줄에 플레이어의 수 N이 주어진다. (2 ≤ N ≤ 1000)
다음 N개의 줄에는 각 플레이어가 치르기로 한 경기 수 Gi가 한 줄에 하나씩 주어진다. (1 ≤ Gi < N)
플레이어는 입력에 주어진 순서대로 1번부터 N번까지 번호가 매겨져 있다.
출력
위 조건을 모두 만족하는 대진표가 존재하면 첫째 줄에 SCHEDULE를, 존재하지 않으면 NO SCHEDULE를 출력한다.