读书人

[] 一道ACM题 分苹果 实在是想不出来

发布时间: 2012-05-01 12:48:58 作者: rapoo

[求助] 一道ACM题 分苹果 实在是想不出来,哪位牛人帮帮忙啊
Description

有1000个苹果和10个筐子,筐子的编号为1-10.现要将这1000个苹果放入这10个筐子,要求:

(1)编号大的筐子中的苹果数量要严格大于编号小的筐子中的苹果数.

(2)从1-1000中任取1个数字,这个数字都能由10个筐子中的某几个筐子的苹果数和组成.

注意:筐中的苹果是一个整体,不能取筐中的一部分苹果,即一旦选取某个筐子,该筐的苹果数就必须全部计入.
Input
没有输入.
Output

要求在屏幕上按"字典"升序打印出所有可行放法.

每行打印1种方法,按编号升序打印出对应的筐中苹果个数,中间用空格隔开.

注意:行尾不要有任何空格出现.
Example Input

Example Output

1 2 4 8 16 31 63 125 250 500
1 2 4 8 16 31 63 125 251 499
1 2 4 8 16 31 63 126 249 500
.
.
.
1 2 4 8 16 32 64 128 256 489

[解决办法]
apples-i是剩下的苹果数目
(n-2)*(n-1)/2则是使得剩下的筐子里苹果逐个增加的数目
apples-i-(n-2)*(n-1)/2表示剩下的苹果数目再扣除需要递增的数目之后还需要多少个
(apples-i-(n-2)*(n-1)/2)/(n-1)计算出下一个框子里的苹果数
i<(apples-i-(n-2)*(n-1)/2)/(n-1),则可满足当前筐中的苹果数少于后续筐中数目。但这里有除法舍入问题存在。
i*(n-1)<apples-i-(n-2)*(n-1)/2,避开舍入问题

读书人网 >C语言

热点推荐