페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3782

소를 균형있게 나누자 (Balanced Cow Subsets) 1초 128MB

문제

농부 존은 N마리의 소를 소유하고 있는데, 소 i는 매일 M_i 리터의 우유를 생산한다.

농부 존은 매일 소의 젖을 짜는 과정을 간소화 하기 위해 헛간에 새로운 착유 기계를 설치한다.

불행히도 기계는 너무 민감한 것으로 밝혀졌다. 안타깝게도 이 기계는 헛간 왼쪽에 있는 소들의 총 우유 생산량과 헛간 오른쪽에 있는 소들의 총 우유 생산량이 정확히 같은 경우에만 제대로 작동한다!

우유 생산량이 동일한 두 그룹으로 나눌 수 있는 젖소의 하위 집합을 "균형"잡혔다고 부른다면, 균형 잡힌 소의 하위 집합만이 착유 기계를 작동시킬 수 있으므로 농부 존은 N 마리의 소들 중 얼마나 많은 하위 집합이 균형을 이루고 있는지 궁금해한다.

그가 이 수량을 계산하도록 도와주자.


입력

첫 줄에 N이 주어진다. (2 \le N \le 20)

두 번째 줄부터 N줄에 걸쳐 i+1번째 줄에 M_i가 주어진다. (1 \le M_i \le 100\,000\,000)


출력

N 마리의 소들 중 몇 개의 하위 집합이 균형을 이루고 있는지 출력한다.


예제1

입력
4
1
2
3
4
출력
3

입력: 소 4마리가 있고 우유 생산량은 1, 2, 3, 4입니다.

출력: 3개의 균형 잡힌 하위 집합이 있습니다. 하위 집합 {1,2,3} 은 {1,2}와 {3}으로 분할 될 수 있고, 하위 집합 {1,3,4}는 {1,3}과 {4}로 분할 될 수 있습니다. , 그리고 {1,4}과 {2,3}으로 분할 될 수 있는 하위 집합 {1,2,3,4}이 있다.


출처

USACO 2012 US Open Gold

역링크 공식 문제집만