면세점
면접 대비시간 제한1초메모리 제한128 MB
각 상자를 한 브랜드에만 배정해 두 브랜드의 총량이 한도를 넘지 않도록 하면서, 정해진 규칙에 따른 정규 배정을 출력하거나 불가능을 보고한다.
문제
Pedro는 국제 정보 올림피아드에 참가하기 위해 유럽에 다녀오는 길이다. 친구들이 모두 선물을 부탁했기 때문에, 그는 초콜릿이 잔뜩 든 큰 봉지 두 개를 샀다. 하나는 Mindt 상표이고 다른 하나는 Lilka 상표이다. 각 봉지에는 작은 초콜릿이 일정 개수만큼 들어 있으며, 이렇게 큰 봉지 두 개를 사는 것이 낱개 상자를 사는 것보다 훨씬 저렴했다.
집에는 예전 여행 때 모아 둔 빈 초콜릿 상자가 몇 개 있다. Pedro는 방금 산 초콜릿을 이 작은 상자들에 나눠 담아 친구들에게 주려고 한다.
그런데 담기 시작하자마자 문제를 깨달았다. 상표가 서로 다른 두 종류가 있는데, 한 상자에 서로 다른 상표의 초콜릿을 섞어 담으면 그 상자를 받은 친구가 돈을 아끼려는 속셈을 눈치채고 기분이 상할 것이다.
모든 상자를 가득 채우되, 각 상자에는 한 가지 상표의 초콜릿만 담기도록 초콜릿을 나눠 담는 것을 도와주자. 남는 초콜릿이 있어도 괜찮다(남은 것은 Pedro가 갖는다).
입력
입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 줄로 구성된다.
- 첫째 줄에 두 정수 과 이 주어진다 (). 각각 Pedro가 산 Mindt 초콜릿과 Lilka 초콜릿의 개수이다.
- 둘째 줄에 빈 상자의 개수를 나타내는 정수 이 주어진다 ().
- 셋째 줄에 개의 정수가 주어지며, 번째 값은 번 상자의 용량 이다(그 상자를 가득 채우는 데 필요한 초콜릿 개수).
입력의 끝은 인 줄로 표시되며, 이 줄은 처리하지 않는다.
출력
모든 상자는 가득 채워져야 하고 한 가지 상표만 담아야 하므로, 각 상자는 Mindt 또는 Lilka 중 하나에 배정된다. Mindt에 배정된 상자들의 용량 합이 이하이고 Lilka에 배정된 상자들의 용량 합이 이하일 때, 그 배분을 유효한 배분이라고 한다.
각 테스트 케이스마다 한 줄을 출력한다.
유효한 배분이 존재하지 않으면 Impossible to distribute를 출력한다.
유효한 배분이 여럿 존재할 수 있으므로, 답을 유일하게 정하기 위해 다음과 같이 정의되는 표준(canonical) 배분을 출력한다. 상자를 번부터 번까지 순서대로 살펴보면서, 현재 상자를 Mindt에 배정했을 때 남은 상자들을 여전히 유효하게 배분할 수 있으면 그 상자를 Mindt에 배정하고, 그렇지 않으면 Lilka에 배정한다. 그런 다음 Mindt에 배정된 상자의 개수를 출력하고, 이어서 그 상자들의 번호를 오름차순으로 출력한다. 모든 값은 공백 하나로 구분한다. (Mindt에 배정된 상자가 하나도 없으면 0만 출력한다.)