Informatica Online Judge

  균형잡힌 부분집합 [1646 / 066E]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 12   Total Tried : 17


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

[USACO 2012 USOPEN]

Background

경곽이는 각 i번째 젖소가 우유를 매일 M(i)리터(1 <= M(i) <= 100,000,000)를 생산하는 N마리의 젖소(2 <= N <= 20)를 가지고 있다.

경곽이는 우유 생산량을 늘리기 위해서 유축기를 구입했다.이 유축기는 균형잡힌 젖소 그룹에 대해서만 우유를 짤 수 있다.

따라서 경곽이는 자신의 젖소들 중 일부를 고른다. 이렇게 고른 젖소들은 원래 젖소집합에서 고른 subset 이라고 할 수 있다.

어떤 젖소들의 subset이 균형잡히게 되려면, 그 집합을 생산량이 동일하도록 두 그룹으로 분할되어야 된다.

경곽이는 균형잡힌 subset이 얼마나 가능한지 구하고 싶어졌다. 이를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 자연수 N이 입력된다.

두 번째 줄부터 N줄에 걸쳐서 M(i)가 입력된다.

Output

소들의 균형잡힌 subset의 수를 출력한다.

IO Example

입력 예시
4
1
2
3
4


출력 예시
3

* 설명 : 다음과 같이 3가지가 가능하다.

subset {1, 2, 3} 에 대하여 {1, 2}, {3}이 가능하고,
subset {1, 3, 4} 에 대하여 {1, 3}, {4}가 가능하며,
subset {1, 2, 3, 4}에 대하여 {1, 4}, {2, 3}이 된다.

이 이외에는 가능한 균형잡힌 subset은 없다.

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