Page 10 of 19
Posted: Mon Jul 28, 2003 2:35 pm
by Scryer
I found your problem running under linux/gcc: the double->u32 conversion truncates downward in your inner loop on this case. I imagine the libraries are enough different that you were unlucky this time. Try modifying it as follows:
Code: Select all
u32CatsPerHat = (uint32)(dCatsPerHat + .0001);
Posted: Mon Jul 28, 2003 11:22 pm
by El-idioto
Hi Scryer,
Your the best ever! That was indeed it.
I changed the line
[cpp]
u32CatsPerHat = (uint32)dCatsPerHat;
[/cpp]
to
[cpp]
u32CatsPerHat = (uint32)floor(dCatsPerHat + 0.5);
[/cpp]
and I got accepted!
I was very surprised I didn't get accepted the first time, since I was quite convinced this was a very simple problem.
Then when I checked all the values I found on the forums (and they were correct on my machine), I was certainly at a loss.
Many thanks again!
Posted: Thu Aug 21, 2003 9:38 am
by jimmyhezhang
does the test data '1 14' make any sense?
Posted: Thu Aug 21, 2003 9:48 am
by jimmyhezhang
i
why '0 0' is the answer of '1 0'? isn't it '0 1'.
Posted: Mon Oct 06, 2003 4:36 am
by bignad98
There is an analytic solution of sorts, although i have no idea of it's efficiency. if you express the two equations with natural logs, you'll get an equation of the form N^c - N -1 = 0, where N is the number of cats in each hat and c is the ratio of the natural logs of the two input constants. You can use numerical analysis to derive an approximation for N and then use N to solve for the tree depth. However, i have no idea what the actual process is (or even if it is efficient) -- i just know it exists, because you can use a math program like Maple to solve the above equation. just thought i would throw it out -- i would love to know the details if anyone can point me in a good direction.
Posted: Mon Oct 06, 2003 9:41 am
by shamim
Here is one way to solve it.
Having the two equations:
(N+1)^x=a --(1)
N^x=b --(2)
now from (1) x=log(a)/log(N+1).
from (2) x= log(b)/log(N);
therefore log(a)/log(N+a)=log(b)/log(N);
this is an equation where N is the only unknown, with a and b as input.
It is easy to solve this using Newton's Method, as log function has a simple deravitives.
Posted: Fri Oct 10, 2003 5:09 pm
by epsilon0
this problem is stupid.
input (1,#) (where # different from 1) makes no sense.
if the top level cat has height 1, then there can be no other cat, and the top level cat is a worker cat (the only one).
thus the only acceptable (1,#) input is (1,1) and the answer is obviously 0 1.
input (#, 0) makes no sense. there are always workers cats.
either give me an explanation or i give up. this is very disappointing that the input data for this problem violates the problem statement specifications.
the problem clearly states that there is always one, and only one top level cat, and there are always worker cats also (at least 1).
help me about cat in the hat (107)
Posted: Fri Oct 17, 2003 4:00 pm
by serfan
i can't find why i am getting WA with this solution. it gives correct outputs(i think) please any one suggest me something
Code: Select all
#include<iostream.h>
int prime[25]={
2,3,5,7,11,
13,17,19,23,29,
31,37,41,43,47,
53,59,61,67,71,
73,79,83,89,97
};
int main(){
unsigned long int l,wc,N,I,nwc,sl,k,i;
while(1){
unsigned long int occ[25]={0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0
};
cin>>l>>wc;
if((l==0)&&(wc==0)) return 0;
if(l==1){
cout<<0<<1<<endl;
continue;
}
k=wc;
for(i=0;i<25;i++){
while(k%prime[i]==0){
occ[i]++;
k/=prime[i];
}
}
N=1;
for(i=0;i<25;i++)
if(occ[i]){
I=occ[i];
N*=prime[i];
}
while((l%(N+1))){///this
N*=N;
I/=2;
} ///this
nwc=1;
k=1;
for(i=1;i<I;i++){
k*=N;
nwc+=k;
}
sl=l;
unsigned long int l2=l;
k=N;
for(i=1;i<I+1;i++){
l2/=(N+1);
sl+=(k*l2);
k*=N;
}
cout<<nwc<<" "<<sl<<endl;
}
return 0;
}
107 : "Cat in The Hat" WA ... ???
Posted: Thu Oct 30, 2003 3:25 pm
by Almost Human
I got WA on this problem ...
Does anybody can help me ???
What should be the output for such input :
0 1
0 10
0 100
1 1
100 1
1000 1
10000 1
any special input I should consider ??
Posted: Thu Oct 30, 2003 7:13 pm
by Maarten
My AC program crashes on the first 3 tests; for the other tests I get the following output:
0 1
7 199
10 1999
13 19999
Hope this helps
Posted: Thu Oct 30, 2003 7:14 pm
by Maarten
Some extra tests:
input:
Code: Select all
1 1
100 1
1000 1
10000 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
1 0
64 1
0 0
output:
Code: Select all
0 1
7 199
10 1999
13 19999
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
1 1
6 127
Posted: Fri Oct 31, 2003 6:32 am
by Almost Human
I wonder why "7 199" should be the output for input "100 1"
Can anybody explain it to me, please ?
Posted: Fri Oct 31, 2003 12:12 pm
by Maarten
I think 100 1 is invalid input, since 100 is not n^3 for any n.
But my program calculates as follows: we end with one worker cat, so the number of cats inside a bigger cat should be 1. Since the first cat has height 100, the second has height 1/(1+1) * 100 = 50, the 3rd 25, and now we run into problems.
Anyway, my method of solving yields the values 7 199, but i don't think you need to consider this test case
Posted: Fri Oct 31, 2003 12:28 pm
by Almost Human
If so, I couldn't figure it out why my program keep gives me WA ....
please help
Code: Select all
#include <math.h>
#include <stdio.h>
#define maxLayer 32
int main ( void )
{
unsigned long initialHeight , numOfSmallestCat , numOfSmallerCat , layer , result1 , result2 , i ;
double catPerHat , epsilon = ( double ) 0.0001 ;
/*freopen ( "107.in" , "r" , stdin ) ;
freopen ( "107.out" , "w" , stdout ) ;*/
while ( scanf ( "%lu %lu" , &initialHeight , &numOfSmallestCat ) != EOF )
{
if ( initialHeight == 0 && numOfSmallestCat == 0 ) break ;
if ( initialHeight == 1 ) printf ( "0 %d\n" , numOfSmallestCat) ;
else
{
for ( layer = 1 ; layer <= maxLayer ; layer ++ )
{
catPerHat = pow ( numOfSmallestCat , ( double ) 1.0 / layer ) ;
if ( catPerHat - floor ( catPerHat ) > epsilon ) continue ;
if ( fabs ( pow ( catPerHat + 1 , layer ) - initialHeight ) < epsilon ) break ;
}
numOfSmallerCat = floor ( catPerHat ) ;
if ( numOfSmallerCat == 1 ) result1 = layer ;
else result1 = ( pow ( numOfSmallerCat , layer ) - 1 ) / ( numOfSmallerCat - 1 ) ;
result2 = 0 , i = 1 ;
do
{
result2 += i * initialHeight ;
if ( initialHeight == 1 ) break ;
initialHeight /= ( numOfSmallerCat + 1 ) ;
i = i * numOfSmallerCat ;
}
while ( 1 ) ;
printf ( "%lu %lu\n" , result1 , result2 ) ;
}
}
return 0 ;
}
107 The Cat in the Hat
Posted: Sat Nov 01, 2003 1:16 am
by Sajid
I got WA. I matched every inputs and outputs in this forum. any1 give some critical inputs?
what will be the maximum height of the tree?