107 - The Cat in the Hat

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

Moderator: Board moderators

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski »

i handled case second number in pair = 1 separetly.
it seems quite different in my solution.
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

I ran your code on my PC and it does not pass the first sample input.
Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

wsarzynski wrote:i handled case second number in pair = 1 separetly.
I did as well.
Sajid Online: www.sajidonline.com
anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

u have to check all the possibles and all the impossibles according to dm. :lol: :lol:
"Everything should be made simple, but not always simpler"
wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski »

in my solution i also had to change int to unsigned because of overflows,
then got accepted.
check boundary conditions, don't count to much in first loop,
you probably need 2 x if( ... ) break;
haven't noticed any other problems or tricks
Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

as far as i understood the problem, its a m-arry tree, and i had to find 'm' for the perticular dataset..
i used a loop to find m. and then, find height of the tree and so on...

i used unsigned long.

what is the maximum value of m ???
Sajid Online: www.sajidonline.com
wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski »

ok, ok, i sent my solution couple of times and it seems that
max height OF STACK is >= 10 and <= 100 millions
Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

actually, i wanted to know the "m", not the height...

but 1st tell me, is my algo ok?
thanx
Sajid Online: www.sajidonline.com
wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski »

i suppose so:
loop to find m and height, 2 solutions are ok
then just second loop to find height of stack
Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

ya, finding "m", i m calculating leaves (height is getting as well), if the number of leaves doesnt macth with the input then continue the loop. off course there is two loop. and working well .. i cant understand my fault. so, i wanted to know the maximum number of "m".
Sajid Online: www.sajidonline.com
wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

Post by wsarzynski »

it is couple of hundreds and, as i said, this does
not causes overflow problems with this algorithm.

check this:
no incorrect rounding in second loop and 1 output number computation - can be done with integer division
m must be >= 2 after you check b != 1
check both input numbers are satisfied
dont print for 0 0 case, even if only one in input
Sajid
Learning poster
Posts: 94
Joined: Sat Oct 05, 2002 5:34 pm
Location: CS - AIUB, Dhaka, Bangladesh.
Contact:

Post by Sajid »

wsarzynski,
thanx a lot .. u did help me a lot , really....

actually.. i did a silly mistake
:(

But, at last get AC
:lol:
Sajid Online: www.sajidonline.com
Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human »

Does floating point height is a valid height ???

I don't get it why "7 199" should be the output for input "100 1"

If I count :
100 <-- first height
50
25
12.5 <-- does it valid ???
6.25
3.125
Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human »

Finally, I got an AC ...

thank you for the inputs and outputs....

Actually, I was confused by the compiler.

double a = 4.0000000000, b ;

b = floor ( a ) ;

printf ( "%lf" , b ) ;

the result is 3.00000 ????
Xeno
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA

Post by Xeno »

Yay, I just solved this problem. Much credit goes to Marteen for his test cases. However, a number of them are invalid inputs, and I thought I'd clean up the list a little bit.

100 1
1000 1
10000 1
The above three are invalid because neither 100, 1000, nor 10000 = 2^x for any x (the base of the right term is 1, so the base of the left must be 1+1=2). I should note that I removed the part of my program that handled input like this and the judge still accepted it, so I know for certain that you needn't worry about it.

1 0
This case is invalid because the problem statement assures us that both integers will be positive.

So, the revised inputs/outputs are:

Input:

Code: Select all

1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1 1
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0
Output:

Code: Select all

0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
6 127
9 217
As far as I know, all the special cases are covered by that list. If you can get your program to generate that output, then it is almost certainly correct.

Edit: Added another input (81 64) that I thought would be good. It's subtly different from the others.
You're in a maze of twisty compiler features, all different.
Post Reply

Return to “Volume 1 (100-199)”