350 - Pseudo-Random Numbers

[razibcse]

Why WA please infome me..kindly...

#include <stdio.h>

void main()
{
long int t,z,i,m,l,a,b[1000],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[0]=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]

array b should more big!
good luck!

[hsuyt831]

i don't knoe how to modify my source code.
Can someone please help me...
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]

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]

why my code give WA?

[c]
#include<stdio.h>

long int stack[10000];

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]

hey b3yours3lf... for output you must print

Code: Select all

Case n: ans

he..he..he.. bye........

[b3yours3lf]

what a stupid mistake.....
thanks!

[Quantris]

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]

I got TLE.
Is there a faster method?
thanks
[cpp]
CUT.
Not a good method.
[/cpp]

[Quantris]

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]

[cpp]
#include <iostream>
using namespace std;
int arr[10001];//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?

[randomtaiwanese]

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

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

class Main
{
static String ReadLn(int maxLg)
{
byte lin[]=new byte[maxLg];
int lg=0,car=-1;
String line="";
try
{
while(lg<maxLg)
{
car=System.in.read();
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[100][4];
int count = 0;
int a;
while ((input=Main.ReadLn (255))!=null)
{
tokenizer = new StringTokenizer(input);
a = Integer.parseInt(tokenizer.nextToken());
if(a!=0)
{
num[count][0]=a;
num[count][1]=Integer.parseInt(tokenizer.nextToken());
num[count][2]=Integer.parseInt(tokenizer.nextToken());
num[count][3]=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][0];
i = num[j][1];
m = num[j][2];
l = num[j][3];
il = num[j][3];
l = (((z*l)+i)%m);
while(l!=il)
{
c++;
l = (((z*l)+i)%m);
}
System.out.println("Case "+(j+1)+": "+c);
}
break;
}
}
}
}
[/java]

[wirjawan]

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][3];
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]

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]

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