## 350 - Pseudo-Random Numbers

Moderator: Board moderators

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
Do you have any critical test cases ?

epilos@CodeHolic
New poster
Posts: 4
Joined: Sat Mar 01, 2008 6:04 am

### 350 endless loop...

CUT After AC

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

but

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

why???

example is wrong??

Sorry my poor english...

Thanks a lot!!!!!
Last edited by epilos@CodeHolic on Sat Mar 01, 2008 6:44 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 24
Joined: Sat Mar 22, 2008 5:49 am
Location: Chennai
Contact:

### Re: if you get WA on 350 notice that.....

wfuny wrote:L might bigger than M

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.
I am not totally useless, because I can still be used as a bad example

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 350

I read all posts but anyone can help me =(

Code: Select all

``````see next post
``````
Last edited by x140l31 on Tue Jun 30, 2009 9:24 pm, edited 1 time in total.

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA

### Re: 350

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
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 350

ExUCI wrote: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
New poster
Posts: 6
Joined: Sun May 09, 2010 4:37 pm

### Re: 350

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
New poster
Posts: 6
Joined: Sun May 09, 2010 4:37 pm

### 350 - 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
New poster
Posts: 2
Joined: Tue Sep 28, 2010 1:50 pm

### Re: 350

#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
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

### Re: 350

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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 350

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.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson