프로그램 명: shredding(open)
제한시간: 1 초
당신은 Shredding Company에서 새로운 파쇄기를 개발하는 역할을 맡고 있다. 원래 일반적인 파쇄기는 그냥 종이를 거기 쓰여 있는 내용을 읽어볼 수 없도록 작은 조각으로 잘게 갈아 버리는 것인데, 이 새로운 파쇄기는 다음과 같은 특성들을 갖고 있다.
- 이 파쇄기는 타겟 넘버와 숫자가 쓰여진 종이를 (입력)받는다.
- 입력받은 종이를 한 자리 이상(한 자리 수도 포함)의 수를 포함하는 조각들로 자른다.
- 특성 2에 맞춰 자르되 잘려진 숫자들의 합이 타겟 넘버보다 작으면서 타겟 넘버에 가장 가깝도록 자른다.
예를 들어, 타겟 넘버가 50이고, 종이의 숫자는 12346이라고 하자. 이 파쇄기는 1,2,34,6의 숫자를 포함하는 네 조각으로 자를 것이다. 왜냐하면 이들의 합 43(=1+2+34+6)은 합으로 가능한 수 중 50보다 작고 50에 가장 가까운 수이기 때문이다. 예로 1,23,4,6은 이들의 합 34는 43보다 작기 때문에 유효하지 않다. 12,34,6의 조합은 이들의 합 52가 50을 초과하기 때문에 역시 유효하지 않다.
그림 1. 타겟 넘버가 50일때 12346이 쓰인 종이를 자름
또 세 가지 규칙들이 있다 :
- 만약에 타겟 넘버와 종이에 쓰인 숫자가 같으면, 자르지 않는다. 예로 타겟 넘버가 100이고 종이에 쓰인 수도 100이면, 종이를 자르지 않는다.
- 만약에 어떤 조합으로도 합이 타겟 넘버 이하인 조합을 만들 수 없다면, error를 출력한다. 예를 들어 타겟 넘버는 1이고 종이에 쓰인 수는 123이면, 가장 작은 합 1+2+3=6도 유효한 조합이 아니므로 유효한 조합을 만드는 것은 불가능하다. 최소 합이 1보다 크므로, error를 출력한다.
- 만약에 합이 타겟 넘버를 넘지 않으면서 가장 가까운 조합이 하나 이상 존재한다면, rejected를 출력한다. 예를 들어 타겟 넘버가 15이고 종이에 쓰인 수는 111이라 하면, 가능한 가장 큰 수 12를 만드는 조합이 2개 존재한다 : (a)1, 11 (b) 11, 1;따라서 rejected를 출력한다.
이러한 파쇄기를 만들기 위해, 당신은 위의 규칙들을 따라 시뮬레이트하는 간단한 프로그램을 먼저 작성하기로 결정했다. 첫 번째 수는 타겟 넘버이고 두 번째 수는 자를 종이에 쓰인 수인 두 수가 주어지면, 당신은 어떻게 파쇄기가 두 번째 수를 '자를' 것인지 계산할 필요가 있다.
입력
각 테스트 데이터는 하나의 공백으로 분리된 두 양의 정수를 포함한다 : (1) 첫 번째 정수 ti는 타겟 넘버이고, (2) 두 번째 정수 numi는 잘릴 종이에 쓰인 수이다.
두 정수 모두 0으로 시작하지 않는다...123은 가능하나 0123은 주어지지 않는다. 두 수 모두 6자리를 넘지 않는다고 가정해도 좋다. 0을 두 개 포함하는 라인은 입력의 끝을 의미한다.(그런데 왜 입출력 예에서는 0 0 이 없는지 모르겠습니다만)
출력
입력으로 주어지는 각 테스트 케이스에 대해, 다음 세 개 중 하나를 출력한다 :
- sum part1 part2 ...
- rejected
- error
첫번째 경우에 대해, parti와 sum은 다음을 의미한다 :
- 각 parti는 종이를 자른 조각들이다. 각 조각은 한 자리 이상의 숫자를 포함한다.
- sum은 잘린 조각들의 수의 합이다.
각 숫자들은 한 칸의 공백으로 구분되어야 한다. 어떤 조합도 불가능하면 error를, 하나보다 많은 최적의 조합이 존재하면 rejected를 출력한다. 각 줄에 대해 처음 혹은 끝에 공백을 포함한 쓸데없는 문자를 출력해서는 안 된다.
입출력 예
입력
50 12346
출력
43 1 2 34 6
입력
9 3142
출력
error
입력
6 1104
출력
rejected
출처: Japan 2002 Kanazawa
번역 : sharifa
[질/답]
[제출 현황]
[푼 후(0)]