生理周期
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 133189 | Accepted: 42577 |
Description
人 生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。在高峰这天，人会在相应的方面 表现出色。例如，智力周期的高峰，人会思维敏捷，精力容易高度集中。因为三个周期的周长不同，所以通常三个周期的高峰不会落在同一天。对于每个人，我们想 知道何时三个高峰落在同一天。对于每个周期，我们会给出从当前年份的第一天开始，到出现高峰的天数（不一定是第一次高峰出现的时间）。你的任务是给定一个 从当年第一天开始数的天数，输出从给定时间开始（不包括给定时间）下一次三个高峰落在同一天的时间（距给定时间的天数）。例如：给定时间为10，下次出现 三个高峰同天的时间是12，则输出2（注意这里不是3）。
Input
输入四个整数：p, e, i和d。 p, e, i分别表示体力、情感和智力高峰出现的时间（时间从当年的第一天开始计算）。d 是给定的时间，可能小于p, e, 或 i。 所有给定时间是非负的并且小于365, 所求的时间小于21252。
当p = e = i = d = -1时，输入数据结束。
Output
从给定时间起，下一次三个高峰同天的时间（距离给定时间的天数）。
采用以下格式：
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 -1
Sample 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.
Source
Translator
北京大学程序设计实习2007, Xie Di
分析：
看到这个题目，三个时间互质，好像没有什么快捷方法，就先尝试暴力破解了。
暴力破解写了3次：
设下一次巅峰时刻分别为p+23*j，i+33*m，e+28*k。
1. j++，m++，k++，直到找到三个数字相等的时刻就是全盛时期。测试数据都过了，但是。。。超时了。
2. 题目要求了，时间不能超过21252天，所以，从d+1开始到21252遍历，找到(ans-p)%23==0 && (ans-e)%28==0 && (ans-i)%33==0时候，就是答案了。耗时250ms。
3. 对2做了点小优化，不再是从d+1到21252一个一个遍历，而是改为，从i+33开始以33为步长进行遍历。耗时110ms。
这个题目也可以用“中国剩余定理”，传说中的韩信点兵啊，具体见http://blog.csdn.net/bo_jwolf/article/details/9355937
第一次：
#include <stdio.h>
#include <stdlib.h> #define SUCCESS 1
#define FAILURE 0 int p = ;
int e = ;
int i = ;
int d = ; int Search(int j, int M, int *inm, int i)
{
int m = *inm;
int result = FAILURE;
while()
{
if(p+*j == i+M*m)
{
result = SUCCESS;
break;
}
else if(p+*j > i+M*m)
m++;
else if(p+*j < i+M*m)
{
m = ;
result = FAILURE;
break;
}
}
*inm = m;
return result;
} int Match(int *j, int *k, int *m)
{
while(*j<)
{
if(SUCCESS == Search(*j,,m,i))
{
if(SUCCESS == Search(*j,,k,e))
return SUCCESS;
} (*j)++;
}
return FAILURE;
} int main(void)
{
int j = ;
int k = ;
int m = ;
int ans = ;
int n = ;
while(==scanf("%d %d %d %d", &p, &e, &i, &d) && (p!=- || e!=- || i!=- || d!=-))
{
getchar();
n++;
p = p % ;
e = e % ;
i = i % ; Match(&j,&k,&m); ans = p+*j; if(ans < d)
ans = + ans - d;
else
ans = ans -d; if(ans% > d)
ans %= ; printf("Case %d: the next triple peak occurs in %d days.\n", n, ans);
}
return ;
}
第二次：
#include <stdio.h>
#include <stdlib.h> int p = ;
int e = ;
int i = ;
int d = ; int main(void)
{
int ans = ;
int n = ;
while(==scanf("%d %d %d %d", &p, &e, &i, &d) && (p!=- || e!=- || i!=- || d!=-))
{
getchar();
n++;
p = p % ;
e = e % ;
i = i % ; for(ans=d+;;ans++)
{
if((ans-p)%== && (ans-e)%== && (ans-i)%==)
{
break;
}
} if(ans < d)
ans = + ans - d;
else
ans = ans - d; if(ans% > d)
ans %= ; printf("Case %d: the next triple peak occurs in %d days.\n", n, ans);
}
return ;
}
第三次：
#include <stdio.h> int p = ;
int e = ;
int i = ;
int d = ; int main(void)
{
int ans = ;
int n = ;
int flag = ;
while(==scanf("%d %d %d %d", &p, &e, &i, &d) && (p!=- || e!=- || i!=- || d!=-))
{
getchar();
p = p % ;
e = e % ;
i = i % ;
ans = i+;
flag = ; if(p==e && e==i && p>d)
{
ans=p-d;
flag=;
}
if(p==e && e==i && p<=d)
{
ans=p+-d;
flag=;
} if(flag)
{
while(((ans-p)%)!=||((ans-e)%)!=||ans-d<)
ans+=;
ans -= d;
} printf("Case %d: the next triple peak occurs in %d days.\n", ++n, ans);
}
return ;
}