## 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
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
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:
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:
u have to check all the possibles and all the impossibles according to dm.
"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
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:
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
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:
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
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:
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
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:
wsarzynski,
thanx a lot .. u did help me a lot , really....

actually.. i did a silly mistake

But, at last get AC
Sajid Online: www.sajidonline.com
Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm
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
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
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.