OJ Board

Posted: **Wed Apr 14, 2004 10:52 am**

lotu wrote: Now more interstinglly if I change
[cpp] if( step % i == 0 && mod % i == 0)[/cpp]

Since the point is searching for uniform distribution you should expect to get a lot of inputs with relative primes. If step and mod are relative primes the loop will iterate step-3 times.
Step may be up to 100000.

lotu wrote: to:
[cpp] if( step % i == 0 || mod % i == 0)[/cpp]

this will loop up to step only if both step and mod are prime otherwise at worst it will iterate min(sqrt(step),sqrt(mod)) times. sqrt(100000) is 316...

lotu wrote: or:
[cpp]if( step % i == 0)[/cpp]
or:
[cpp]if( mod % i == 0)[/cpp]

both will loop up to the size of the variable if prime or up to its square root in the worst case otherwise.

lotu wrote:it dosen't time out any more and finshes in less than a second
Of course the code dosen't output the correct answer then.
So what is wrong?

If judge's input is big enough and contains a lot of big relative primes it is easily seen that with the first test it may run >10x slower...

Ciao!!!

Claudio

Posted: **Thu Aug 05, 2004 12:18 am**

I think that I that a choice is a "Good Choice" if, and only if,
gcd(mod,step)==1.
Is this correct? Help plezz
Here is my code:

#include <stdio.h>

int mcd (int x, int y)
{
int residuo, aux;
if (y>x)
{
aux=x; x=y; y=aux;
}
while ( residuo!=0 )
{
residuo = x % y;
x = y;
y = residuo;
}
return (x);
}

void main ()
{
int step, mod;

while ( scanf ("%d%d%*c", &step, &mod) == 2 )
{

if ( mcd(step,mod) == 1 )
printf ("%10d%10d Good Choice\n\n", step, mod);
else
printf ("%10d%10d Bad Choice\n\n", step, mod);
}
}

Posted: **Sat Aug 07, 2004 8:59 pm**

Hmm... Try to change this lines:
[c]/* ... */
while ( scanf ("%d%d%*c", &step, &mod) == 2 )
/* ... */
printf ("%10d%10d Good Choice\n\n", step, mod);
else
printf ("%10d%10d Bad Choice\n\n", step, mod);
/* ... */[/c]
1) scanf - there is no need to read '%*c' <- this * is a bug? Any way you don't read this %*c - no pointer for that in variables list
2) you will have P.E. I think, after %10d%10d there is more than one space - %10d aligns number to left, this means the extra spaces will be added on left side of number, on right side there is 4 spaces.

Posted: **Sat Jun 18, 2005 2:26 pm**

Hi I don't know why i'm gettin PE....

Anyone do?
here's a part of my code

Code: Select all

while(scanf("%d%d",&step,&mod)==2)
{
    printf("%10d%10d%15s\n\n",step,mod,choice(step,mod));
}

Regards!

Posted: **Sat Jun 18, 2005 2:39 pm**

I think the "choice" should be left justified.

Posted: **Sun Jun 19, 2005 10:48 am**

Yes I changed it a little bit
there was one unnecessary space

now is good

Code: Select all

while(scanf("%d%d",&step,&mod)==2)
{
    printf("%10d%10d    %s Choice\n\n",step,mod,choice(step,mod));
}

where "choice" returns "Good" or "Bad"
thx man, got AC:>

Posted: **Thu Feb 23, 2006 2:04 pm**

I solve this problem using Ad Hoc algorithm and got 1.041 second, I feel there is a faster algorithm to solve it. But I don't know, is there any faster algorithm to solve the problem?

Posted: **Sun Apr 02, 2006 4:15 am**

unless you can make a faster form of seed=(seed+x)%y or can correlate the inputs to possible output...i dont hink you can decrease the time too much as for each mod value, it'll have to parse the whole 0-mod once

one possible improvement is checking if gcd of step and mod is 1
fastest way for this would be the eular's algorithm(or was it euclid's algorithm)

Posted: **Sun Nov 12, 2006 6:12 pm**

Hi, I tried to post my program twice, once I got WA then after adding the delete [] array instruction to free memory I got Runtime Error. Anyone can help and tell me what's wrong with this code? I've gone through all the test cases I could find here, and my program got them right. Is there anything wrong with the formatting of the output??? Help would be appreciated!

Code: Select all

Posted: **Sun Nov 12, 2006 6:31 pm**

Your forgeting this.

After each output test set, your program should print exactly one blank line.

cin.eof() sometimes doesn't work well (i don't know why), so instead of

Code: Select all

while (!cin.eof())

try

Code: Select all

while (cin >> step >> mod)

I think you don't need delete[] (it's causing a error. I don't know why it occurs).

----
Sory for my poor English

Posted: **Sun Nov 12, 2006 6:57 pm**

Thank you for the answer, rio. I did the changes and posted it again but this time I got a Presentation Error. The modified code looks like this:

Code: Select all

while(cin>>step>>mod)
    {
                     array = createTable(step, mod);
                     good = goodChoice(array, mod);
                     if(good) 
                     {
                              answer = "Good Choice";
                              stringl = 15;
                     }
                     else 
                     {
                          answer = "Bad Choice";
                          stringl = 14;
                     }
                     cout << setw(10) << setfill(' ') << step << setw(10) << setfill(' ') << mod << setw(stringl) << setfill(' ') << answer << "\n" <<endl;
    }
    return 0;

Posted: **Sun Nov 12, 2006 7:22 pm**

``Good Choice" or ``Bad Choice" left-justified starting in column 25

so try

Code: Select all

 cout << setw(10) << setfill(' ') << step << setw(10) << setfill(' ') << mod << "    " << answer << endl<<endl;

Read the problem caerfully.

Posted: **Sun Nov 12, 2006 7:42 pm**

Thank you a lot, it worked.

Posted: **Fri Nov 24, 2006 3:12 pm**

Can somenone plz give explanation or proof why STEP and MOD are good choices if gcd(STEP,MOD) == 1.

-Shihab

Posted: **Fri Nov 24, 2006 3:53 pm**

if gcd(STEP,MOD)==5 then all the numbers generated will be multiple of five, so they will never cover all the numbers within range.

OJ Board

408 - Uniform Generator

Re: 408 very odd infinte loop

408 - why wrong answer?

408 how to fix PE??

408 any effective method to solve the problem

WA and RE

hmm