## 107 - The Cat in the Hat

Moderator: Board moderators

safayat rahaman
New poster
Posts: 2
Joined: Sun Jul 29, 2007 7:09 am
Location: DHAKA
here is my code_

Code: Select all

``````#include<stdio.h>

#include<math.h>
long power(long,long);
main()
{
long arr;

long a,pwr,b,c,d,e,i,flag,n,flag1,n1,h2;
long j,wm,h,h1,NWM,H;
arr=1;
arr=2;
i=1;
for(j=3;j<10000;j=j+2)
{
for(a=1;arr[a]<=sqrt(j);a++)
{
if(j%arr[a]==0)break;
}
if(arr[a]>sqrt(j))
{i=i+1;
arr[i]=j;

}
}
for(;;)
{
scanf("%ld%ld",&wm,&h);
if(wm==0&&h==0)break;
if(h==1)
h2=wm;
else
h2=h;

n=1;b=0;flag1=0;n1=1;
if(wm-h>1&&h!=0)
{
for(a=1;arr[a]<=sqrt(h2);a++)
{
for(c=1;h2%arr[a]==0;c++)
{h2=h2/arr[a];
if(c==1)
n=arr[a]*n;
if(flag1==0)
b++;
}
if(b!=0)flag1=1;
if(h2==1)
break;
}
if(h2!=1)
n=n*h2;
if(power(n+1,b)!=wm)
{n1=n;
for(c=1;c<=b;c++)
if(b%c==0)
{
n=power(n1,c);
pwr=b/c;
if(power(n+1,pwr)==wm)
{b=pwr;break;}
}
}

if(h==1){NWM=b;n=1;}
else
NWM=(h-1)/(n-1);
}
if(wm!=h&&h!=0)
{if(wm-h==1)
{NWM=1;b=1;n=h;}
H=power(n+1,b+1)-power(n,b+1);
}
else
{
if(wm==h==1)
{
NWM=0;
H=1;
}
if(h==0)
{
NWM=1;
H=wm;
}
}
printf("%ld %ld\n",NWM,H);

}
return 0;
}
long power(long n,long m)
{
long sum,a;
sum=1;
for(a=1;a<=m;a++)
sum=sum*n;
return sum;
}
``````

DiogoPimenta
New poster
Posts: 5
Joined: Fri Aug 10, 2007 10:44 am
Location: Portugal
Contact:
I'm getting WA too and my code calculates good anwsers on the examples given in the forum.
Can someone provide test inputs and AC results ?? So i can see if i'm getting any WA.

I also saw many AC posts that give answer to wrong input, I dont want that kind of input for my tests !!

Thanks

DiogoPimenta
New poster
Posts: 5
Joined: Fri Aug 10, 2007 10:44 am
Location: Portugal
Contact:

I don't have math skills, so i try to solve this just using integers.

I find N and k (number of cat "generations") by cheking the reminders.

for the example input

216 125

I calculate like this

(N = 2)

216 % 2+1 = 0
125 % 2 = 1 // This reminder as to be 0 there is no such this as a HalfCat -> next N

(N=3)
216 % 3+1 = 0
125 % 3 = 2 // next N

... and so on

(N=5)
216 % 5+1 = 0
125 % 5 = 0

Here a possible N is found so we try to get to the end of the tree getting valid results and getting k as well

k = 1

216 / 5+1 = 36
125 / 5 = 25

Using same method now with the results

36 % 5+1 = 0
25 % 5 = 0 // if one of these were != 0 will would have to try next N

k++

36 / 5+1 = 6
25 / 5 = 5

6 % 5+1 = 0
5 % 5 = 0 // if one of these were != 0 will would have to try next N

k++

6 / 5+1 = 1
5 / 5 = 1

Ok! N = 5 and k = 3

if I don't get a result 1 and 1, and one of them is less than 1, then we will have to try another N

Still i get WA on the judge.
I've tested all input examples on the forum on another posts, and still my code calculates all corrected.

So please, provide me with some test inputs because i can't find no one with AC code that gets diferent anwsers than mine.

Thanks

DiogoPimenta
New poster
Posts: 5
Joined: Fri Aug 10, 2007 10:44 am
Location: Portugal
Contact:
I get same output, and still i get WA!!! Do you have more inputs to test ??

My code does not give an anwser when a bad input like 100 1 is given, and it doesn't loop forever, simply get to the next input. AND STILL I GET WA... provide-me with inputs please...

DiogoPimenta
New poster
Posts: 5
Joined: Fri Aug 10, 2007 10:44 am
Location: Portugal
Contact:
I get WA.

I've tested all inputs on the post and get the same anwsers, but i'm ignoring bad inputs like.

3 1
100 1
25 60
9 9

Thanks

DiogoPimenta
New poster
Posts: 5
Joined: Fri Aug 10, 2007 10:44 am
Location: Portugal
Contact:
Is

1 14

a valid input ??

krap
New poster
Posts: 4
Joined: Wed Aug 29, 2007 3:52 pm
Location: Thessaloniki, Greece
Contact:
I seem to get RTE too. Here is my code so if anybody sees something wrong, let me know guys!

Code: Select all

``````#include <stdlib.h>
#include <iostream.h>
#include <math.h>

int main()
{

unsigned int initialCatsHeight;
unsigned int nofWorkingCats;

int upperLimit = 200;
int allInputs ;
int inputCount = 0;
char input;

do
{
cin.getline( input, 50 );

char integer1;
char integer2;
bool otherString = false;
int j = 0;

for ( unsigned int i = 0; i < strlen( input ); i++ )
{
if ( input[i] == ' ' )
{
integer1[j] = '\0';
otherString = true;
j = 0;
}
else if ( otherString == false )
{
integer1[j] = input[i];
j++;
}
else
{
integer2[j] = input[i];
j++;
}
}

integer2[j] = '\0';

allInputs[inputCount]  = atoi( integer1 );
allInputs[inputCount]  = atoi( integer2 );

inputCount++;
}
while ( allInputs[inputCount - 1]  != 0 && allInputs[inputCount - 1]  != 0 );

for ( int i = 0; i < (inputCount - 1); i++ )
{
initialCatsHeight = allInputs[i];
nofWorkingCats = allInputs[i];

if ( initialCatsHeight == 1 && nofWorkingCats == 1 )
{
cout << "0 1" << endl;
}
else
{
unsigned int nofNotWorkingCats = 1;
unsigned int totalHeight = initialCatsHeight + nofWorkingCats;

int catsInHat;
int nofDifferentHeights;

for ( int i = 2; i <= upperLimit; i++ )
{

float r;
float t;

float exponent = 1.0 / ( float )( i - 1 );

r = pow( nofWorkingCats, exponent );
t = pow( initialCatsHeight, exponent );

if ( t == r + 1 )
{
catsInHat = ( int )r;
nofDifferentHeights = i;
break;
}

if ( i == upperLimit )
{
}
}

{
for ( int i = 1; i <= ( nofDifferentHeights - 2 ); i++ )
{
nofNotWorkingCats += ( float )pow( catsInHat, i );
}

double temp = 0.0;

for ( int i = 1; i < ( nofDifferentHeights - 1 ); i++ )
{
double base = ( double )catsInHat / ( double )( catsInHat + 1 );
temp += pow( base, i );
}

if ( ( temp - abs( temp ) ) != 0 )
{
double temp2 = temp * pow( 10.0, 9.0 );
double fraction = temp2 - abs( temp2 );

if ( fraction >= 0.5 )
{
fraction = ceil( fraction );
}
else
{
fraction = floor( fraction );
}

temp = abs( temp2 ) + fraction;
temp = temp * pow( 10.0, -9.0 );
}

totalHeight += ( unsigned int ) ( temp * initialCatsHeight );
cout << nofNotWorkingCats << " " << totalHeight << endl;
}
}
}
}
``````
Rather be a thinker than a casuist

krap
New poster
Posts: 4
Joined: Wed Aug 29, 2007 3:52 pm
Location: Thessaloniki, Greece
Contact:
Well you can see it as a tree but I believe that the total height is formed by both internal and external nodes.

Anyhow by having a glance at your code I could't understand what you're doing!

Would you mind extending in natural language?

Be well
Rather be a thinker than a casuist

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am
You have rounding error, try adding/subtracting a small epsilon.

mwiley63
New poster
Posts: 2
Joined: Mon Jan 28, 2008 9:21 pm

### Need help understand my comipler (Dev C++ 4.9.9.2)

I solved problem number 107 mathematically and fell apart when I came to testing my code in Dev C++. So I did some looking around on the forums and realized that it could have been due to my compiler as to why my numbers seemed incorrect.

So I decided to submit the problem to the online judge just to see what would happen, and I got an AC much to my surprise. I then uploaded the code to my school's ssh server, and it compiled fine on there running gcc 4.2.1 with the correct outputs.

This raises two questions.

Does the compiler used by Dev C++ treat unsigned shorts and longs different then the compiler used by the judge? Or is it functions from the math library that are treated differently such as pow? Could someone explain this to me?

I tried to download the gnu 4.1.2 compiler off the web and I am on windows. I could not figure out how to untar the compiler file in windows or how I would get dev C++ to use it. If anyone could offer me any help with this, I would appreciate it greatly.

kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Contact:

### TLE in 107(cats in hats)

thanx jan vi I solved the problem without using double.
one trick:::for those who cudnt solve it yet.
workers cat may be 1 and the height of the largest cat may be more than 1 (actually any number)...

Code: Select all

``````2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
0 0
``````
etc.
if anyone still cudnt get the trick pm me...i will explain more.
output

Code: Select all

``````1 3
1 4
2 7
2 8
2 10
2 11
3 15
3 16
3 18
``````
Last edited by kbr_iut on Thu Sep 18, 2008 6:34 pm, edited 4 times in total.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: WA in 107

You can solve it using integer arithmetic only. However, there are many cases given in the board. Try them.
Ami ekhono shopno dekhi...
HomePage

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

### Re: Need help understand my comipler (Dev C++ 4.9.9.2)

sorry..pretty late

windows doesn't works fine with long long (even with long?)... I think it exists something like "int64"...
There is no knowledge that is no power.

m.kavakebi
New poster
Posts: 2
Joined: Sat Dec 05, 2009 3:01 am

### Re: 107 WA help plz.. :-(

in case input is (x 1)
x must be powers of 2
so
this inputs are invalid
100 1
1000 1
10000 1

katagalan
New poster
Posts: 1
Joined: Thu Aug 12, 2010 12:00 pm

### 107 WA

I got WA with this code in 107 The Cat in the Hat problem. I use arithmetic solution for worker cat > 1 cases and deal separately when worker cat number is 1. My code generates right answers with below input data. So I can't figure out where gone wrong, does somebody know? Thanks!!

Code: Select all

``````#include <stdio.h>
#include <math.h>

long int h, nx;

long int findn(void);

int main(){
long int n;

while( scanf("%ld %ld", &h, &nx) != EOF){
if( h==0 && nx==0 )
break;
else{
if( h == 1 && nx != 1 )
printf("1 %ld\n", nx);
else if( nx == 1 ){
n = 1;
printf("%ld %ld\n", (long int)log2(h), ((h-nx)*(n+1))+nx);
}
else{
n = findn();
printf("%ld %ld\n", (nx-1)/(n-1), ((h-nx)*(n+1))+nx);
}
}
}/*while input data*/

exit(0);
}

long int findn(void){
long int i;
float x1, x2;
float nsqr;

nsqr = sqrt(nx);
for(i=2; i<=nsqr; i++){
x1 = log(nx)/log(i);
x2 = log(h)/log(i+1);
if( x1 == x2 )
return i;
}

return nx;
}
``````
Input:

Code: Select all

``````1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
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
29524 4017157
615441 1931252289
21 369
6 127
9 217``````