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 » Tue Aug 06, 2002 2:41 am

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 » Tue Aug 06, 2002 10:08 am

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 » Mon Dec 16, 2002 5:01 am

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 » Mon Dec 16, 2002 8:39 am

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 » Tue Aug 19, 2003 11:00 am

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 » Thu Aug 21, 2003 5:59 pm

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 » Fri Aug 22, 2003 4:21 am

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 » Sat Jan 24, 2004 4:52 am

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 » Fri Jan 30, 2004 8:13 am

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 » Fri Jan 30, 2004 9:40 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

Post by Morning » Wed Oct 06, 2004 7:51 pm

[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 » Wed Oct 20, 2004 8:09 am

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 » Mon Oct 25, 2004 11:05 pm

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 » Wed Oct 27, 2004 5:42 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

Post by wirjawan » Wed Oct 27, 2004 9:56 am

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)”