107 - The Cat in the Hat

[galois_godel]

thank u
I've solved this problem.

[Sanghack]

Code: Select all

					// ^2
					large_n=(first_height-last_number-1)/2;
					if(large_n*large_n==last_number){
						times=2;						
					}
					else{
						calc1=log(first_height)/log(last_number);
						for(large_n=2;large_n<100000;large_n++){
							if(fabs(calc1-a[large_n])<0.000000000001) break;
						}
						times=(int)((log(last_number)/log(large_n))+0.1);
						// adjust 
					}

is the part where 'find N'...
how can I change this O(n) algorithm to O(1) algorithm?

[popel]

By Solving the Equation in Bi-Section Method.
(like Binary Search)

[Zhou Yiyan@SHU]

I change double to integer to make it work without floating_point error but failed. It still got error, but why???
[cpp]
#include <stdio.h>
#include <math.h>

#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define maxint 2147483647
#define dead 1e-15
#define abs(a) (((a)>=0)?(a):(-(a)))


#ifndef ONLINE_JUDGE
FILE *FIN=fopen("c:\\in.txt","r");
#else
FILE *FIN=stdin;
#endif
FILE *FOUT=stdout;

unsigned int trunc(double doublenum) {
return (unsigned int)floor(doublenum+0.5);
}

unsigned int root(unsigned int expo, unsigned int base) {
return trunc(pow((double)expo,1.0/(double)base));
}

unsigned int log(unsigned int num, unsigned int expo) {
return trunc(log((double)expo)/log((double)num));
}

bool isuint(double num) {
if(fabs(num-trunc(num))<1e-10) return true;
return false;
}

unsigned int pow(unsigned int a, unsigned int b) {
unsigned int i,p = 1;
for (i=0; i<b; i++) p *= a;
return p;
}

void main()
{
double fworkCat,finitHeight;
unsigned int workCat,initHeight;
unsigned int lazyCat,sumHeight;
unsigned int a,b;
unsigned int i,k,n;
double t1,t2,z;

while(fscanf(FIN,"%lf %lf",&finitHeight,&fworkCat)==2) {
initHeight=trunc(finitHeight); workCat=trunc(fworkCat);
if(initHeight==0 || workCat==0) break;
if(initHeight>maxint || workCat>maxint) while(1);

if(workCat==1) {
fprintf(FOUT,"%u %u\n",initHeight-1,initHeight*(initHeight+1)/2);
continue;
}
if(initHeight==1) {
fprintf(FOUT,"0 %u\n",workCat);
continue;
}
if(initHeight==workCat+1) {
fprintf(FOUT,"1 %u\n",initHeight+workCat);
continue;
}

//binary search k
a=0; b=min(root(workCat,2),root(initHeight,2));
do {
k=(a+b)/2;
t1=pow((double)workCat,1.0/(double)k);
t2=pow((double)initHeight,1.0/(double)k);
z=t2-t1;
if(isuint(t1) && isuint(t2) && trunc(z)==1) {
n=trunc(t1); break; }
if(z<1) b=k-1;
if(z>1) a=k+1;
}while(a<=b);

lazyCat=(pow(n,k)-1)/(n-1);
for(i=0,sumHeight=0;i<=k;i++) {
sumHeight+=pow(n+1,i)*pow(n,k-i);
}

fprintf(FOUT,"%u %u\n",lazyCat,sumHeight);
}
}[/cpp]

[Subeen]

i got the prog. WA. what's wrong with my code?
[c]code removed/c]
now I have got it AC. careful about floating point errors!!

[selnip]

if input is 1 1, output is 0 1 ? right? how?

give me the sample~

I got the wrong answer..

if input is 1 100

what is output?

[pc5971]

I have the same problem... With all this input dates the program goes Ok but I still receive WA...


[pascal]
{@JUDGE_ID: 21671JW 107 Pascal}
program p107;
const eps=1.0e-10;
var a,b,x,y:integer;
n,k,i:integer;

function verif(k:integer):boolean;
var a,b:real;
begin
a:=exp(ln(y)/k)+1;
b:=exp(ln(x)/k);
if abs(a-b)<eps then
verif:=true
else
verif:=false;
end;

begin
readln(x,y);
while not ((x=0) and (y=0)) do
begin
if (x=1) and (y=1) then
begin
a:=0; b:=1;
end
else
for i:=1 to 100 do
if verif(i) then
begin
n:=trunc(exp(ln(y)/i));
if n=1 then
a:=i
else
a:=(y-1) div (n-1);
b:=x+n*(x-y);
writeln(a,' ',b);
break;
end;
readln(x,y);
end;
end.
[/pascal]

Please give me an example for which my program doesn't go...

[pc5971]

Sorry I put the wrong programm... The correct one is:

[pascal]
{@JUDGE_ID: 21671JW 107 Pascal}
program p107;
const eps=1.0e-20;
var a,b,x,y:integer;
n,k,i:integer;

function verif(k:integer):boolean;
var a,b:real;
begin
a:=exp(ln(y)/k)+1;
b:=exp(ln(x)/k);
if abs(a-b)<eps then
verif:=true
else
verif:=false;
end;

begin
readln(x,y);
while not ((x=0) and (y=0)) do
begin
if (x=1) and (y=1) then
begin
a:=0; b:=1;
writeln(a,' ',b);
end
else
for i:=1 to 100 do
if verif(i) then
begin
n:=trunc(exp(ln(y)/i));
if n=1 then
a:=i
else
a:=(y-1) div (n-1);
b:=x+n*(x-y);
writeln(a,' ',b);
break;
end;
readln(x,y);
end;
end.
[/pascal]

[pc5971]

I have some problems with this problem too. But I found an possible cause of my problem. I also work with BP7.0 and the program work's, but when I try to compile with DJGPP the results was't the same... So I must work a little more to this problem... Can somebody tell me the range of the types (integer, real, double...) in this system ... In BP the thing's are very clear: integer are -> 32676...

Thank you because I descover this problem only after I read this topic

[Subeen]

i tried a lot by my code got WA. can anyone tell me the bug?
here is my code:

Code: Select all

cutted

finally got it AC. got some good sample IO from another post.

[knight823]

anyone can tell me what's wrong!!! thanks!!

//@BEGIN_OF_SOURCE_CODE
#include <iostream>
#include <math.h>

void main()
{
while(cin)
{
int hight,wcat,nowcat=1,allhight,M,N,test,i;
cin>>hight>>wcat;
if(hight==0&&wcat==0) break;
if(hight==1&&wcat==1)
{cout<<'0'<<" "<<'1'<<endl;continue;}

for(i=1;i<=hight;i++)
{
M=0;N=i;test=1;
while(test<hight)
{
if(test==hight) break;
else {test*=(N+1);M++;continue;}
}
if(pow(N,M)==wcat) break;
else continue;
}

allhight=hight;

for(i=1;i<M;i++)
{
nowcat+=pow(N,i);
allhight+=(pow(N,i)*(hight=hight/(N+1)));
}

cout<<nowcat<<" "<<allhight+wcat<<" "<<endl;
}
}
//@END_OF_SOURCE_CODE

[21743NX]

Hi, can any kind soul please tell me why is my code getting the wrong answer even though the I got the test inputs on the paper and those on the electronic board correct??


Below is my code

#include <stdio.h>

int main(void)
{
long tallest, workers;
long i, temp;
long multiplier, new_h, total_h, new_n, total_n;
while(scanf("%ld %ld", &tallest, &workers)==2 && (workers != 0 || tallest != 0))
{
total_h = new_h = tallest;
total_n = 1;
i = 0;

if (tallest == 0)
{
continue;
}


if (tallest == 1 && workers > 1)
{
continue;
}

if(workers == 1)
{
switch (tallest)
{
case 1 : printf("%ld %ld\n", 0, 1);
break;
case 2: printf("%ld %ld\n", 1, 3);
break;
default: break;
}
continue;

}

if ( (workers + 1) == tallest)
{
printf("%ld %ld\n", 1, tallest + workers);
}

if(workers && (tallest - workers != 1))
{
for( multiplier = 2; ; multiplier++ )
{
new_n = 1;
while(new_n <= workers/multiplier)
{
new_n *= multiplier;
}
if(new_n == workers)
{
temp = tallest;
while (temp > 1)
{
i = temp / (multiplier+1);
if ((i * (multiplier + 1)) == temp)
{
temp = i;
}
else
{
i =1;
break;
}

}

if (temp == 1)
{
i = 0;
break;
}
else
{
i = 1;
break;
}

}

}

if(i == 0)
{
new_n = 1;
new_h /= (multiplier+1);
for(; new_h > 1; )
{
new_n *= multiplier;
total_h += new_h * new_n;
total_n += new_n;
new_h /= (multiplier+1);
}

total_h += workers;
printf("%ld %ld\n", total_n, total_h);
}
}
}

return 0;
}

[Dominik Michniewski]

This code was accepted before rejudgement. After it, it is WA. Could anyone help me and show what's wrong with it ??

I'm very frustrated ....

Code: Select all

:-) sorry boys - I cut it off ...

and I found very nice input data:
if our solutions are rejected after rejudgement, try this input
2 1
4 1
1024 1
and so on
.....
output is easy to compute ....

[jpfarias]

My code is getting Time Limit Exceed, and I don't know why...
Can u send some input that it would hang forever?
Here it is:

Code: Select all

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

int pot(int a, int b) {
	int p=1;
	for (int i=0;i<b;++i) {
		p *= a;
	}
	return p;
}

int main() {
	int h, w;
	for (;;) {
		scanf("%d %d",&h, &w);
		if (!h && !w) {
			break;
		}
		if (h == 1) {
			printf("0 %d\n",w);
			continue;
		}
		if (h == w+1) {
			printf("1 %d\n",h+w);
			continue;
		}
		int n = 2;
		int k;
		while (log(w)/log((double)n)-log(h)/log((double)(n+1)) > 0.1e-15) {
			//printf("%.20lf %.20lf\n",log(w)/log(n),log(h)/log(n+1));
			++n;
		}
		int incn=1;
		for (;;) {
			//printf("%d\n",k);
			k = (int)floor(log(w)/log((double)n));
			int k1 = k-1;
			int k2 = k+1;
			if (pot(n,k) == w && pot(n+1,k)==h)
				break;
			if (pot(n,k1) == w && pot(n+1,k1)==h) {
				k = k1;
				break;
			}
			if (pot(n,k2) == w && pot(n+1,k2)==h) {
				k = k2;
				break;
			}
			if (!k) {
				incn = -1;
			}
			n+=incn;
		}
		int idle = 0, toth = 0;
		for (int i = 0; i<k;++i) {
			idle += (int)(pow(n,i));
			toth += (int)(pow(n+1,k-i) * pow(n,i));
		}
		toth += (int)pow(n,k);
		printf("%d %d\n",idle,toth);
	}
	return 0;
}

Thanx in advance!
Jo

[famousun]

#include<iostream.h>
#include<math.h>
unsigned int idl , tot;
int js(int later,int sume,int height)
{
int temp , i ,j;
for(i = 2 ; i<=later ; i++)
{
temp = (int)(log(sume)/log(i) );
if((int)pow(i+1,temp) == height)
break ;
}
for(j=1; j <= temp ; j++)
{
tot += ((int)pow(i,j)*(int)pow(i+1,temp-j));
idl += (int)pow(i,j-1);
}

return (i) ;
}
void main()
{
unsigned int height, sum2, fi;
cin>>height>>sum2 ;
int later ;
while((sum2 != 0)&&(height != 0))
{
later = (int)sqrt(sum2) ;
if(sum2 == 1)
{
idl = 0 ;
tot = height ;
}
else if(height - sum2 == 1)
{
idl = 1 ;
tot = height + sum2 ;
}
else
{
idl = 0; tot = height;
fi = js(later,sum2,height) ;
}

cout<<idl<<' '<<tot<<endl ;
cin>>height>>sum2 ;
}
}