acm 猴子分香蕉
作者&投稿：东郭很 （若有异议请与网页底部的电邮联系）
猴子分香蕉的问题~
直接用暴力：比如拿3 3的sample考虑：可以从最后一只猴子开始考虑，可以假设最后一只猴子，即第n只，是分成1 + 1 + 1 + 1的，然后把这只猴子的拿掉就省1 + 1了，现在就可以根据1 + 1 = 2；考虑n-1只猴子了，补上他的份，必然是2 + 2 + 2 + 1，考虑n - 2只猴子，发现2 + 2 + 2 + 1 = 7 是无法由两份构成的，所以假设的1 + 1 + 1 + 1的最初情况失败，于是假设2 + 2 + 2 + 1,还失败的话，假设3 + 3 + 3 + 1,由此穷举得正确答案。我刚才现写了下代码，sample是可以过的，不知道对不对，哪个oj的不知道，我们hdoj没这个题，代码：
#include <stdio.h>
int main()
{
int n, k;
int i, j, flag, sum;
while (scanf("%d%d", &n, &k), n || k)
{
for (i = 1; ; i++)
{
sum = 0;
for (j = n; j >= 1; j--)
{
if (j == n)
{
sum += i * k + 1;
}
else
{
if (sum % (k - 1) == 0)
{
sum += sum / (k - 1) + 1;
}
else break;
}
}
if (j == 0)
{
printf("%d\n", sum);
break;
}
}
}
return 0;
}
这道题用递归的算法应该能解决。
1：假设第一次分完自之后剩下的为a1；香蕉的总数是x；a1=x-（x-1）/k；
2：第二次为a2=a1-(a1-1)/k-1；
3：一次下去；
4：an=aN-1-（aN-1-1）/k-1
BNUOJ 4097 猴子分香蕉
此题是问最初最少有多少香蕉设原有x个香蕉先借给第一个猴子4个他就能把这一大堆分成五分
他拿走自己的一份。剩下的｛4/5*X（X+4)}个香蕉
因为第一个猴子拿走自己的香蕉与连吃带拿的一样多。
所以现在剩下的香蕉比原来那样分时多4个
因而第二猴子又能平分成五份
剩下（4/5）^2*（x+4)个香蕉
以此类推
最后剩下（4、5）5(x+4)个香蕉
x+4被5^5整除
所以x至少是5^5-4=3121
设原有X个香蕉，先借给第一个猴子4个香蕉，他就能把这一大堆分成五分并且拿走自己的一份（包括吃掉的那个香蕉）。剩下的(4/5)*(X+4)个香蕉，扣除刚才借来的4个，所以实际上剩余香蕉(4/5)*(X+4)-4个；
第二只猴子出来之后，也同样借来4个香蕉，这时剩余香蕉数量时(4/5)*（X+4)，也能分成5分，并且拿走自己的一份（包含吃掉的一个），剩余(4/5)^2*（X+4)个香蕉，同样扣除刚才借来的4个，实际上剩余(4/5)^2*(X+4)-4个香蕉；以此类推，第四只猴子分完了之后剩余(4/5)^4*（X+4)-4个香蕉，第五只猴子起来吃了一个香蕉正好能评分，也就是(4/5)^4*（X+4)能被5整除，即x+4被5^5整除，所以x至少是5^5-4=3121。
直接用暴力：比如拿3 3的sample考虑：可以从最后一只猴子开始考虑，可以假设最后一只猴子，即第n只，是分成1 + 1 + 1 + 1的，然后把这只猴子的拿掉就省1 + 1了，现在就可以根据1 + 1 = 2；考虑n-1只猴子了，补上他的份，必然是2 + 2 + 2 + 1，考虑n - 2只猴子，发现2 + 2 + 2 + 1 = 7 是无法由两份构成的，所以假设的1 + 1 + 1 + 1的最初情况失败，于是假设2 + 2 + 2 + 1,还失败的话，假设3 + 3 + 3 + 1,由此穷举得正确答案。我刚才现写了下代码，sample是可以过的，不知道对不对，哪个oj的不知道，我们hdoj没这个题，代码：
#include <stdio.h>
int main()
{
int n, k;
int i, j, flag, sum;
while (scanf("%d%d", &n, &k), n || k)
{
for (i = 1; ; i++)
{
sum = 0;
for (j = n; j >= 1; j--)
{
if (j == n)
{
sum += i * k + 1;
}
else
{
if (sum % (k - 1) == 0)
{
sum += sum / (k - 1) + 1;
}
else break;
}
}
if (j == 0)
{
printf("%d\n", sum);
break;
}
}
}
return 0;
}
这道题用递归的算法应该能解决。
1：假设第一次分完自之后剩下的为a1；香蕉的总数是x；a1=x-（x-1）/k；
2：第二次为a2=a1-(a1-1)/k-1；
3：一次下去；
4：an=aN-1-（aN-1-1）/k-1
BNUOJ 4097 猴子分香蕉
