OI题库

USACO Contest Dec2011 Problem 3:逃离农场

【题目描述】

奶牛们做了一个鲁莽的计划：那就是逃离农场主Farmer John。她们已经获得了一个可充气的小型木筏，计划在某天夜晚中，一群奶牛通过使用木筏渡而过位于农场边界的河流。这个计划似乎很完美，直到奶牛们意识到她们的小木筏可能不能承受住她们的体重。

这N头奶牛(1<=N<=20)的体重w_1…w_N。为了计算出一群奶牛的体重能否避免木筏沉没的悲剧，一群奶牛把她们的体重加在一起。

不幸的是，奶牛们在算术方面臭名远扬，并且一群奶牛内的各奶牛体重相加的过程中如果出现了进位（标准的10进制），那么这群奶牛只好放弃因为她们知道她们的体重对于小木筏来说太重了。

所有 那些群内奶牛体重相加不出现进位的奶牛群都被认为可以乘坐那个木筏而不发生沉没。

请帮奶牛们找出能乘坐木筏而不沉没的奶牛群的最大奶牛数。（也就是说，找出最多的奶牛使她们的体重相加而不出现进位。）

程序名：cowescape

输入格式：

▪第1行：奶牛的数量，N(1<=N<=20)

▪第2…N+1行：每行包含一头奶牛的体重，一个整数(1…100,000,000)。

输入样例(file cowescape.in)：

5

522

6

84

7311

19

输入解释：

有5只奶牛，她们的体重分别为522，6，84，7311和19。

输出格式：

只有一行，表示一群使她们的体重相加而不出现进位的奶牛的最大奶牛数量。

输出样例（file cowescape.out）：

3

输出解释：

这三个奶牛的体重分别为：522，6，7311，它们相加不会出现进位：

     522

         6

+7311

——–

  7839

Translated by Freddy.