문제 설명
무게가 서로 다른 \(k\)개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 \(0\)으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 \(S\)라 하자. 예를 들어, 추가 \(3\)개이고, 그 무게가 각각 \({1, 2, 6}\)이면, \(S=9\)이고, 양팔 저울을 한번만 이용하여 \(1\)부터 \(S\)사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서, \(X\)는 그릇에 담는 물의 무게를 나타내고, \(\Box\)는 그릇을 나타낸다.
만약 추의 무게가 \({1, 5, 7}\)이면 \(S=13\)이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 \({1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}\)이다. 즉, \(1\)부터 \(S\)사이 수 가운데 \(9\)와 \(10\)에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.
\(k(3 \le k \le 13)\)개 추 무게 \(g_1, g_2, ... , g_3\)가 주어질 때, \(1\)부터 \(S\)사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.
배점정보 및 제약조건
1. (10점) \(3 \le k \le 5\)
2. (40점) \(3 \le k \le 9\)
3. (50점) 제약 조건 없음.
|
\(X\) |
1 |
2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|
|
\(\Box:1\) |
\(\Box:2\) |
\(\Box:(1+2)\) |
\((\Box+2):6\) |
\((\Box+1):6\) |
\(\Box:6\) |
\(\Box:(1+6)\) |
\(\Box:(2+6)\) |
\(\Box:(1+2+6)\) |
\(k(3 \le k \le 13)\)개 추 무게 \(g_1, g_2, ... , g_3\)가 주어질 때, \(1\)부터 \(S\)사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.
배점정보 및 제약조건
1. (10점) \(3 \le k \le 5\)
2. (40점) \(3 \le k \le 9\)
3. (50점) 제약 조건 없음.
입력 설명
입력의 첫 줄에는 추의 개수를 나타내는 정수 \(k(3 \le k \le 13)\)가 주어진다.
다음 줄에는 \(k\)개의 정수 \(g_i(1 \le i \le k)(1 \le g_i \le 200,000)\)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.
다음 줄에는 \(k\)개의 정수 \(g_i(1 \le i \le k)(1 \le g_i \le 200,000)\)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.
출력 설명
표준 출력으로 \(1\)부터 \(S\)(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 출력하라.
입력 예시 Copy
3
1 5 7
출력 예시 Copy
2