#PUSACO11DecBro3. 逃离农场
逃离农场
逃离农场
题目描述
奶牛们决定采取一个大胆的计划来逃脱农夫约翰的魔掌。他们设法买了一只小型充气筏,在夜幕的掩护下,一群牛登上木筏,划到农场的边界地带。这个计划似乎很完美,直到 奶牛意识到他们的小型充气筏可能无法承受很大的重量!N只牛(1 <= n <= 20)的重量分别为 w_1 … w_n。为了弄清楚一组奶牛是否足够轻,以避免翻船,奶牛们将该组的所有重量加起来。不幸的是,奶牛在算术上是出了名的差,如果在一个组中增加奶牛的重量会发生进位(使用10进制计算),奶牛就会放弃,并得出结论,这个组太重了会翻船。某组的重量相加不产生任何进位的则该组被认为足够轻,筏能承受这样的重量。请帮助奶牛确定最大的组的大小,他们相信可以登筏逃离(即最大的组,所有重量加在一起没有进位)。
输入格式
第1行:奶牛的只数,N(1 <= N <= 20)。第2..N+1行:每一行包含一个整数,表示一只奶牛的重量,范围是1....100,000,000。
输出格式
第1行:最多的奶牛只数前提是它们的重量相加不会产生进位。
数据范围
(原站未提供,导入后需人工补齐)
样例
5
522
6
84
7311
19
3
提示
输入描述:这里有5只奶牛,重量分别是522,6,84,7311,19。
输出描述:这样的3只奶牛 522,6,7311,加在一起不会产生进位:
