## 350 - Pseudo-Random Numbers

Moderator: Board moderators

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

### 350:Why WA

#include <stdio.h>

void main()
{
long int t,z,i,m,l,a,b,c,d,e,x;

for(e=1;;e++)
{
scanf("%ld %ld %ld %ld",&z,&i,&m,&l);
if(z==0 && i==0 && m==0 && l==0) break;

t=0;
b=l;
for(c=1;;c++)
{
a=(z*l)+i;
b[c]=a%m;

for(d=c-1;d>=0;d--)
if(b[d]==b[c])
{
x=c-d;
t=x;
break;
}
if(t>0) break;
l=b[c];
}

printf("Case %ld: %ld\n",e,t);
}

}

[c][/c]

lu shukai
New poster
Posts: 7
Joined: Tue Aug 06, 2002 9:26 am

### i use your code get ac

array b should more big!
good luck! hsuyt831
New poster
Posts: 3
Joined: Mon Dec 16, 2002 4:53 am

### pb350--why i got time exceeded

i don't knoe how to modify my source code.
here is my source code

#include <stdio.h>

int main()
{
long int j,z,l,m,i,x,y;
int n=1;

scanf("%ld%ld%ld%ld",&z,&i,&m,&l);

while(z!=0 && i!=0 && m!=0 && l!=0){
x=l;
l=(z*l+i)%m;
for(j=1;l!=x;j++)
l=(z*l+i)%m;

printf("case %d : %ld\n",n,j);

n++;

scanf("%ld%ld%ld%ld",&z,&i,&m,&l);
}
return 0;
}

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Your problem is that you think that the first number is always in the cycle. But there may be cases that the first number will never appear among the next numbers!! As a result - TLE. Find any number to repeat - not just the first.

Good luck!

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
why my code give WA?

[c]
#include<stdio.h>

long int stack;

main()
{
long int Z, I, M, L;
int count, i;
#ifndef ONLINE_JUDGE
freopen("350.in","r",stdin);
freopen("350.out","w",stdout);
#endif
while(scanf("%ld %ld %ld %ld",&Z,&I,&M,&L)==4)
{
if(Z==0 && I==0 && M==0 && L==0) break;
count=0;
while(1)
{
stack[count]=L;
L=(Z*L+I)%M;
count++;
for(i=0;i<count;i++)
if(stack==L)
goto cetak;
}
cetak :
printf("%d\n",count-i);
}
return 0;
}[/c]

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia
hey b3yours3lf... for output you must print

Code: Select all

``Case n: ans``
he..he..he.. bye........ b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am
what a stupid mistake.....
thanks!

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am

### not sure why this keeps getting WA

so, what's the issue with this solution...I can't find any more errors in it! All the test cases I made up seem to work fine.

[cpp]

#include <iostream>

using namespace std;

int main() {

int* encountered;

int Z, I, M, L, c;

c = 1;

cin >> Z >> I >> M >> L;

while ((Z != 0) || (I != 0) || (M != 0) || (L != 0)) {

encountered = new int[M];
for (int i = 0; i < M; i++)
encountered = 0;

int pos = 1;

while (encountered[L] == 0) {
encountered[L] = pos;
L = (Z*L + I) % M;
pos++;
}

cout << "Case " << c << ": " << pos-encountered[L] << endl;
c++;
cin >> Z >> I >> M >> L;
delete[] encountered;
}
}
[/cpp]

Hanselmin
New poster
Posts: 2
Joined: Fri Jan 30, 2004 7:52 am

### Re: not sure why this keeps getting WA

I got TLE.
Is there a faster method? thanks
[cpp]
CUT.
Not a good method.
[/cpp]
Last edited by Hanselmin on Fri Jan 30, 2004 10:32 am, edited 1 time in total.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
If you look at the way I did it, I used the numbers 'L' as the array index, and the term # as the value, this way you don't need to waste time using that for loop everytime.

however, it does give me WA...I don't think it's a problem with the idea though, just the implementation of some special case that I can't think of.

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

### 350 is my algorithm wrong

[cpp]
#include <iostream>
using namespace std;
int arr;//used to flag whether a number has been visited
int get(int z,int i,int m,int l)
{
//before the while() loop is initial
int count = 0;
for(int t = 0;t < 10001;t++)
{
arr[t] = 0;
}
arr[l] = 1;
while(1)
{
count++;
l = (z * l % m + i % m) % m;
//cout << l << endl;
if(arr[l] != 1)
{
arr[l] = 1;
}
else
{
break;
}
}
return count;
}
int main()
{
int z,i,m,l;
while(cin >> z >> i >> m >> l)
{
if(!z && !i && !m && !l) break;
else {cout << get(z,i,m,l) << endl;}
}
return 0;
}
[/cpp]

input :
9111 5309 6000 1234

the output should be 500,why mine is 501?
"Learning without thought is useless；thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

randomtaiwanese
New poster
Posts: 32
Joined: Fri Oct 01, 2004 10:53 pm

how could i make it more effective???
[java]//350_PseudoRandomNumbers

import java.io.IOException;
import java.util.StringTokenizer;

class Main
{
{
byte lin[]=new byte[maxLg];
int lg=0,car=-1;
String line="";
try
{
while(lg<maxLg)
{
if ((car<0)||(car=='\n'))
{
break;
}
lin[lg++]+=car;
}
}
catch(IOException e)
{
return(null);
}
if ((car<0)&&(lg==0))
{
return(null);
}
return (new String (lin, 0, lg));
}
public static void main(String[] args)
{
Main newMain = new Main();
newMain.start();
}
void start()
{
String input;
StringTokenizer tokenizer;
int[][] num = new int;
int count = 0;
int a;
{
tokenizer = new StringTokenizer(input);
a = Integer.parseInt(tokenizer.nextToken());
if(a!=0)
{
num[count]=a;
num[count]=Integer.parseInt(tokenizer.nextToken());
num[count]=Integer.parseInt(tokenizer.nextToken());
num[count]=Integer.parseInt(tokenizer.nextToken());
count++;
}
else
{
int z,i,m,l,il,c;
for(int j=0;j<count;j++)
{
c = 1;
z = num[j];
i = num[j];
m = num[j];
l = num[j];
il = num[j];
l = (((z*l)+i)%m);
while(l!=il)
{
c++;
l = (((z*l)+i)%m);
}
System.out.println("Case "+(j+1)+": "+c);
}
break;
}
}
}
}
[/java]

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
But be careful: the cycle might not begin with the seed!

since the seed might not be in the cycle, you want to take note of every random number that the algorithm produce (You can use an array to keep track of everything, and check if you already found that number everytime you generate a new random number, jump up and down if you already found one). Or, you can calculate 1 step ahead and "assume" that this random number is going to be in the cycle (which is true(?) for this problem).

try to change :
[java]
il = num[j];
l = (((z*l)+i)%m);
[/java]

to

[java]
il=((l*z)+i)%m; /* next rand_num */
l=(((z*il)+i)%m; /* next_next_rand_num */
[/java]

The last line will contain four zeroes, and marks the end of the input data.
they have to be all 0's not just the first one.

p.s. you might want to increase your array size (you don't need to store them in array anyway).
hope this helps.
..

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

My first program for #350 assumed that cycle begins with the seed, and it was accepted!
Then I modified it, add in the check funtion, and tested it successfuly on my comp. But i always get the "Wrong answer" when i submit it, please anyone can have a look at my code and tell me wher i did it wrong:

#include <iostream>
#include <stdlib.h>
#include <vector>

using namespace std;
bool Search( vector<int> numProduced, int num);
int main (){
int Z,L,I,M;
int caseNum=1;
vector<int> numProduced;

cin>>Z>>I>>M>>L;

while(Z!=0&&I!=0&&M!=0&&L!=0)
{

int randomNum;
randomNum=(Z*L+I)%M;
numProduced.push_back(randomNum);
int first= randomNum;
int count=1;
while(1)
{
randomNum=(Z*randomNum+I)%M;
if(Search(numProduced,randomNum))
break;
count++;
}

cout<<"Case "<<caseNum++<<": "<<count<<endl;
cin>>Z>>I>>M>>L;
}

return 0;
}
bool Search( vector<int> numProduced, int num)
{
int lenght = numProduced.size();
for(int i = 0; i < lenght; i++)
if(num==numProduced)
return true;
return false;
}

wirjawan
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia
maybe you want to at least push the generated random number into the vector?

and try to change
[cpp]
while(Z!=0&&I!=0&&M!=0&&L!=0)
[/cpp]

to
[cpp]
while(!(Z==0&&I==0&&M==0&&L==0))
[/cpp]

hope this helps
..