Page 3 of 4
Posted: Tue Jan 10, 2006 9:36 am
by 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...
Posted: Tue Jan 10, 2006 9:56 am
by 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
Posted: Tue Jan 10, 2006 10:31 am
by 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.
350 RE??
Posted: Sat Mar 25, 2006 10:10 am
by sakhassan
I cant understand whats the wrong??? I haved complied it in VC more than 100 times
Re: 350 RE??
Posted: Sat Mar 25, 2006 3:40 pm
by sakhassan
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???
if you get WA on 350 notice that.....
Posted: Fri May 12, 2006 3:12 pm
by wfuny
L might bigger than M
add L=L%M in your code
I hope it can help you.
350 - WA
Posted: Wed Nov 22, 2006 1:20 pm
by 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;
}
Posted: Wed Nov 22, 2006 5:12 pm
by Jan
Dont open a new thread if there is one already. Try posting in the existing threads.
Posted: Wed Nov 22, 2006 7:03 pm
by 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.
Posted: Wed Nov 22, 2006 11:23 pm
by 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.
Posted: Sat Jul 14, 2007 5:58 pm
by RC's
I always get TLE for this problem. Does anyone know what test case might lead to it ?
Posted: Tue Jul 17, 2007 12:12 pm
by RC's
This is my code
This is my code, but it always gets TLE when submitted.
Does anyone know why ?
Posted: Wed Jul 18, 2007 12:35 am
by 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..
Posted: Wed Jul 18, 2007 6:51 am
by 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.
Posted: Wed Jul 18, 2007 2:56 pm
by Jan
What about keeping track of L only. Then try ayeshapakhi's hint. Hope it helps.