756 - Biorhythms

[Zhichao Li]

I got wrong answers. Would you please tell me why?

[pascal]
{$E+,I-,N+,Q-,R-,S-}

var
a,b,c,d,s:longint;
ccase:longint;
begin
ccase:=0;

repeat
ccase:=ccase+1;

read(a,b,c,d);
if a+b+c+d=-4 then exit;
a:=a mod 23;
b:=b mod 28;
c:=c mod 33;

s:=a*28*33*6+b*23*33*19+c*23*28*2;
if s>=23*28*33 then s:=s mod (23*28*33);

if s<=d then s:=s+23*28*33;

writeln('Case ',ccase,': the next triple peak occurs in ',s-d,' days.');
until false;
end.[/pascal]

[xenon]

It's multi input

[Dominik Michniewski]

Could anyone tell me what's wrong with this algorithm ?

Code: Select all

#include <stdio.h>

#define MAX   21300

char days[MAX];

int main(void)
{
   int i,n,N,P,E,I,d,c;

   scanf("%d",&N);
   for(n=0;n<N;n++)
   {
      c = 1;
      while(scanf("%d %d %d %d",&P,&E,&I,&d) == 4)
      {
         if((P == -1) && (E == -1) && (I == -1) && (d == -1)) break;
         for(i=0;i<MAX;i++) days[i] = 0;
         for(i=P;i<MAX;i+=23) days[i]++;
         for(i=P-23;i>0;i-=23) days[i]++;
         for(i=E;i<MAX;i+=28) days[i]++;
         for(i=E-28;i>0;i-=28) days[i]++;
         for(i=I;i<MAX;i+=33) days[i]++;
         for(i=I-33;i>0;i-=33) days[i]++;
         for(i=d+1;i<MAX;i++) if(days[i] == 3) break;
         if(i > 21252) i = d + 21252;
         printf("Case %d: the next triple peak occurs in %d days.\n",
            c++,i-d);
      }
      if(n < N-1) printf("\n");
   }
   return 0;
}


I don't talk about eficiency of this algorithm, because it's poor but about cases in which these code doesn't work ... I can't find such one ....
Please help!!!

Dominik Michniewski

[Dominik Michniewski]

I've got Accepted this problem. But I still want to know, why these problem cannot be solved in this way ... I try to send it with larger size of table (23000), but still got WA ....

My Accepted solution use another algorithm (much faster than this)

DOminik

[technogeek]

Can't imagine why I get WA. Some nice test cases may help if you can't point out my mistake......

Code: Select all

#include<iostream.h>

main()
{
        int p,e,i,d,z,count=1,cases;

        for(cin >> cases;cases--;){
        while(1)
        {
                cin>>p>>e>>i>>d;
                if(p==-1) break;

                p = p % 23;
                e = e % 28;
                i = i % 33;

                z = (d/33*33)+i;
                if(z==d) z+=33;
                for(;z<=21252;z+=33)
                if (z%23==p && z%28==e) break;

                cout<<"Case "<<count<<": the next triple peak occurs in "
                <<(z-d)<<" days.\n";
                count++;
        }count=1;cout << "\n";
        }
}


Please help me out oh brainy ones.

[hager]

Your program produces wrong output for this input:
[c]
1

210 44 270 348
152 37 4 148
365 290 231 89
-1 -1 -1 -1
[/c]
The output should be:
[c]
Case 1: the next triple peak occurs in 20976 days.
Case 2: the next triple peak occurs in 21141 days.
Case 3: the next triple peak occurs in 21229 days.
[/c]

I also saw that you print an empty line after the last case, which is probably not WA, but at least PE.

Best regards

--
hager

[technogeek]

Thanks a lot for the test cases. A little investigation reavealed

you may assume that a triple peak will occur within 21252 days of the given date.

I had assumed 21252 days from beginning of year.

Also, even the extra line that you had mention gave me a WA. However even after I removed that, I got PE.......gotta look into that, but who cares ?

Thanks again !

[Observer]

Excuse me, can anyone tell me why the method above works?

'cos I can only think of the "try-it-all" approach (I used it and got ACC in 0.14 s. Not a very good time, of course )

[bugzpodder]

Extended Euclidean Algorithm + Chinese Remainder Theorem

[WR]

The program reproduces all output as it should be, following the posts.
Nevertheless I still get WA.

It would be very nice if somebody could tell me why. I'm rather sure
it's a silly mistake, but I can't find it.

Thanks

Added: I'm off for three weeks so there won't be any replies during
that period.

Addes (years later): It's not a multiple input problem anymore?!

[szymcio2001]

The program reproduces all output as it should be, following the posts.
Nevertheless I still get WA.

It's a multiple input problem.

[CDiMa]

Could anyone tell me what's wrong with this algorithm ?

Code: Select all

#include <stdio.h>

#define MAX   21300


MAX should be at least 21252+365=21617

Code: Select all

         if(i > 21252) i = d + 21252;
         printf("Case %d: the next triple peak occurs in %d days.\n",
            c++,i-d);


I don't talk about eficiency of this algorithm, because it's poor but about cases in which these code doesn't work ... I can't find such one ....
Please help!!!

Dominik Michniewski

Since you can assume that the peak will occur within 21252 days of the given date, you can omit the check

Code: Select all

if(i>21252)

Actually the check is incorrect and should be

Code: Select all

if(i>d+21252)

Anyway I think it's better to omit it entirely...

Ciao!!!

Claudio

[WR]

The program reproduces all output as it should be, following the posts.
Nevertheless I still get WA.

It's a multiple input problem.

Multiple input means there's more than input line? The program
should handle that. Or is there a misconception of multiple input
on my side?!

[CDiMa]

It's a multiple input problem.

Multiple input means there's more than input line? The program
should handle that. Or is there a misconception of multiple input
on my side?!

Multiple input means that the program must process a set of inputs.
Here is the relevant link:
http://online-judge.uva.es/portal/modules/acminfo/?id=minput

Ciao!!!

Claudio

[WR]

Could anybody please tell me what's wrong with this program?
I suppose the program now handles multiple input?! It didn't
before, but even now it's a WA.

CODE removed.

Thanks to UFP2161 (see below) I'm sure the program now will be accepted.