## 350 - Pseudo-Random Numbers

Moderator: Board moderators

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
Thanks for the feedback. I don't think the original (multiplier*last + increment)%modulo will overflow because the spec says each number will only be at most 4 digits big and so the largest value this can get is 9999*9999 + 9999 which should be less than 2^31 for an int.

On the other hand, as Solaris pointed out in the same thread, I don't think we should always be counting from the beginning. Instead, it sounds like we should count from the first time the repeated pseudo-random number appears.

If you still have your code, try running it against the sample input and see if you get 501 as opposed to 500 for the 3rd case.

Anyways, I still get WA even if I change my program as recommended. Really strange...

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:

Code: Select all

``````        for(int i=0; i<modulo; i++)
firstAppearance[i] = -1;``````
What if L in input is larger than M and previously you've got the same?
Input

Code: Select all

``````9999 9999 9999 9999
9998 9998 9998 9999
``````
Output

Code: Select all

``````1
1
``````

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
But the problem explicitly stated that "L will be less than M". I wonder if the input can actually be negative numbers since the problem only mentioned they are integers. But there are so many successful submissions which lead me to wonder if things can get that tricky. I feel that my solution is a standard one already haha.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### 350 RE??

I cant understand whats the wrong??? I haved complied it in VC more than 100 times
Last edited by sakhassan on Sat Mar 25, 2006 3:43 pm, edited 1 time in total.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### Re: 350 RE??

sakhassan wrote: DELETED............

I cant understand whats the wrong??? I haved complied it in VC more than 100 times
GOT AC... found my Runtime BUG!!!!!!!!!!!
Why doesnt make it clear in the problem !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
that what happen only if M = 0 ??????????????????????
would that be skipped or not???

wfuny
New poster
Posts: 5
Joined: Fri May 12, 2006 3:06 pm

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

L might bigger than M

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm

### 350 - WA

why wa . plz help me .

Code: Select all

``````# include <iostream>

# include <cmath>

# include <string>

# include <fstream>

using namespace std;

int main()

{

long long int Z,L,I,M,i,n,cas=0;

char arr[10000];

//ifstream fin("testin");

//ofstream fout("testout");

while(cin>>Z>>I>>M>>L)

{

if(Z == 0 && I == 0 && M == 0 && L == 0)	return 0;

cas++;

int count = 0;

for(i=0;i<10000;i++)	arr[i]=0;

arr[L]=1;

L=( (Z % M * L % M) % M + I ) % M;

while(!arr[L])

{

arr[L]=1;

count++;

L=( (Z % M * L % M) % M + I ) % M;

//cout<<L<<'\n';

}

cout<<"Case "<<cas<<": "<<count+1<<'\n';

}

return 0;

}	``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Ami ekhono shopno dekhi...
HomePage

abhi
Learning poster
Posts: 94
Joined: Fri Nov 25, 2005 7:29 pm
can anybody please explainto me why the output of
9999 9999 9999 9999
and
9998 9998 9998 9999
s equal to 1 and not 2

well first we have to generate a random number by using the formula
that gives us 0 for this input.
it is the 1st number in the chain.
using this as the seed and using the formula we get 0 again.
since 0 has already appeared we terminate the chain.
so it should be 2.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
Yes, since 0 has already appeared we terminate the chain, not including the last 0 since it's already there. So the cycle contains only one number.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
I always get TLE for this problem. Does anyone know what test case might lead to it ?

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
This is my code

Code: Select all

``````AC
``````
This is my code, but it always gets TLE when submitted.
Does anyone know why ?
Last edited by RC's on Sat Jul 28, 2007 5:15 am, edited 1 time in total.

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm
avoid checking the already appeared values with looping..
try to do this in O(1) time...
Hint: all parameters will have no more than four digits..

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm
I still don't understand what you mean ?
Do you mean I save the z, i, m, l and the cycle of each case ?
Then it will consume a huge amount of memory.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm