【文件属性】:
文件名称:11075强盗分赃
文件大小:505B
文件格式:TXT
更新时间:2015-11-22 06:39:06
强盗分赃
11075 强盗分赃
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: 无限制
Description
有天夜里5个强盗A、B、C、D、E抢到一大堆金币(金币个数不超过n个,n<=100000000),可是怎么也无法平均分成5份,吵吵嚷嚷……
吵累了,只好先睡觉,准备第二天再分。
夜深了,一个强盗A偷偷爬起来,先拿了一个金币私下放自己口袋藏好,再将金币分为5等份,将自己的那一份再私藏好就去睡觉了。
随着第二个强盗B也爬起来,也是私拿了一个金币再分5等份,也私藏起自己那份就睡觉去了。
后来的三个强盗C、D、E也都是这样办的。
问最初有多少个金币?(最初的金币个数有多种可能,请输出n以内所有可能,从小到大排列)
Input
输入一个数,n。
请输出金币数不超过n的可能的初始金币个数。Output
初始金币个数的多种可能(初始金币个数小于等于n)。
请输出不超过n的“所有的”可能,从小到大排列出,中间空格相连。
如果不超过n没有一种可能,输出impossible(无标点,无大写)
例如输入10,则输出impossible
Sample Input
8000
Sample Output
3121 6246
Hint
此题所说的是:每个强盗私拿1个金币后都可以五等分,再私藏起1份,留下4份。
这样的初始金币个数是怎样的数,才能满足这个条件。
方法一:
此题若仅采用程序实现的话是较为简单的,可使用递归算法,或循环处理。递归算法如下(循环处理也很简单):
int count = 0;
int func(int num) //判断初始为num的数是否合适
{
int temp = num-1;
if(temp%5 == 0 && count<5)
{
count++;
return func(temp/5*4);
}
else
if (count==5)
return 1;
else
return 0;
}
但若要分析初始金币个数的通项函数表达就更难一些:
方法二:
从最后一个强盗往前考虑,假设到第五个强盗E时,平均每个强盗得到x个金币
第五个强盗E藏掉一个金币后剩5x个
第四个强盗D藏掉一个金币后剩5(5x+1)/4=25x/4+5/4
第三个强盗C藏掉一个金币后剩5(25x/4+5/4+1)/4=125x/16+45/16
第二个强盗B藏掉一个金币后剩5(125x/16+45/16+1)/4=625x/64+305/64
第一个强盗A藏掉一个金币后剩5(625x/64+305/64+1)/4=3125x/256+1845/256
原来共有金币3125x/256+1845/256+1=3125x/256+2101/256=(12x+8)+53(x+1)/256
这里是突破口:53(x+1)/256 是整数,因金币数是整数,所以x=255时最小的初始金币总数3121个。
方法三:或者这样分析,设金币总数n,由于5个强盗都是先藏一个后,发现余下的金币刚好均分5份,
所以设想在总数中加入4个新金币,则每个强盗占有的金币数不会改变(包括藏了的那一个),
从而每次分金币时这4个假想的金币会留存到后一层总数中,这使得每次分5份都是恰好的整数,
由此可见,n+4至少是5^5的整数倍,所以n的最小值为5^5-4=3121。
其余可能的n值为n=k*(5^5)+4,k为大于1的整数。