시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 141 | 58 | 36 | 37.113% |
상근이는 양을 복제하려고 한다. 따라서 복제 기계 N개를 구매했다.
복제 기계에는 키보드가 하나씩 달려있고, 양의 정수를 입력할 수 있다. 기계 안에 양이 K마리 있고, 키보드로 p를 입력했다고 하자. 이 상태에서 복제 버튼을 누르면 기계 안에 있는 양은 총 p*K마리가 된다.
기계에 입력하는 p는 항상 소수이어야 한다. 또, 복제 기계에는 최대 용량이 정해져있고, 이 수만큼 양이 들어있을 수 있다.
상근이는 복제를 하기 위해서 기계로 이동하고 버튼을 누르는 것이 매우 귀찮았다. 결국 상근이는 조수 N명을 고용했고, 각 기계 앞에 한 명씩 배정했다. 그 다음, 각 조수에게 다음과 같은 명령을 외칠 것이다.
상근이는 각 기계에 양을 한 마리씩 넣어 놓았다. 기계를 최대한 효율적으로 이용하기 위해서 각 기계의 최대 용량만큼 양을 복제하려고 한다. 양은 복제를 하는 중간에 뺄 수 없다. 또, 목이 아프기 때문에 명령을 최대한 조금 외치려고 한다.
각 기계의 최대 용량과 M이 주어졌을 때, 양을 최대한 많이 만들기 위해서 필요한 명령의 순서를 구하는 프로그램을 작성하시오. 명령의 수는 최소이어야 하며, 가능한 명령의 순서가 여러 가지인 경우에는 아무거나 출려가면 된다.
첫째 줄에 복제 기계의 수 N이 주어진다. (1 ≤ N ≤ 50)
둘째 줄에는 각 기계의 최대 용량이 주어진다. 이 값은 1,000,000,000보다 작은 자연수이다.
셋째 줄에는 상근이가 한 번의 CLONE 명령에서 외칠 수 있는 최대 수의 개수 M이 주어진다. (1 ≤ M ≤ N)
한 줄에 하나씩 상근이가 외치는 명령을 출력한다.
3 2 3 6 2
ENTER 2 CLONE 1 3 ENTER 3 CLONE 2 3
5 25 25 30 25 25 3
ENTER 2 CLONE 3 ENTER 5 CLONE 1 2 3 CLONE 5 4 1 CLONE 2 4 5 ENTER 3 CLONE 3
Olympiad > Croatian Highschool Competitions in Informatics > 2009 > National Competition #2 - Juniors 1번