## 10190 - Divide, But Not Quite Conquer!

Moderator: Board moderators

haoto
New poster
Posts: 1
Joined: Sat Oct 27, 2001 2:00 am
Location: Taipei
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

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:
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:
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:
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:
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:
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:
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:
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
Contact:
No sajid its output is
Boring!

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

### thanX

Jalal Bhaiya, thanx for ur help...

and Whinii as well.

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

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
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:
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 AC at last

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:
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. . Enjoy
Not AC yet AC at last

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
Thank you very very much for you kind reply. I have got accepted.