Question

pku poj 1006 总是wrong answer ！

以下是我的代码，运行的特殊数据都对，不知道哪里错了，望高手指点一下！
#include<iostream>
using namespace std;
typedef struct pe
{
int date;
struct pe *next;
}PEAK;
int main()
{
int fun(int p,int e,int i,int d);
int p,e,i,d,j=0,k;
PEAK *h=NULL ,*peak,*q;
cin>>p>>e>>i>>d;
while(!(p==-1&&e==-1&&i==-1&&d==-1))
{
peak=new PEAK;
peak->date=fun(p,e,i,d);
peak->next=NULL;
if(h==NULL)
{
h=peak;
q=h;
}
else
{
q->next=peak;
q=q->next;
}
j++;
cin>>p>>e>>i>>d;
}
q=h;
for(k=0;k<j;k++)
{
cout<<"Case "<<k+1<<": the next triple peak occurs in "<<q->date<<" days."<<endl;
q=q->next;
}
return 0;
}
int fun(int p,int e,int i,int d)
{
int max=i;
while(max-p<=0||max-e<=0)
max+=33;
while(!((max-e)%28==0&&(max-p)%23==0))
max+=33;
max=max-d;
if(max>21252)
max=max%21252;
return max;
}
如果真对我有帮助，我会追加分数的！

Answer 1

具体哪里错了我不清楚。但即使修正了也未必能过，一开始我也用这种方法的。结果TLE。这题应用了中国剩余定理能过。下面是我的比较拙的代码，希望对你有帮助。(算法部分请参考中国剩余定理的相关资料，《算法导论》上有)

#include <stdio.h>
int n1 = 23, n2 = 28, n3 = 33, n;
int m1, m2, m3;
int c1, c2, c3;
int ExtendedEuclid(int a, int n, int& x, int& y)
{
if(n == 0)
{
x = 1;
y = 0;
return a;
}
int d = ExtendedEuclid(n, a % n, x, y);
int x1 = x;
x = y;
y = x1 - (a / n) * y;
return d;
}
void Initial()
{
n = n1 * n2 * n3;
m1 = n / n1;
m2 = n / n2;
m3 = n / n3;
int x, y;
ExtendedEuclid(m1, n1, x, y);
x = (x % n1 + n1) % n1;
//printf("x: %d\n", x);
x = (x % n1 + n1) % n1;
c1 = m1 * x;
ExtendedEuclid(m2, n2, x, y);
x = (x % n2 + n2) % n2;
//printf("x: %d\n", x);
c2 = m2 * x;
ExtendedEuclid(m3, n3, x, y);
x = (x % n3 + n3) % n3;
//printf("x: %d\n", x);
c3 = m3 * x;
//printf("c1 %d\nc2 %d\nc3 %d\n", c1, c2, c3);
}

int Ans(int p, int e, int i, int d)
{
int ans;
ans = (p * c1) % n;
ans = (ans + e * c2) % n;
ans = (ans + i * c3) % n;
ans = ((ans - d) % n + n) % n;
if(ans == 0)
ans = n;
return ans;
}
int main()
{
Initial();
int p, e, i, d;
int num = 0;
while(scanf("%d%d%d%d", &p, &e, &i, &d) != EOF)
{
if(p == -1 && e == -1 && i == -1 && d == -1)
break;
printf("Case %d: the next triple peak occurs in %d days.\n", ++num, Ans(p, e, i, d));
}
return 0;
}

Answer 2

if(max>21252)
max=max%21252;

这里有问题. 你还要进行更多判断, 因为max可能为负数.
可以考虑加入
if ( max <= 0 )
max += 21252;

比如这个数据
10 5 0 34

Answer 3

//---------------------------------------------------------------------------

#include<iostream>
using namespace std;

int main(void)
{
int fun(int p,int e,int i,int d);
int p,e,i,d,j=1,k;

do
{
cin>>p>>e>>i>>d;
if (!(p==-1&&e==-1&&i==-1&&d==-1)) {
k=fun(p,e,i,d);
cout<<"Case "<<j++<<": the next triple peak occurs in "<<k<<" days."<<endl;
}

} while(!(p==-1&&e==-1&&i==-1&&d==-1));
return 0;
}
int fun(int p,int e,int i,int d)
{
int max=i;
while(max-p<=0||max-e<=0)
max+=33;
while(!((max-e)%28==0&&(max-p)%23==0))
max+=33;
max=max-d;
if(max>21252)
max=max%21252;
return max;
}
//---------------------------------------------------------------------------

Answer 4

#include<iostream>
using namespace std;
typedef struct pe
{
int date;
struct pe *next;
}PEAK;
int main()
{
int fun(int p,int e,int i,int d);
int p,e,i,d,j=0,k;
PEAK *h=NULL ,*peak,*q;
cin>>p>>e>>i>>d;
while(!(p==-1&&e==-1&&i==-1&&d==-1))
{
peak=new PEAK;
peak->date=fun(p,e,i,d);
peak->next=NULL;
if(h==NULL)
{
h=peak;
q=h;
}
else
{
q->next=peak;
q=q->next;
}
j++;
cin>>p>>e>>i>>d;
}
q=h;
for(k=0;k<j;k++)
{
cout<<"Case "<<k+1<<": the next triple peak occurs in "<<q->date<<" days."<<endl;
q=q->next;
}
return 0;
}
int fun(int p,int e,int i,int d)
{
int max=i;
while(max-p<=0||max-e<=0)
max+=33;
while(!((max-e)%28==0&&(max-p)%23==0))
max+=33;
max=max-d;
if(max>21252)
max=max%21252;
return max;
}

Answer 5

#include "stdafx.h"

我刚刚运行的，把第一句改成如上，即没有错误了~