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 » Sat Nov 01, 2003 1:43 am

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

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

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.
Sajid Online: www.sajidonline.com

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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

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

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 ???
Sajid Online: www.sajidonline.com

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

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

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
Sajid Online: www.sajidonline.com

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

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

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".
Sajid Online: www.sajidonline.com

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

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

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
:lol:
Sajid Online: www.sajidonline.com

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

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
New poster
Posts: 4
Joined: Mon Nov 17, 2003 2:01 am
Location: Colorado, USA

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.
You're in a maze of twisty compiler features, all different.

Post Reply

Return to “Volume 1 (100-199)”