아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

면세점

면접 대비

시간 제한1초메모리 제한128 MB

요약
각 상자를 한 브랜드에만 배정해 두 브랜드의 총량이 한도를 넘지 않도록 하면서, 정해진 규칙에 따른 정규 배정을 출력하거나 불가능을 보고한다.
난이도

보통10점 중 6점

유형
그리디, 동적 계획법, 정렬, 구현
정답자
아직 제출이 없습니다

문제

Pedro는 국제 정보 올림피아드에 참가하기 위해 유럽에 다녀오는 길이다. 친구들이 모두 선물을 부탁했기 때문에, 그는 초콜릿이 잔뜩 든 큰 봉지 두 개를 샀다. 하나는 Mindt 상표이고 다른 하나는 Lilka 상표이다. 각 봉지에는 작은 초콜릿이 일정 개수만큼 들어 있으며, 이렇게 큰 봉지 두 개를 사는 것이 낱개 상자를 사는 것보다 훨씬 저렴했다.

집에는 예전 여행 때 모아 둔 빈 초콜릿 상자가 몇 개 있다. Pedro는 방금 산 초콜릿을 이 작은 상자들에 나눠 담아 친구들에게 주려고 한다.

그런데 담기 시작하자마자 문제를 깨달았다. 상표가 서로 다른 두 종류가 있는데, 한 상자에 서로 다른 상표의 초콜릿을 섞어 담으면 그 상자를 받은 친구가 돈을 아끼려는 속셈을 눈치채고 기분이 상할 것이다.

모든 상자를 가득 채우되, 각 상자에는 한 가지 상표의 초콜릿만 담기도록 초콜릿을 나눠 담는 것을 도와주자. 남는 초콜릿이 있어도 괜찮다(남은 것은 Pedro가 갖는다).

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 세 줄로 구성된다.

  • 첫째 줄에 두 정수 MM과 LL이 주어진다 (0≤M,L≤10000 \le M, L \le 1000). 각각 Pedro가 산 Mindt 초콜릿과 Lilka 초콜릿의 개수이다.
  • 둘째 줄에 빈 상자의 개수를 나타내는 정수 NN이 주어진다 (N≤M+LN \le M+L).
  • 셋째 줄에 NN개의 정수가 주어지며, ii번째 값은 ii번 상자의 용량 Ci>0C_i > 0이다(그 상자를 가득 채우는 데 필요한 초콜릿 개수).

입력의 끝은 M=L=0M = L = 0인 줄로 표시되며, 이 줄은 처리하지 않는다.

출력

모든 상자는 가득 채워져야 하고 한 가지 상표만 담아야 하므로, 각 상자는 Mindt 또는 Lilka 중 하나에 배정된다. Mindt에 배정된 상자들의 용량 합이 MM 이하이고 Lilka에 배정된 상자들의 용량 합이 LL 이하일 때, 그 배분을 유효한 배분이라고 한다.

각 테스트 케이스마다 한 줄을 출력한다.

유효한 배분이 존재하지 않으면 Impossible to distribute를 출력한다.

유효한 배분이 여럿 존재할 수 있으므로, 답을 유일하게 정하기 위해 다음과 같이 정의되는 표준(canonical) 배분을 출력한다. 상자를 11번부터 NN번까지 순서대로 살펴보면서, 현재 상자를 Mindt에 배정했을 때 남은 상자들을 여전히 유효하게 배분할 수 있으면 그 상자를 Mindt에 배정하고, 그렇지 않으면 Lilka에 배정한다. 그런 다음 Mindt에 배정된 상자의 개수를 출력하고, 이어서 그 상자들의 번호를 오름차순으로 출력한다. 모든 값은 공백 하나로 구분한다. (Mindt에 배정된 상자가 하나도 없으면 0만 출력한다.)

예제3

  1. 예제 1

    입력
    12 9
    4
    5 2 8 5
    100 120
    5
    21 32 110 54 3
    0 0
    
    예상 출력
    3 1 2 4
    Impossible to distribute
    
  2. 예제 2

    입력
    10 0
    2
    4 6
    0 0
    
    예상 출력
    2 1 2
    
  3. 예제 3

    입력
    0 10
    2
    4 6
    0 0
    
    예상 출력
    0