350 - Pseudo-Random Numbers

[stcheung]

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]

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]

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]

I cant understand whats the wrong??? I haved complied it in VC more than 100 times

[sakhassan]

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]

L might bigger than M
add L=L%M in your code
I hope it can help you.

[abhi]

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]

Dont open a new thread if there is one already. Try posting in the existing threads.

[abhi]

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]

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]

I always get TLE for this problem. Does anyone know what test case might lead to it ?

[RC's]

This is my code

Code: Select all

AC

This is my code, but it always gets TLE when submitted.
Does anyone know why ?

[ayeshapakhi]

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]

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]

What about keeping track of L only. Then try ayeshapakhi's hint. Hope it helps.