문제
무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다.
양팔 저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다.
주어진 모든 추 무게의 합을 S라 하자.
예를 들어, 추가 3개 이고 그 무게가 각각 {1,2,6} 이면, S = 9이고,
양팔 저울을 한 번만 이용하여 1부터 S사이의 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다.
여기서 X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.
만약 추의 무게가 {1,5,7}이면 S=13이 되고, 양팔 저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 (1,2,3,4,5,6,7,8,11,12,13}이다.
즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.
k(3 ≤ k ≤ 13)개 추 무게 g1, g2,…,gk 가 주어질 때, 1부터 S사이에 있는 정수 중,
양팔 저울을 한 번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.
입력
입력의 첫 불에는 추의 개수를 나타내는 정수 k(3≤k≤13)가 주어진다.
다음 중에는 k개의 정수 gi(1≤i≤k)(1≤gi≤200,000)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.
출력
표준 출력으로 1부터 S(추 무게의 합) 사이에 있는 정수 중,
양팔 저울을 한 번만 이용하여서는 측정이 불가능한 경우의 수를 출력하라.
각 테스트 케이스에 대한 배점 정보와, 제약 조건은 다음과 같다.
- 그룹1, 총 10점 상당의 테스트 케이스로 구성되어 있다. 3≤k≤5를 만족한다.
- 그룹2, 총 40점 상당의 테스트 케이스로 구성되어 있다. 3≤k≤9를 만족한다.
- 그룹3, 총 50점 상당의 테스트 케이스로 구성되어 있다. 추가적인 제약 조건이 없다.
예제1
3
157
2