시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 8 1 1 100.000%

문제

오늘은 국회의원을 뽑는 날이다.

총 V명이 투표를 했으며, 각 사람은 정당 N개 중 하나에 표를 던졌다. 이 중 M명이 국회에 진출하게 된다.

D'Hondt 방법을 이용해 의석 배정을 하며, 한계치는 5%이다. 각 정당은 1번부터 N번까지 번호가 매겨져 있고, 받은 표의 개수는 V1, V2, ..., VN이다. 의석 배정은 다음과 같이 이루어진다.

  1. 총득표수(V)의 5%보다 표를 적게 받은 정당은 정당 목록에서 지운다.
  2. 처음에 모든 정당에 할당된 의석은 0이다.
  3. 각각의 정당 P에 대해서, 몫 QP = VP/(SP+1)을 구한다. VP는 정당 P가 받은 표의 개수이고, SP는 그때 까지 정당 P에 할당된 의석의 수이다.
  4. 가장 큰 QP를 갖는 정당이 의석 하나를 갖게 된다. 그런 경우가 여러개라면 번호가 가장 작은 정당이 의석을 하나 갖게 된다.
  5. 모든 의석이 할당될 때 까지 3번과 4번을 반복한다.

현재 개표가 진행중이며, 일부만 개표된 상황이다. 각 정당의 득표수는 모두 알려져 있다. 

일부만 개표된 결과가 주어졌을 때, 각 정당이 받을 수 있는 최대 의석 수와 최소 의석 수를 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 V, N, M이 주어진다. (1 ≤ V ≤ 10,000,000, 1 ≤ N ≤ 100, 1 ≤ M ≤ 200)

둘째 줄에 각 정당이 받은 표의 수가 주어진다. 합은 V를 넘지 않는다. 

출력

첫째 줄에 각 정당의 가능한 최대 의석 수, 둘째 줄에 최소 의석 수를 출력한다.

예제 입력

20 4 5
4 3 6 1

예제 출력

3 3 3 2
1 0 1 0

힌트

개표된 표의 수는 14, 미개표된 표의 수는 6이다. 예를 들어, 개표된 결과가 첫 번째 정당이 2표, 두 번째 정당이 0표, 세 번째 정당이 1표, 네 번째 정당이 3표인 결과를 생각해보자. 각 정당이 받은 표의 수는 6, 3, 7, 4이다. 모든 정당이 총득표수의 5%를 넘었다. 의석은 다음과 같이 배정된다.

  1. 첫 번째 몫을 구해보면 6/1, 3/1, 7/1, 4/1이다. 정당 3(7/1)이 의석을 하나 가져간다.
  2. 몫은 6/1, 3/1, 7/2, 4/1이다. 정당 1(6/1)이 의석을 하나 가져간다.
  3. 몫은 6/2, 3/1, 7/2, 4/1이다. 정당 4(4/1)가 의석을 하나 가져간다.
  4. 몫은 6/2, 3/1, 7/2, 4/2이다. 정당 3(7/2)이 의석을 하나 가져간다.
  5. 몫은 6/2, 3/1, 7/3, 4/2이다. 정당 1과 2의 몫이 6/2, 3/1로 같다. 정당 번호가 작은 1이 마지막 의석을 가져간다.

각 정당의 의석수는 2, 0, 2, 1이 된다. 정당 2가 의석을 하나도 못 받는 경우가 존재한다. 따라서, 둘째 줄의 두 번째 숫자는 0이다.