시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 256 MB | 38 | 4 | 3 | 60.000% |
친구들과 즐거운 저녁 식사를 마친 상근이는 각 사람이 돈을 얼마나 내야하는지 계산을 하려고 한다.
이 레스토랑은 카드 결제가 되지 않기 때문에 현금으로 계산해야 한다. 또, 레스토랑은 잔돈을 거슬러주지 않는다.
각 사람이 가지고 있는 현금 정보가 주어졌을 때, 사람들끼리 돈을 적절히 교환해 모든 사람이 정확하게 자기가 내야할 돈을 낼 수 있을까?
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 식사를 한 사람의 수 N이 주어진다. 다음 N개 줄에는 아래와 같은 정보가 주어진다.
xi ci,1 ci,5 ci,10 ci,25 ci,100 ci,500 ci,1000 ci,2000 ci,5000 ci,10000
xi는 i번 사람이 내야하는 돈을 나타내고, ci,v는 i번 사람이 가지고있는 v원 동전 또는 지폐의 개수이다. 예를 들어, 1번 사람은 1원 동전을 c1,1개, 5원 동전을 c1,5개 가지고 있다.
입력의 마지막 줄에는 0이 하나 주어진다.
모든 사람은 항상 음식값을 낼 수 있으며, 모든 사람이 가지고 있는 돈의 양은 부호있는 32비트 정수 범위 이내이다. 또한, N ≤ 100000이다.
각 테스트 케이스마다 "Case #:"형태로 케이스 번호를 출력하고, 공백을 한 칸 출력한 다음, YES (모든 사람이 돈을 낼 수 있는 경우) 또는 NO (그 외의 경우) 를 출력한다.
1 10 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 500 0 0 0 0 0 1 0 0 0 0 1 100 4 0 2 3 0 1 0 0 0 0 0
Case 1: YES Case 2: YES Case 3: NO
University > The MIT Programming Contest > 2008-09 > MIT Programming Contest Individual Round 2008 7번