350 - Pseudo-Random Numbers

[RC's]

Okay then, I've followed your advice. Now I get WA.
Do you have any critical test cases ?

[epilos@CodeHolic]

CUT After AC

1, 2, 4 example is right....

but

third example..... infinity....

why???

example is wrong??



Sorry my poor english...


Thanks a lot!!!!!

[mf]

Read the problem statement carefully.

The cycle might not begin with the seed

Any sequence of form <next number> = f(<previous number>) mod M is always periodic, simply because there are just M possible numbers (0..M-1), and once any number repeats, the sequence will repeat from that point forward, too. However, some initial part of the sequence (called 'pre-cycle') might not appear in its cyclic part.

[zyxw]

L might bigger than M

add L=L%M in your code

I hope it can help you.

Just now i got AC, where i considered that L is less than M.

One more thing:
As the problem states, "the cycle might not begin with the seed!", I used something like this:

Code: Select all

initialize count=1;

loop
   // calculate next 'l' using formula.
   // check whether it is repeated and break if so.
   // Else count++.
end loop

if ( repeated_number == seed )
 print count;
else
 print (count-1);

Hope it helps.

[x140l31]

help please!!!

I read all posts but anyone can help me =(

Code: Select all

see next post

[ExUCI]

The only thing wrong is that you have to generate first a random number and then start your calculations

Remove you code after AC

[x140l31]

The only thing wrong is that you have to generate first a random number and then start your calculations

Remove you code after AC

I don't understand why it will modify the output...

I changed it and still getting WA =/

Code: Select all

Removed after AC

L might not be less than M

Critical Input:
1111 1111 1111 1111
9999 9999 9999 9999
9876 5432 1234 1786
1234 5678 8956 8524
9999 1111 9999 1111

Critical Output:
Case 1: 1
Case 2: 1
Case 3: 77
Case 4: 373
Case 5: 1

From http://tausiq.wordpress.com/2009/01/24/acm-uva-350/

[ytlau9]

HI everyone, i am new to coding and uva..
can anyone tell me why i keep got WA with my code..

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
int main(){
        int *a;
        int z,l,i,m,count,sum,count2=0;
        while(scanf("%d %d %d %d", &z,&i,&m,&l),!(z==0 && i==0 && m==0 && l==0)){
                a = (int*)malloc(sizeof(int)*10000);
                memset(a,0,sizeof(a));
                count=1; count2++;
                while(a[l]==0){
                        a[l]=count++;
                        l = ((z*l)+i)%m;
                }
                printf("Case %d: %d\n", count2, count-a[l]);
                free(a);
        }
        return 0;
}

[ytlau9]

PLEASE HELP ME!! I HAVE PASSED ALL TEST CASES I'VE FOUND...BUT I STILL GET WA!
CAN ANYONE TELL ME WHAT'S THE PROBLEM OF MY CODE!?

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
int main(){
        int *a;
        int z,l,i,m,count,sum,count2=0;
        while(scanf("%d %d %d %d", &z,&i,&m,&l),!(z==0 && i==0 && m==0 && l==0)){
                a = (int*)malloc(sizeof(int)*10000);
                memset(a,0,sizeof(a));
                count=1; count2++;
                while(a[l]==0){
                        a[l]=count++;
                        l = ((z*l)+i)%m;
                }
                printf("Case %d: %d\n", count2, count-a[l]);
                free(a);
        }
        return 0;
}

[kgduu]

#include <stdio.h>

#define MAXN 10000

int a[MAXN];

int main()
{
int Z, I, M, L;
int count;
int tests = 0;

freopen("c:\\uva_in.txt", "r", stdin);

while (scanf("%d%d%d%d", &Z, &I, &M, &L) && (Z != 0 || I != 0 || M != 0 || L != 0))
{
memset(a, 0, sizeof(a));
count = -1;

do
{
L = ((Z % M) * (L % M) + I) % M;
a[L]++;
count++;
} while (a[L] == 1);

printf("Case %d: %d\n", ++tests, count);
}

return 0;
}

[sir. manuel]

This problem it's easy, i used a little hash because i am training problems with hash,,,
You have to read the problem, and see, that YOU FIRTS HAVE TO GENARATE A SEED WITH L, then you can start to cont,,,

[plamplam]

Just check if a number appears twice or not. Break your loop whenever a number that has previously appeared shows up again.
If the seed is given then print count and if the seed is not given then print count - 1.