[POJ 1006]Biorhythms C++解題
9993 ワード
Biorhythms
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 107569
Accepted: 33365
Description
Some people believe that there are three cycles in a person's life that start the day he or she is born. These three cycles are the physical, emotional, and intellectual cycles, and they have periods of lengths 23, 28, and 33 days, respectively. There is one peak in each period of a cycle. At the peak of a cycle, a person performs at his or her best in the corresponding field (physical, emotional or mental). For example, if it is the mental curve, thought processes will be sharper and concentration will be easier.
Since the three cycles have different periods, the peaks of the three cycles generally occur at different times. We would like to determine when a triple peak occurs (the peaks of all three cycles occur in the same day) for any person. For each cycle, you will be given the number of days from the beginning of the current year at which one of its peaks (not necessarily the first) occurs. You will also be given a date expressed as the number of days from the beginning of the current year. You task is to determine the number of days from the given date to the next triple peak. The given date is not counted. For example, if the given date is 10 and the next triple peak occurs on day 12, the answer is 2, not 3. If a triple peak occurs on the given date, you should give the number of days to the next occurrence of a triple peak.
Input
You will be given a number of cases. The input for each case consists of one line of four integers p, e, i, and d. The values p, e, and i are the number of days from the beginning of the current year at which the physical, emotional, and intellectual cycles peak, respectively. The value d is the given date and may be smaller than any of p, e, or i. All values are non-negative and at most 365, and you may assume that a triple peak will occur within 21252 days of the given date. The end of input is indicated by a line in which p = e = i = d = -1.
Output
For each test case, print the case number followed by a message indicating the number of days to the next triple peak, in the form:
Case 1: the next triple peak occurs in 1234 days.
Use the plural form ``days'' even if the answer is 1.
Sample Input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1Sample Output
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
：生理周期
Time Limit: 1000MS
Memory Limit: 10000K
Total Submissions: 107569
Accepted: 33365
Description
人生には3つの生理周期があり、それぞれ体力、感情、知能周期であり、それらの周期の長さは23日、28日、33日である.各サイクルの1日がピークです.ピークの日には、人は相応の面で優れている.例えば、知能周期のピークは、人は思考が敏捷で、精力が高度に集中しやすい.3サイクルの周長が異なるため、通常、3サイクルのピークは同じ日に落ちません.一人一人にとって、私たちはいつ3つのピークが同じ日に落ちるか知りたいです.各サイクルについて、現在の年の初日からピークまでの日数(必ずしも最初のピークが発生した時間ではありません).あなたのタスクは、その年の初日から数えた日数を指定し、所定の時間から次の3つのピークが同じ日に落ちる時間を出力することです.(所定時間からの日数).たとえば、所定時間が10で、次の3つのピークが同じ日に現れる時間が12であれば、出力2(ここでは3ではないことに注意).
Input
4つの整数:p,e,i,dを入力します.p,e,iはそれぞれ体力、感情、知能のピークが現れる時間(時間はその年の初日から計算される)を表す.dは与えられた時間であり、p,e,またはiより小さい可能性がある.すべての与えられた時間は非負であり、365未満であり、求められた時間は21252未満である.
p=e=i=d=1の場合、入力データは終了する.
Output
指定された時間から、次の3つのピークが同じ日になる時間(指定された時間からの日数).
次の形式を使用します.
Case 1: the next triple peak occurs in 1234 days.
注意:結果が1日であっても、複数形の「days」が使用されます.
Sample Input
0 0 0 0
0 0 0 100
5 20 34 325
4 5 6 7
283 102 23 320
203 301 203 40
-1 -1 -1 -1Sample Output
Case 1: the next triple peak occurs in 21252 days.
Case 2: the next triple peak occurs in 21152 days.
Case 3: the next triple peak occurs in 19575 days.
Case 4: the next triple peak occurs in 16994 days.
Case 5: the next triple peak occurs in 8910 days.
Case 6: the next triple peak occurs in 10789 days.
解決策
中国の残りの定理、本題の難点はプログラミングではありませんて、テーマを分析してそして数学の公式に転化します
本題の解法を導入するには、まず「韓信点兵」という物語を見てみましょう.西漢大将の韓信は、比較的若いため、部下が彼に感心しなかったという伝説があります.ある閲兵式の時、韓信は兵士に3つの縦隊に分けるように要求したが、結局末尾は2人増え、5つの縦隊に変わった.結局末尾は3人増え、7つの縦隊に変わった.結果は2人残った.その後、下級将校は兵士2395人を報告した.韓信はすぐに笑って違うと言った(2395を3で割った余りは1で、2ではないため)、兵士の総数が2300~2400の間にあることが分かったので、韓信は23128233、-----、隣接する2つの数の間隔が105(3、5、7の最小公倍数)であることを根拠に、直ちに実際の人数が2333人であるべきだと言った(2333=128+20χ105+105、それは3余り2で除算して、5余り3で除算して、7余り2で除算します).このように下級将校を敬服させたのが、韓信の点兵の話だ.
韓信点兵問題簡略化:既知n%3=2、n%5=3、n%7=2、nを求める.
私たちのこの問題を見て、p,e,i,dの4つの整数を読みます.
既知(n+d)%23=p; (n+d)%28=e;(n+d)%33=i,nを求める.
二つの問題は同じです.しかし、韓信は当時結果を計算したのだろうか.韓信用は「中国の残りの定理」であり、「孫算経」には計算方法があり、関連資料を調べることができる.「韓信点兵」問題は以下のように計算される.
n%3=2、n%5=3、n%7=2のため、私たちはまず最小の数を探して5と7で除去することができて、そして3の余剰数を除いて1で、ここで、私たちは最小の数が70であることを見つけることができます.どのようなメリットがあるのか、70*1%3=1であれば、70*2%3=2、70*a%3=aであれば、140という3余で割った2の数を見つけることができ、同時に5と7で除去することができます.
同様に、21は3と7で割り切れるが5で割ると1の数であり、63は5で割ると3である.15は3と5で割り切れるが、7で割ると1で、30は7で割ると2の数になる.
では140+63+30=233は、必ず1つを3で割ると2であり、5で割ると3であり、7で割ると2の数であるが、233に3,5,7の最小公倍数を加えたり減らしたりして、得られた数が同様にこの性質を満たすことを容易に知ることができる.韓信は兵士数が2300~2400の間にあることを知っているので、233+iしか必要ありません.× lcm(3,5,7)= 233 + 105 * 20 = 2333.
同じように、この問題の解法は次のとおりです.
n日後、3つの生理周期が同時にピークに達すると仮定します.
既知(n+d)%23=p; (n+d)%28=e;(n+d)%33=i使33×28×a 23で残り1を除去し、33で×28×8=5544;23×33×b 28で残り1を除去し、23×33×19=14421;23×28×c 33で残り1を除去し、23で×28×2=1288.したがって(5544)×p+14421×e+1288×i)% lcm(23,28,33) =n+d
また、lcm(23,28,33)=21252である23,28,33の相互作用.だからn=(5544)×p+14421×e+1288×i-d)%21252
本題で求めたのは最小整数解であり,nが負であることを避けるため,最終結果はn=[n+21252]%21252であり,最終的にnを解く式は以下の通りである.
n=(5544*p+14421*e+1288*i-d+21252)%21252;
問題が数学式に変換されると、それは非常に簡単であることがわかります...結果を直接出力しました.
ソースコード
1 /*
2 poj 1000
3 version:1.0
4 author:Knight
5 Email:[email protected]
6 */
7
8
9 #include<iostream>
10 using namespace std;
11
12 int main(void)
13 {
14 int p,e,i,d;
15 int time=1;
16 while(cin>>p>>e>>i>>d)
17 {
18 if(p==-1 && e==-1 && i==-1 && d==-1)
19 break;
20
21 int lcm=21252; // lcm(23,28,33)
22 int n=(5544*p+14421*e+1288*i-d+21252)%21252;
23 if(n==0)
24 n=21252;
25 cout<<"Case "<<time++<<": the next triple peak occurs in "<<n<<" days."<<endl;
26 }
27 return 0;
28 }