## 107 - The Cat in the Hat

Moderator: Board moderators

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania
I get WA, I could be having the same problem or some wacky test cases...
I tryed long long to hold the numbers, but stil WA.

Here is my code:

Code: Select all

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

#define size_t long

int getl(size_t b, size_t n){
size_t i=n*n;
int count=2;

while( (i<b)&&(i>0) ) {i=i*n; count++;}
if (i==b) return count;
else return 0;
}

int main(){
double nd;
size_t a, b, n, l, sq, idle, height;

while(scanf("%ld%ld", &a, &b)==2){
if (!a && !b) break;
if (a==1 && b==1) printf("0 1\n");
else if (a == b+1) printf("1 %ld", a+b);
else if (b==1){
l = getl(a, 2);
idle = l; height = 2*a-1;
printf("%ld %ld\n", idle, height);
}
else{
sq = (size_t) sqrt(b);
for (n=2; n<=sq; n++)
if (b%n == 0){
l = getl(b, n);
if (l && (fabs(pow(n+1,l) - a) < 0.0001)){
idle = (b-1)/(n-1);
height = b+(a-b)*(n+1);
printf("%ld %ld\n", idle, height);
break;
}
}
}
}
return 0;
}
``````
I read a, b. a = (n+1)**l and b = n**l, where n is the N in the problem and l is the number or times cats come out of hats.
Using geometric progression sums, I've come to the formulas for idle cats and total height.
the if's are for l=0, l=1 respectively n=1, which were special cases for my algorithm.
It works on sample tests and additional tests I've used, and I'm REALLY puzzeled... Understanding a problem in a natural way will lead to a natural solution

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am
Hi, jakabjr.
Try following input.

Code: Select all

``````2 1
4 1
1024 1
371293 248832
11 10
1 1
0 0``````
Output should be :

Code: Select all

``````1 3
2 7
10 2047
22621 1840825
1 21
0 1``````

And, my AC code uses double.

Best regards. yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland
In this task you have to be careful about the precision errors. Even the 1e-5 precision may not work.. There is a way to solve this task using only integer numbers - just to implement some mathematical operations using ints.
And there is no need to use big num.

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania
this is really embarrasing...
I left out a '\n' at an output case, and adding it gave me AC. numbers fit into long.
Sorry for my clumsiness
Understanding a problem in a natural way will lead to a natural solution

Luchi
New poster
Posts: 3
Joined: Thu Mar 24, 2005 4:33 pm

### 107 can you help me

can anybody give me critical inputs to check my program

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

unsigned long i , j , k , m , n , m1 , n1 , t , a , b , min , sum , pas;

void B_NULL()
{
for(i=0;i<10003;i++)
b=0;
}

void prime ()
{unsigned long N , i , j , s ;
N=100000;
s=1;a=2;
for(i=3;i<=N;i+=2)
{
for(j=0;(a[j]*a[j]<i)&&(i%a[j]!=0);j++){}
if(i%a[j]!=0) {a[s]=i;s++;}
}
return;
}

int main()
{
prime();
cin>>m>>n;
while(n||m)
{
m1=m;n1=n;B_NULL();
if(m==1) cout<<0<<' '<<1<<'\n'; else
{
for(i=0;n1!=1;i++)
{t=1;
while((n1>1)&&t)
if(!(n1/a)) t=0; else
if (n1%a) {t=0;} else {n1/=a;b++;}
}
for(i=0;(i<10003)&&!b;i++);
min=b;
for(;i<10003;i++)
if(b) if(min>b) min=b;
t=1;
for(i=1;(i<=min)&&t;i++)
{sum=1;if(!(min%i)){ for(j=0;j<10003;j++) if(b[j]) for(k=0;k<b[j]/i;k++) sum*=a[j];if(pow(sum+1,i)==m) {pas=sum;t=0;}}}
m1=0;
for(j=0;j<i;j++)
{m1+=pow(pas,j)*m;m=m/(pas+1);}
n1=0;
for(j=0;j<i-1;j++)
{n1+=pow(pas,j);}
cout<<n1<<' '<<m1<<'\n';
}
cin>>m>>n;
}

return 0;
}

jakabjr
Learning poster
Posts: 56
Joined: Wed Mar 23, 2005 9:21 pm
Location: Timisoara, Romania
Try following input.
2 1
4 1
1024 1
371293 248832
11 10
1 1
0 0
Output should be :
1 3
2 7
10 2047
22621 1840825
1 21
0 1

Also see the topic just below yours, from Apr 06, and find out how to solve without tables[/code]
Understanding a problem in a natural way will lead to a natural solution

nebel
New poster
Posts: 4
Joined: Sun Apr 10, 2005 3:19 pm
Location: Kiev, Ukraine
Contact:

### Tests to 107

can somebody give me some test with answers to thу 107th problem ?

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

### some question on problem 107

I am trying to solve 107 using long long and I am getting WA.
should I use double , since the problem clarifies that it has to do with integers?

more over I saw in the forum the sample input 11 10 ,
with the output 1 21.

Is it valid input? As far as for the input pair a b there should be integers n , m such that a=(n+1)^m and b=n^m it looks like invalid to me and anyway I don't understand how it comes this specific output.

Thanks in advance for any help.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Yes, that input is valid, that is N = 10, a big cat with 10 cats in it's hat, thus their weights are 11 * 1 / (N + 1) == 1.

I used real type in PASCAL in my AC solution..., best regards,

Yandry.

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
In my AC solution I used long long when the input fit into a long long,
otherwise I used a simple form of biginteger.
Bottom line is, you have to handle those large inputs with something else than a long long.

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece
It was stupid from me that I didn't consider the powers in 1 .
I am AC now.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### hints for 107. TLE

I got AC. but..

at first, i got TLE ( 0:10.068 ; CPU )
only i use the log10, pow math functions.

but, when change the my code ( pow -> my function )

i got AC ( 0:05.619 ; CPU )

;; careful floating point and math functions. ;;

follow code is my pow function

Code: Select all

``````inline unsigned int pow2( unsigned int x, unsigned int y )
{
register unsigned int ret = 1 ;
register unsigned int loop;

for (loop=0 ; loop < y ; loop++)
ret *= x ;

return ret ;
}
``````

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

### Re: hints for 107. TLE

Gaolious wrote:I got AC. but..
but, when change the my code ( pow -> my function )

i got AC ( 0:05.619 ; CPU )
I was just wondering... Try using a pow function that runs in O( lg n ) time, but uses recursion which is sooo slow. What running time will you get ?

Code: Select all

``````typedef unsigned int uint;

uint power( uint b, uint e )
{
if( e == 0 ) return 1;
if( e == 1 ) return b;
if( e & 1 ) return b * power( b, e - 1 );

uint tmp = power( b, e >> 1 );
return tmp * tmp;
}
``````
Of course e ( exponent ) will never be greater that 32 or so, but i think it will eventually have an impact on the running time ( possibly worse )...

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

### got AC.

got AC when use the your power function.

time is 0:06.000(CPU).

sk
New poster
Posts: 2
Joined: Fri Jun 17, 2005 3:07 pm

### Help 107!!!

#include<stdio.h>
main(){
unsigned int n,m,i,j,a,b,t,t2,t3;
while(1){
scanf("%u %u",&n,&m);
if(n==0&&m==0)break;
if(n==1)printf("0 1\n");
else if(m==1){
a=b=0;
do{
b+=n;
n>>=1;
a++;
}while(n);
a--;
printf("%u %u\n",a,b);
}
else{
for(i=2;i<=m;i++){
t=m;
if(t%i==0){
while(t>1){
if(t%i)break;
t/=i;
}
if(t==1&&n%(i+1)==0)break;
}
}
a=b=0;
t2=i+1;
t=m;
do{
t/=i;
a+=t;
}while(t);
t=1;
do{
b+=t*n;
n/=t2;
t*=i;
}while(n);
printf("%u %u\n",a,b);
}
}
return 0;
}

Help I don't know why it is WA
I have try all I/O that have been given in this forum,and I've passed it all