107 - The Cat in the Hat

[jakabjr]

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...

[tan_Yui]

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]

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]

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

[Luchi]

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[10003] , b[10003] , 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[0]=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]

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]

[nebel]

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

[Grazyna]

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]

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]

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]

Thanx for reply.
It was stupid from me that I didn't consider the powers in 1 .
I am AC now.

[Gaolious]

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]

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]

got AC when use the your power function.

time is 0:06.000(CPU).

[sk]

#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
Please help me
Thx !!