이사

면접 대비

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

요약

무게 제한이 있는 두 대의 차로 최대 10개의 가구를 나눠 실어, 모든 가구를 옮기는 데 필요한 최소 왕복 횟수를 구한다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 이분 탐색, 완전 탐색, 백트래킹
정답자: 아직 제출이 없습니다

문제

엠마와 에릭은 신혼여행에서 돌아온 뒤 새로 산 집으로 이사를 합니다. 다행히 친구 몇 명이 이사를 도와주고 있습니다. 가구를 옮겨야 하는데 쓸 수 있는 차가 작은 승용차 두 대뿐이라 상황이 조금 까다롭습니다. 가구가 차 안에 들어가지 않기 때문에, 에릭은 가구를 차 지붕 위에 실으려고 합니다. 하지만 각 차의 지붕이 견딜 수 있는 무게에는 한계가 있어서, 모든 가구를 옮기려면 여러 번 왕복해야 합니다.

이사 과정은 다음과 같습니다.

예전 집에서 두 대의 차에 가구를 싣는다.
두 대의 차로 새 집까지 운전해 가서 가구를 위층으로 옮긴다.
모두 예전 집으로 돌아오고, 모든 가구를 새 집으로 옮길 때까지 이 과정을 반복한다.

모두가 즐겁게 이사하고 아무도 외롭지 않도록 일행은 항상 함께 움직입니다. 두 집 사이의 거리가 꽤 멀기 때문에 에릭은 왕복 횟수를 최대한 줄이고 싶어 합니다.

각 가구의 무게 $w_i$ 와 두 차의 지붕 적재 한계 $C_1$ , $C_2$ 가 주어질 때, 모든 가구를 옮기려면 새 집까지 몇 번 왕복해야 할까요? 적재 한계가 $C$ 인 차는 한 번의 왕복에서 무게 합이 최대 $C$ 까지인 가구를 실을 수 있습니다.

입력

첫 번째 줄에는 시나리오의 개수가 주어집니다. 각 시나리오는 두 줄로 이루어집니다. 첫 번째 줄에는 세 정수 $n$ , $C_1$ , $C_2$ 가 주어지며, $n$ 은 가구의 개수( $1 \le n \le 10$ ), $C_1$ 과 $C_2$ 는 두 차의 지붕 적재 한계( $1 \le C_i \le 100$ )입니다. 두 번째 줄에는 가구의 무게를 나타내는 $n$ 개의 정수 $w_1, \dots, w_n$ 이 주어집니다( $1 \le w_i \le 100$ ). 모든 가구는 적어도 한 대의 차에는 실을 수 있음이 보장됩니다.

출력

각 시나리오마다 먼저 Scenario #i: 형식의 줄을 출력합니다. 여기서 $i$ 는 1부터 시작하는 시나리오 번호입니다. 그다음 줄에는 모든 가구를 옮기기 위해 새 집까지 왕복해야 하는 최소 횟수를 출력합니다. 연속한 시나리오 사이는 빈 줄로 구분합니다.

예제2

예제 1

입력

2
6 12 13
3 9 13 3 10 11
7 1 100
1 2 33 50 50 67 98

예상 출력

Scenario #1:
2

Scenario #2:
3

예제 2
입력
```
1
3 10 10
10 10 10
```
예상 출력
```
Scenario #1:
2
```