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

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

Post by RC's »

Okay then, I've followed your advice. Now I get WA.
Do you have any critical test cases ?

epilos@CodeHolic
New poster
Posts: 4
Joined: Sat Mar 01, 2008 6:04 am

350 endless loop...

Post by epilos@CodeHolic »

CUT After AC

1, 2, 4 example is right....

but

third example..... infinity....

why???

example is wrong??



Sorry my poor english...


Thanks a lot!!!!!
Last edited by epilos@CodeHolic on Sat Mar 01, 2008 6:44 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

Read the problem statement carefully.
The cycle might not begin with the seed
Any sequence of form <next number> = f(<previous number>) mod M is always periodic, simply because there are just M possible numbers (0..M-1), and once any number repeats, the sequence will repeat from that point forward, too. However, some initial part of the sequence (called 'pre-cycle') might not appear in its cyclic part.

zyxw
New poster
Posts: 24
Joined: Sat Mar 22, 2008 5:49 am
Location: Chennai
Contact:

Re: if you get WA on 350 notice that.....

Post by zyxw »

wfuny wrote:L might bigger than M

add L=L%M in your code

I hope it can help you.
Just now i got AC, where i considered that L is less than M.

One more thing:
As the problem states, "the cycle might not begin with the seed!", I used something like this:

Code: Select all

initialize count=1;

loop
   // calculate next 'l' using formula.
   // check whether it is repeated and break if so.
   // Else count++.
end loop

if ( repeated_number == seed )
 print count;
else
 print (count-1);
Hope it helps.
I am not totally useless, because I can still be used as a bad example :P

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 350

Post by x140l31 »

help please!!!

I read all posts but anyone can help me =(

Code: Select all

see next post
Last edited by x140l31 on Tue Jun 30, 2009 9:24 pm, edited 1 time in total.

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA

Re: 350

Post by ExUCI »

The only thing wrong is that you have to generate first a random number and then start your calculations

Remove you code after AC :D
Remove your code after AC :)

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 350

Post by x140l31 »

ExUCI wrote:The only thing wrong is that you have to generate first a random number and then start your calculations

Remove you code after AC :D
I don't understand why it will modify the output...

I changed it and still getting WA =/

Code: Select all

Removed after AC

L might not be less than M

Critical Input:
1111 1111 1111 1111
9999 9999 9999 9999
9876 5432 1234 1786
1234 5678 8956 8524
9999 1111 9999 1111

Critical Output:
Case 1: 1
Case 2: 1
Case 3: 77
Case 4: 373
Case 5: 1

From http://tausiq.wordpress.com/2009/01/24/acm-uva-350/


ytlau9
New poster
Posts: 6
Joined: Sun May 09, 2010 4:37 pm

Re: 350

Post by ytlau9 »

HI everyone, i am new to coding and uva..
can anyone tell me why i keep got WA with my code..

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
int main(){
        int *a;
        int z,l,i,m,count,sum,count2=0;
        while(scanf("%d %d %d %d", &z,&i,&m,&l),!(z==0 && i==0 && m==0 && l==0)){
                a = (int*)malloc(sizeof(int)*10000);
                memset(a,0,sizeof(a));
                count=1; count2++;
                while(a[l]==0){
                        a[l]=count++;
                        l = ((z*l)+i)%m;
                }
                printf("Case %d: %d\n", count2, count-a[l]);
                free(a);
        }
        return 0;
}

ytlau9
New poster
Posts: 6
Joined: Sun May 09, 2010 4:37 pm

350 - WA

Post by ytlau9 »

PLEASE HELP ME!! I HAVE PASSED ALL TEST CASES I'VE FOUND...BUT I STILL GET WA!
CAN ANYONE TELL ME WHAT'S THE PROBLEM OF MY CODE!?

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
int main(){
        int *a;
        int z,l,i,m,count,sum,count2=0;
        while(scanf("%d %d %d %d", &z,&i,&m,&l),!(z==0 && i==0 && m==0 && l==0)){
                a = (int*)malloc(sizeof(int)*10000);
                memset(a,0,sizeof(a));
                count=1; count2++;
                while(a[l]==0){
                        a[l]=count++;
                        l = ((z*l)+i)%m;
                }
                printf("Case %d: %d\n", count2, count-a[l]);
                free(a);
        }
        return 0;
}

kgduu
New poster
Posts: 2
Joined: Tue Sep 28, 2010 1:50 pm

Re: 350

Post by kgduu »

#include <stdio.h>

#define MAXN 10000

int a[MAXN];

int main()
{
int Z, I, M, L;
int count;
int tests = 0;

freopen("c:\\uva_in.txt", "r", stdin);

while (scanf("%d%d%d%d", &Z, &I, &M, &L) && (Z != 0 || I != 0 || M != 0 || L != 0))
{
memset(a, 0, sizeof(a));
count = -1;

do
{
L = ((Z % M) * (L % M) + I) % M;
a[L]++;
count++;
} while (a[L] == 1);

printf("Case %d: %d\n", ++tests, count);
}

return 0;
}

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 350

Post by sir. manuel »

This problem it's easy, i used a little hash because i am training problems with hash,,,
You have to read the problem, and see, that YOU FIRTS HAVE TO GENARATE A SEED WITH L, then you can start to cont,,,

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 350

Post by plamplam »

Just check if a number appears twice or not. Break your loop whenever a number that has previously appeared shows up again.
If the seed is given then print count and if the seed is not given then print count - 1.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Post Reply

Return to “Volume 3 (300-399)”