10190 - Divide, But Not Quite Conquer!

haoto · Post by **haoto** » Tue Jan 28, 2003 6:50 pm

Nope...
I think the judge is right, because k must >1.

Sajid · Post by **Sajid** » Sun Mar 09, 2003 12:40 am

i have got Time Limit Exceeded in this problem. what is the effiecient algorithm for this problem? help,. plz

Whinii F. · Post by **Whinii F.** » Sun Mar 09, 2003 5:12 am

I think simple division algorithm is enough to handle this problem, since the algorithm's time complexity is O(log_m_n) .. So the longest run will not be longer than 31. =)

I think you don't handle some EXCEPTIONAL cases correctly..

Sajid · Post by **Sajid** » Sun Mar 09, 2003 6:18 am

Since September 28th 2002 the default CPU limit is 10 seconds.

......

anyway, what's the eXceptional cases?

Whinii F. · Post by **Whinii F.** » Sun Mar 09, 2003 8:20 am

Why don't you try to figure it out on your own?
Knowing solutions before thinking deeply doesn't have any effects. It's use for nothing.

anyway, I'll give one more hint:

Each line will consist of two "non-negative" integers n,m which are both less than 2000000000. You must read until you reach the end of file.

It's non-negative. right?

Sajid · Post by **Sajid** » Sun Mar 09, 2003 9:59 am

sorry, it's my fault. there was some problem with the input 0 and 1.

any way, plz check it...
Input:

Code: Select all

Output:

Code: Select all

Boring!
Boring!
Boring!
Boring!
88

is it ok???

Sajid · Post by **Sajid** » Sun Mar 09, 2003 10:00 am

sorry, it's my fault. there was some problem with the input 0 and 1.

any way, plz check it...
Input:

Code: Select all

Output:

Code: Select all

Boring!
Boring!
Boring!
Boring!
88

is it ok???

Whinii F. · Post by **Whinii F.** » Sun Mar 09, 2003 11:21 am

The first four are okay, the last one is not..
It doesn't end with 1, so it must be a "boring!" sequence.

Good luck =)

Sajid · Post by **Sajid** » Sun Mar 09, 2003 2:09 pm

sorry, still WA...

Input:

Code: Select all

1 1

Output:

Code: Select all

is it correct?

Jalal · Post by **Jalal** » Sun Mar 09, 2003 10:47 pm

No sajid its output is
Boring!

Sajid · Post by **Sajid** » Sun Mar 09, 2003 11:06 pm

Jalal Bhaiya, thanx for ur help...

and Whinii as well.

Jalal Bhai, dowa rakhben.

yahoo · Post by **yahoo** » Sat Mar 15, 2003 7:40 pm

I can't understand why i got wrong answer all the time in this problem. I have tested my program with all known typical test cases. Can anybody tell where my code is wrong. Thanks in advance. Here is my code:

Code: Select all

code has been remove because after some modification it got accepted.

bery olivier · Post by **bery olivier** » Sun Mar 16, 2003 12:38 am

yahoo wrote: [c]
while(1)
{
r=scanf("%lld%lld",&n,&m);
if(r==EOF) break;
[/c]

Humm,

This seems incorrect to me.

You can use
[c]
while(1)
{
r=scanf("%lld%lld",&n,&m);
if(m==EOF || n==EOF) break;
[/c]

or better :
[c]
while(1)
{
r=scanf("%lld%lld",&n,&m);
if(r!=2) break;
[/c]

But I don't really like this. Better use this, it's shorter and more safe. Moreover, you don't need to use 'r' nor a 'break'.
[c]
while(scanf("%lld%lld",&n,&m)==2)
[/c]

Hope it'll help

bery olivier · Post by **bery olivier** » Sun Mar 16, 2003 11:05 am

you must do k-1 succesive divisions to reach n = 1

You should print the results only if (n%m)!=0 until the end.
try these inputs

Code: Select all

it gives me

Code: Select all

But this gives me better outputs
[c] if(!flag || a[i-1]!=1) printf("Boring!\n"); [/c]

I just tested it and I got accepted.

. Enjoy

yahoo · Post by **yahoo** » Sun Mar 16, 2003 4:27 pm

Thank you very very much for you kind reply. I have got accepted.

OJ Board

10190 - Divide, But Not Quite Conquer!

10190: TLE.. help, plz

thanX