107 - The Cat in the Hat

wsarzynski · Post by **wsarzynski** » Sat Nov 01, 2003 1:43 am

i handled case second number in pair = 1 separetly.
it seems quite different in my solution.

shamim · Post by **shamim** » Sat Nov 01, 2003 5:53 am

I ran your code on my PC and it does not pass the first sample input.

Sajid · Post by **Sajid** » Sat Nov 01, 2003 5:57 am

wsarzynski wrote:i handled case second number in pair = 1 separetly.

I did as well.

anupam · Post by **anupam** » Sat Nov 01, 2003 8:14 am

u have to check all the possibles and all the impossibles according to dm.

wsarzynski · Post by **wsarzynski** » Sat Nov 01, 2003 3:39 pm

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 · Post by **Sajid** » Sat Nov 01, 2003 5:41 pm

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 ???

wsarzynski · Post by **wsarzynski** » Sat Nov 01, 2003 7:53 pm

ok, ok, i sent my solution couple of times and it seems that
max height OF STACK is >= 10 and <= 100 millions

Sajid · Post by **Sajid** » Sat Nov 01, 2003 8:00 pm

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

but 1st tell me, is my algo ok?
thanx

wsarzynski · Post by **wsarzynski** » Sat Nov 01, 2003 8:06 pm

i suppose so:
loop to find m and height, 2 solutions are ok
then just second loop to find height of stack

Sajid · Post by **Sajid** » Sat Nov 01, 2003 8:15 pm

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".

wsarzynski · Post by **wsarzynski** » Sat Nov 01, 2003 8:49 pm

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 · Post by **Sajid** » Sun Nov 02, 2003 12:17 am

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

actually.. i did a silly mistake

But, at last get AC

Almost Human · Post by **Almost Human** » Mon Nov 03, 2003 6:59 am

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 · Post by **Almost Human** » Mon Nov 03, 2003 7:35 am

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 · Post by **Xeno** » Sat Nov 22, 2003 8:56 am

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.