网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Open12]平衡奶牛子集
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | subsets.in | 输出文件 | subsets.out |
Problem 3: Balanced Cow Subsets [Neal Wu, 2012]
Farmer John's owns N cows (2 <= N <= 20), where cow i produces M(i) units
of milk each day (1 <= M(i) <= 100,000,000). FJ wants to streamline the
process of milking his cows every day, so he installs a brand new milking
machine in his barn. Unfortunately, the machine turns out to be far too
sensitive: it only works properly if the cows on the left side of the barn
have the exact same total milk output as the cows on the right side of the
barn!
Let us call a subset of cows "balanced" if it can be partitioned into two
groups having equal milk output. Since only a balanced subset of cows can
make the milking machine work, FJ wonders how many subsets of his N cows
are balanced. Please help him compute this quantity.
PROBLEM NAME: subsets
INPUT FORMAT:
* Line 1: The integer N.
* Lines 2..1+N: Line i+1 contains M(i).
SAMPLE INPUT (file subsets.in):
4
1
2
3
4
INPUT DETAILS:
There are 4 cows, with milk outputs 1, 2, 3, and 4.
OUTPUT FORMAT:
* Line 1: The number of balanced subsets of cows.
SAMPLE OUTPUT (file subsets.out):
3
OUTPUT DETAILS:
There are three balanced subsets: the subset {1,2,3}, which can be
partitioned into {1,2} and {3}, the subset {1,3,4}, which can be
partitioned into {1,3} and {4}, and the subset {1,2,3,4} which can be
partitioned into {1,4} and {2,3}.