Informatica Online Judge

  부엌 측정 [2269 / 08DD]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 5   Total Tried : 5


The Champion of this Problem (C++) : gs17044 - ms / 1009byte
My Best Submission (C++) : N/A

[2015 Mid-Central Regional Programming Contest]

Background

부엌에 다양한 부피의 컵이 있다.

당신은 물을 원하는 만큼의 양으로 정확히 맞춰야하지만, 원하는 부피의 컵은 없으며 컵에는 눈금도 없다.

따라서 한 컵에서 다른 컵으로 물을 부을 때는, 붓고 있는 컵이 가득 차거나 원래 컵의 물이 다 떨어지게된다.

예를 들어, 물이 가득찬 부피가 5인 컵에서 텅빈 부피 2인 컵으로 물을 부으면 각각 물이 3, 2만큼 남게 된다.(그림 1(a)참조)




또 다른 예로, 부피가 각각 9, 6, 3, 2인 컵이 있고 9-컵에만 물이 가득 찬 상태에서 9-컵에 8부피의 물이 들어있도록 하려는 경우를 생각해보자.

9-컵의 물을 6-컵과 2-컵에 부은 다음, 나머지 1부피를 9-컵에서 3-컵으로 옮기고, 다시 9-컵에 6-컵과 2-컵을 부으면 부피 8의 물이 완성된다.(그림 1(b)참조)

이 때 부어진 물의 총 부피는 6+2+1+6+2=17이다.

만약 9-컵에서 3-컵으로 물을 부은 다음 3-컵에서 2-컵으로 물을 붓고, 2-컵을 6-컵으로 부으면 똑같이 부피 8의 물이 완성된다.

하지만 이 때 부어진 물의 총 부피는 3+2+2=7이다.(그림 1(c)참조)

마지막 예로, 부피 11, 10, 7, 4, 2의 컵을 가지고 있고 11-컵에만 물이 가득 찬 상태에서 11-컵에 10의 부피의 물이 들어있도록 하려는 경우를 생각해보자.

10-컵에 물을 붓고 나머지 1부피를 다른 컵에 버린 다음 다시 10-컵의 물을 11-컵으로 옮기면 세 번의 이동만에 10+1+10=21의 물을 움직여 끝낼 수 있다.(그림 2(a)참조)

하지만 이동횟수는 더 많지만 물을 덜 움직이는 방법이 존재하고, 그림 2(b)가 이를 보여준다.

Input

첫째 줄에 n c_1 c_2 ... c_n V의 형태로 입력이 된다.
n은 컵의 개수, c_i (1<=i<=n)는 각 컵의 부피, V는 목표 부피이다.

[입력값의 정의역]
2 <= n <= 5
64 >= c_1 > c_2 > ... > c_n >= 1
1 <= V < c_1

항상 가장 큰 컵은 가득 차있고 나머지 컵은 비어있는 상태에서 시작하며, 목표 상태는 가장 큰 컵에 V만큼의 물이 들어있어야한다.

Output

목표 상태로 도달하기 위해 부어야만 하는 물의 총 부피의 최솟값을 출력한다.
만약, 목표 상태로 도달하지 못할 경우 impossible을 출력한다.

IO Example

입력1
2 5 2 4

출력1
impossible

입력2
5 64 45 41 28 2 63

출력2
121

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]