ACM 猴子分桃答案.doc

先以5小猴子分桃子为例,每个小猴子分桃子时都是分成5堆多一个,5堆多一个这种情况一共有5次,这样就很容易想到先借这些猴子4个桃子,这样的话每个猴子可将桃子平均分成5堆,这样的情况一共有5次。因为题目要求求出最少的符合要求的桃子的数目。所以
有5个小猴子的时候,最少的桃子的数为:5^5-4;当有n个小猴子的时候,最少的桃子数为5^n-4。
留下给老猴子的桃子数为:n+(x+4)*(4/5)^n-4;
代码:
View Code
#include<>
int main()
{
int n;
while (scanf("%d", &n), n)
{
int i;
__int64 sum=1;
for (i=1; i<=n; i++) //桃子数为sum-4;
{
sum*=5;
}
__int64 old=sum;
for (i=1; i<=n; i++) //老猴子得到的桃子数为old+n-4;
{
old=old/5*4;
}
printf("%I64d %I64d\n", sum-4, old+n-4);
}
return 0;
}
这道题的解法很多,最简单的解法是先给这堆桃子添上4只。
第一只猴子:恰好将这堆桃子均分为5份(每份比原来多1只)。它走后,留下4份,比原来留下的4份多4只;
第二只猴子:也恰好将剩下的桃子均分为5份(每份比原来多1只)。它走后,留下4份,比原来留下的4份多4只。
依此类推,每只猴子都可以将桃子均分为5份。
如果最后一只猴子分的时候,桃子是K×5只(K是一个整数),它相当于第四只猴分剩的4份,那么第4只猴子分的时候,桃子是K×5÷4×5只,第三只猴子分的时候,桃子是K×5÷4×5÷4×5÷4×5只,第