FJNU.1688
Description
The short story titled Coconuts, by Ben Ames Williams, appeared in the Saturday Evening Post on October 9, 1926. The story tells about five men and a monkey who were shipwrecked on an island. They spent the first night gathering coconuts. During the night, one man woke up and decided to take his share of the coconuts. He divided them into five piles. One coconut was left over so he gave it to the monkey, then hid his share and went back to sleep.
Soon a second man woke up and did the same thing. After dividing the coconuts into five piles, one coconut was left over which he gave to the monkey. He then hid his share and went back to bed. The third, fourth, and fifth man followed exactly the same procedure. The next morning, after they all woke up, they divided the remaining coconuts into five equal shares. This time no coconuts were left over.
An obvious question is ``how many coconuts did they originally gather?" There are an infinite number of answers, but the lowest of these is 3,121. But that's not our problem here.
Suppose we turn the problem around. If we know the number of coconuts that were gathered, what is the maximum number of persons (and one monkey) that could have been shipwrecked if the same procedure could occur?
Input
The input will consist of a sequence of integers, each representing the number of coconuts gathered by a group of persons (and a monkey) that were shipwrecked. The sequence will be followed by a negative number.
Output
For each number , determine the largest number of persons who could have participated in the procedure described aboveof coconuts. Display the results similar to the manner shown below, in the Sample Output. There may be no solution for some of the input cases; if so, state that observation.
Sample Input
25
30
3121
-1
Sample Output
25 coconuts, 3 people and 1 monkey
30 coconuts, no solution
3121 coconuts, 5 people and 1 monkey
My Program
#include < iostream >
using namespace std;
int Search( int n)
... {
int i,j,x;
for(i=10;i>1;i--)
...{
x=n;j=i;
while(j)
...{
if((x-1)%i!=0)break;
x-=(x-1)/i+1;j--;
}
if(j==0&&x%i==0)
return i;
}
return 0;
}
int main()
... {
int c,p;
while(cin>>c)
...{
if(c==-1)
break;
cout<<c<<" coconuts, ";
p=Search(c);
if(p>0)
cout<<p<<" people and 1 monkey"<<endl;
else
cout<<"no solution"<<endl;
}
return 0;
}
Source
North Central North America 1997
YOYO's Note:
┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄它是華麗的分隔線
【題意簡述】
有n個椰子（話說我一直以為應該是核桃……），p個人和一隻猴子，
假設有某晚上 第一個人起來後把這些椰子分成p份，恰好多餘一個給了猴子，自己藏了一份；
第二個人起來後又把剩下的椰子分成p份，恰好又多餘一個給猴子，自己藏了一份……
這樣p個人都分完後正好沒有剩餘，現已知n數，求滿足條件的最大的p。
【粗略分析】
一直沒注意是求最大的……
于是從2開始inc循環一直WA……
後來終于看到了determine the largest number of persons who could have participated in the procedure described aboveof coconuts這句話。。便從10起downto勒。。
【C++源代碼】
#include < iostream >
using namespace std;
int Search( int n)
... {
int i,j,x;
for(i=10;i>1;i--)
...{
x=n;j=i;
while(j)
...{
if((x-1)%i!=0)break;
x-=(x-1)/i+1;j--;
}
if(j==0&&x%i==0)
return i;
}
return 0;
}
int main()
... {
int c,p;
while(cin>>c)
...{
if(c==-1)
break;
cout<<c<<" coconuts, ";
p=Search(c);
if(p>0)
cout<<p<<" people and 1 monkey"<<endl;
else
cout<<"no solution"<<endl;
}
return 0;
}
【注意事項】
※ 每個人後面要輸出and 1 monkey
※有可能no solution
※ 沒有1個人的情況，是以down到2就可以勒
【點評】
增掃興那天不在~