레이팅 미적용설명
농부 존(Farmer John)은 N마리 (2 <= N <= 20)의 소를 기르며, 소 i는 매일 M(i) 단위 (1 <= M(i) <= 100,000,000)의 우유를 생산한다. FJ는 매일 소젖을 짜는 과정을 간소화하고 싶어서, 헛간에 최신형 착유기를 설치했다. 안타깝게도 이 기계는 지나치게 민감한 것으로 드러났다. 헛간 왼쪽에 있는 소들의 우유 생산량 총합이 오른쪽에 있는 소들의 총합과 정확히 같아야만 제대로 작동한다!
어떤 소들의 부분집합을 우유 생산량이 같은 두 그룹으로 나눌 수 있으면, 그 부분집합을 "균형 잡혔다"고 하자. 균형 잡힌 소 부분집합만이 착유기를 작동시킬 수 있으므로, FJ는 N마리의 소의 부분집합 중 균형 잡힌 것이 몇 개인지 궁금해한다. 이 수를 계산하는 것을 도와주자.
제약
입력 형식
첫째 줄: 정수 N.
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 M(i)가 주어진다.
출력 형식
균형 잡힌 소 부분집합의 개수.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
subsets.in · 출력을 쓸 파일 subsets.out예제 1
입력
4
1
2
3
4출력
3설명
Input details: There are 4 cows, with milk outputs 1, 2, 3, and 4.
Output details: There are three balanced subsets: {1,2,3} -> {1,2},{3}; {1,3,4} -> {1,3},{4}; {1,2,3,4} -> {1,4},{2,3}.
문제 정보
태그