350 - Pseudo-Random Numbers

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

350:Why WA

Post by 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
New poster
Posts: 7
Joined: Tue Aug 06, 2002 9:26 am

i use your code get ac

Post by lu shukai »

array b should more big!
good luck! :D

hsuyt831
New poster
Posts: 3
Joined: Mon Dec 16, 2002 4:53 am

pb350--why i got time exceeded

Post by 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
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by 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
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by 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
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

hey b3yours3lf... for output you must print

Code: Select all

Case n: ans
he..he..he.. bye........ :lol:

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf »

what a stupid mistake.....
thanks!

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

not sure why this keeps getting WA

Post by 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
New poster
Posts: 2
Joined: Fri Jan 30, 2004 7:52 am

Re: not sure why this keeps getting WA

Post by Hanselmin »

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
Location: Edmonton AB Canada

Post by 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
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

350 is my algorithm wrong

Post by 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?
"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

350 please help

Post by 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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by 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
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

350 wrong answer-strange!

Post by 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
New poster
Posts: 16
Joined: Fri Oct 01, 2004 10:48 pm
Location: Indonesia

Post by 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
..

Post Reply

Return to “Volume 3 (300-399)”