3661번 - 생일 선물 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 183 | 76 | 67 | 46.528% |
문제
오늘은 선영이의 생일이다. 선영이의 친구들은 선영이에게 생일선물로 스타크래프트 2를 사주기로 했다.
선영이의 친구들은 비용을 공정하게 내기로 결정했다. 친구들 중 일부는 다른 친구들보다 돈이 많기 때문에, 각자 낼 수 있는 금액보다 더 많은 금액은 내지 않기로 했다. 모든 사람이 내는 돈은 1원의 배수이다. 즉, 분수로 낼 수는 없다.
친구들은 자신이 낼 수 있는 최대 금액을 적어서 냈다. 이제 이 정보를 이용해서 각자 낼 금액이 얼마인지 계산해보려고 한다.
공정하게 선물 비용을 내려면, 선물 금액의 1/n과 각 사람이 낸 금액의 차이의 최댓값을 최소로 해야 한다. 만약, 같은 경우가 나오는 경우에는 두 번째 차이의 최댓값을 최소로 해야 하고, 이런 식이다. 각 사람이 낼 수 있는 최소 금액은 1원이기 때문에, 금액을 분배하는 방법이 여러 가지가 나올 수 있다. 이 경우에는 돈을 많이 낼 수 있는 사람이 더 내게 된다. 그래도 여러 가지라면, 리스트의 앞에 있는 사람이 돈을 더 낸다.
선영이의 친구들이 낼 수 있는 금액과 선물의 금액이 주어졌을 때, 각자 얼마를 내야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.
각 테스트 케이스의 첫째 줄에는 선물의 가격 p (1 ≤ p ≤ 1,000,000)와 선영이 친구의 수 n (2 ≤ n ≤ 100) 이 주어진다. 둘째 줄에는 각 사람이 낼 수 있는 금액 ai (1 ≤ ai ≤ 1,000,000) 가 주어진다.
출력
각 테스트 케이스마다 각 사람이 내야 하는 금액을 출력한다. 만약, 공정하게 선물을 사는 방법이 없다면 IMPOSSIBLE을 출력한다.
예제 입력 1
3 20 4 10 10 4 4 7 3 1 1 4 34 5 9 8 9 9 4
예제 출력 1
6 6 4 4 IMPOSSIBLE 8 7 8 7 4
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 A번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호