10190 - Divide, But Not Quite Conquer!

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

haoto
New poster
Posts: 1
Joined: Sat Oct 27, 2001 2:00 am
Location: Taipei

Post by haoto »

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

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

10190: TLE.. help, plz

Post by Sajid »

i have got Time Limit Exceeded in this problem. what is the effiecient algorithm for this problem? help,. plz
Sajid Online: www.sajidonline.com

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

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
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

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

......

anyway, what's the eXceptional cases?
Sajid Online: www.sajidonline.com

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

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
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

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

any way, plz check it...

Input:

Code: Select all

0 0
0 1
1 0
1 88
88 1
Output:

Code: Select all

Boring!
Boring!
Boring!
Boring!
88
is it ok???
Sajid Online: www.sajidonline.com

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

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

any way, plz check it...

Input:

Code: Select all

0 0
0 1
1 0
1 88
88 1
Output:

Code: Select all

Boring!
Boring!
Boring!
Boring!
88
is it ok???
Sajid Online: www.sajidonline.com

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. »

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
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

sorry, still WA...

Input:

Code: Select all

1 1
Output:

Code: Select all

1
is it correct?
Sajid Online: www.sajidonline.com

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal »

No sajid its output is
Boring!
:wink:

Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

thanX

Post by Sajid »

Jalal Bhaiya, thanx for ur help...

and Whinii as well.


Jalal Bhai, dowa rakhben. :wink:
Sajid Online: www.sajidonline.com

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo »

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.
Last edited by yahoo on Mon Mar 17, 2003 7:08 am, edited 1 time in total.

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

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
Not AC yet Image AC at last Image

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier »

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

999 111
55 11
40 20
8 4
it gives me

Code: Select all

999 9
55 5
40 2
8 2
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. :P . Enjoy :wink:
Not AC yet Image AC at last Image

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo »

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

Post Reply

Return to “Volume 101 (10100-10199)”