2926번 - 비례대표 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 15 | 3 | 3 | 100.000% |
문제
오늘은 국회의원을 뽑는 날이다.
총 V명이 투표를 했으며, 각 사람은 정당 N개 중 하나에 표를 던졌다. 이 중 M명이 국회에 진출하게 된다.
D'Hondt 방법을 이용해 의석 배정을 하며, 한계치는 5%이다. 각 정당은 1번부터 N번까지 번호가 매겨져 있고, 받은 표의 개수는 V1, V2, ..., VN이다. 의석 배정은 다음과 같이 이루어진다.
- 총득표수(V)의 5%보다 표를 적게 받은 정당은 정당 목록에서 지운다.
- 처음에 모든 정당에 할당된 의석은 0이다.
- 각각의 정당 P에 대해서, 몫 QP = VP/(SP+1)을 구한다. VP는 정당 P가 받은 표의 개수이고, SP는 그때 까지 정당 P에 할당된 의석의 수이다.
- 가장 큰 QP를 갖는 정당이 의석 하나를 갖게 된다. 그런 경우가 여러개라면 번호가 가장 작은 정당이 의석을 하나 갖게 된다.
- 모든 의석이 할당될 때 까지 3번과 4번을 반복한다.
현재 개표가 진행중이며, 일부만 개표된 상황이다. 각 정당의 득표수는 모두 알려져 있다.
일부만 개표된 결과가 주어졌을 때, 각 정당이 받을 수 있는 최대 의석 수와 최소 의석 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 V, N, M이 주어진다. (1 ≤ V ≤ 10,000,000, 1 ≤ N ≤ 100, 1 ≤ M ≤ 200)
둘째 줄에 각 정당이 받은 표의 수가 주어진다. 합은 V를 넘지 않는다.
출력
첫째 줄에 각 정당의 가능한 최대 의석 수, 둘째 줄에 최소 의석 수를 출력한다.
예제 입력 1
20 4 5 4 3 6 1
예제 출력 1
3 3 3 2 1 0 1 0
예제 입력 2
100 3 5 30 20 10
예제 출력 2
4 3 3 1 1 0
힌트
첫 번째 예제에서 개표된 표의 수는 14, 미개표된 표의 수는 6이다. 예를 들어, 개표된 결과가 첫 번째 정당이 2표, 두 번째 정당이 0표, 세 번째 정당이 1표, 네 번째 정당이 3표인 결과를 생각해보자. 각 정당이 받은 표의 수는 6, 3, 7, 4이다. 모든 정당이 총득표수의 5%를 넘었다. 의석은 다음과 같이 배정된다.
- 첫 번째 몫을 구해보면 6/1, 3/1, 7/1, 4/1이다. 정당 3(7/1)이 의석을 하나 가져간다.
- 몫은 6/1, 3/1, 7/2, 4/1이다. 정당 1(6/1)이 의석을 하나 가져간다.
- 몫은 6/2, 3/1, 7/2, 4/1이다. 정당 4(4/1)가 의석을 하나 가져간다.
- 몫은 6/2, 3/1, 7/2, 4/2이다. 정당 3(7/2)이 의석을 하나 가져간다.
- 몫은 6/2, 3/1, 7/3, 4/2이다. 정당 1과 2의 몫이 6/2, 3/1로 같다. 정당 번호가 작은 1이 마지막 의석을 가져간다.
각 정당의 의석수는 2, 0, 2, 1이 된다. 정당 2가 의석을 하나도 못 받는 경우가 존재한다. 따라서, 둘째 줄의 두 번째 숫자는 0이다.
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > Croatian Olympiad in Informatics 2009 1번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호