107 - The Cat in the Hat

[C8H10N4O2]

Always assume that since the problem has been solved, the input set is within specification. Are you using floating point?

[ftomi]

I'm using one.

[Stefan Pochmann]

I've just seen your constant there. You hopefully don't rely on this constant being slightly larger than 1? Because this constant will be used as exactly 1. Look at this code:

Code: Select all

int main () {
  double d = 1.000000000000001;
  double e = 1.00000000000000000000000000000001;
  printf( "%e %en", d-1, e-1 );
}

The output is "1.110223e-15 0.000000e+00". This is because the distance between the leftmost and rightmost 1-bit is too large for a double. Note that I already made d as long as possible. If I insert one more 0, then output is "0.000000e+00 0.000000e+00"

[ram]

Here is my latest code. And it works absolutely OK on all test cases. But I am getting wrong answer.

Code: Select all

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

using namespace std; 

double round(double num)
{
   if(ceil(num)-num<num-floor(num))
	    return ceil(num);
        else
	    return floor(num);
}

int main(){ 

double inht,workn,finht,N; 
double gen,number,i; 
while(cin>>inht>>workn){ 
if(inht==0&&workn==0) break; 
if(inht!=1) 
{ 
gen=1; 

while((pow(inht,1/gen)-pow(workn,1/gen)-1)>0.000000000001||round(pow(inht,1/gen))-(int)(pow(inht,1/gen)+0.0005)>0.00000000001||round(pow(workn,1/gen))-(int)(pow(workn,1/gen)+0.0005)>0.00000000001) 
gen++; 


N=pow(workn,1/gen); 
number=0; 
finht=0; 

for(i=0;i<gen;i++) 
{ 
finht+=inht*pow((1/(N+1)),i)*pow(N,i); 
number+=pow(N,i); 
} 
finht+=inht*pow((1/(N+1)),i)*pow(N,i); 

} 
else 
{ 
number=0; 

finht=1*workn; 
} 

cout<<setiosflags(ios::fixed)<<setprecision(0)<<number<<" "<<finht<<endl; 
} 

return 0; 
} 

I use VC++/Windows. Can any body help me with a test case thats fails my program.
Thanx.

[Stefan Pochmann]

Ok, this is the last time I say this, I swear: Please get yourself a good mail program or configure yours correctly. Please don't take this personally, but this has been said way too often now...

I just got your program accepted! Without any changes!

You can also look at the thread I started last week in "Misc" with the screaming title "ATTENTION!...".

[ram]

Stefan,

It just got accepted. thanx a lot. I usually use my university's mail program and it never gave me trouble, thats the reason I didnt even suspect this. hmmm, I guess I would go UNIX now.

[mafattah]

I solved the problem right, but I had time limit exceeded error. I do not see how I could get such an error (except if the number of worker cats is a prime number).

[C8H10N4O2]

Rule #1, if the judge says your answer is wrong, your solution is most likely incorrect in someway. As most Computer Scientists know, proving correctness is mighty difficult. I suggest that if you are using floating point to make sure you are incorporating epsilon. Also, make sure your input works well with files. Try piping the sample test file into your program. Please post more specifics if you need more detailed help.

[mafattah]

I have tried the program on the given test sample, once using keyboard for input, then indirecting the input from a file, and the answer was correct in the two times.

Here is the code:

Code: Select all

 #include <fstream.h>
#include <math.h>

int levels(int num, int& span) {
	int n=0;
	bool finished = false;
	while(!finished) {
		n++;
		long x = log(num)/log(n);
		int y = int(x+0.5);
		if (num==pow(n, y)) { // n is a valid N
			span = n;
			return y;
		}
	}
}

void cats(int cat1h, int line1, int& notworking, int& height) {
	int N;
	int k = levels(line1, N);
	notworking = (pow(N, k)-1)/(N-1);

	height = 0;
	int levheight = cat1h;
	for (int i = 0; i <= k; i++) {
		height += levheight*pow(N, i);
		levheight = levheight/(N+1);
	}
}

void main() {

	int cat1h, line1, notworking, height;
	cin >> cat1h >> line1;
	while (cat1h != 0 || line1 != 0) {
		cats(cat1h, line1, notworking, height);
		cout << notworking << ' ' << height << endl;
		cin >> cat1h >> line1;
	}

I do not see the bottleneck that may cause a 'time limit exceeded'. I did not get a wrong output, but time limit exceeded error.

[C8H10N4O2]

Usually TLE is caused by infinite loop. For example, what if return y is never called? Time limit exceeded
[cpp]int levels(int num, int& span) {
int n=0;
bool finished = false;
while(!finished) {
n++;
long x = log(num)/log(n);
int y = int(x+0.5);
if (num==pow(n, y)) { // n is a valid N
span = n;
return y;
}
}
} [/cpp]

[popel]

Your program is not efficient. To realize this give inputs
483736625
481890304
The output should be 615441 1931252289.

In this problem,your main task is to solve the equation :
log(x+1)/log(x)=log(i)/log(w) in an efficient process.

as i and w is given the right part is a constant (=k)
x must be>1 and the left part is always >1.As x increases, it decreases,
and lim log(x+1)/log(x) =1
x->infinity
The lowese possible value of x is 2. log3 / log2=1.584962501...
log(3^p)/log(2^p) = p (log3) / p (log2) = log3 / log2
but if p!=1, 3^p - 2^p !=1

So, f:N->N (x)=log(x+1)/log(x)
never has any pick,the values of f(x) are sorted.

This implies that ,we can easily apply Bisection method to solve the equation, which we always use to search a criteria in a sorted array,named Binary Search.

Now,
1.Use Binary search process to find the root in a predefined interval,
such as [2,10e100].
2.Use double for calculation and show output using ".0lf"

[Betovsky]

hmm i dont know where the error is
to the exmples it works great , but the judge keeps saying WA
i also tryed with doubles...

[c]

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

int main(){
long long unsigned height, n_workers, i, n_cats, n, h_total, h;

scanf("%Lu %Lu", &height, &n_workers);

while( (height | n_workers) != 0 ){
if(height == (n_workers+1) ){
printf("%d %Lu\n", 1, (height+n_workers));
}else{
for(i=2;i<=sqrt(n_workers);i++){
if(height%(i+1) != 0) continue;
h=height/(i+1);
h_total=height;
n_cats=1;
for(n=i;n<n_workers;n=n*i){
if(h%(i+1) != 0) break;
h_total=h_total+(h*n);
h=h/(i+1);
n_cats=n_cats+n;
}
if(n==n_workers){
h_t

iotal+=n_workers;
break;
}
}
printf("%Lu %Lu\n", n_cats, h_total);
}
scanf("%Lu %Lu", &height, &n_workers);
}
return 0;
}

[/c]

Thx

[Revenger]

It's veru strange that this program gets WA. May be there are big numbers in input?(As 10e50?)

[pascal]Program p107;

Var H,Work,P,i,t : integer;
S,Sa,Cur,j : integer;

Function Check(N : integer) : boolean;
Var Res,i,j,k : Integer;
begin
Res:=Round(Exp(ln(H)/(N+1)));
j:=1;
for i:=1 to N+1 do j:=j*Res;
P:=Res;
Res:=Round(Exp(ln(Work)/(N+1)));
k:=1;
for i:=1 to N+1 do k:=k*Res;
Check:=(j=H)and(k=Work);
end;

begin
While True do begin
Readln(H,Work);
if H=0 then break;
for i:=100 downto 1 do
if Check(i) then begin
t:=i;
break;
end;
S:=0; SA:=0;
for j:=1 to t+2 do begin
if j=1 then Cur:=1 else begin Cur:=Cur*(P-1); H:=H div P; end;
SA:=SA+Cur*H;
S:=S+Cur;
end;
S:=S-Work;
Writeln(S,' ',SA);
end;
end.[/pascal]

[..]

hm........are you sure that the floating point operation has no error?
I know someone uses floating point opearation, but get WA becuase of floating point error.........

[Archangel]

I try may input but still got wrong answer !!
Can anyone help me??
#include<stdio.h>

unsigned int height,one_num,temp,count,i,j,non_work,total_height,temp2;
int power_check,power_check2;

main()
{

while(scanf("%d %d",&height,&one_num) != 0)
{ if((height == 0)&&(one_num == 0)) /* end of input */
break;
if((one_num == 1)||(height == 1))
printf("0 %d\n",height);
else
{
for(i=2;i<=one_num;i++)
{
if(one_num % i == 0)
{
power_check = 1;
count = 1;
temp = one_num;
while(temp / i != 1) /* check if the second number is i's power((i)^a) */
{
if (temp % i != 0)
{
power_check = 0; /* not */
break;
}
temp = temp / i;
count++;
}
power_check2 = 0;
if((power_check == 1)&&(height % (i+1) == 0)) /* check if the first number is i's power((i+1)^a) */
{
power_check2 = 1;
temp = height;
while(temp / (i+1) != 1)
{
if (temp % (i+1) != 0) /* not */
{
power_check2 = 0;
break;
}
temp = temp / (i+1);
}
}
if(power_check2 == 1) /* answer found */
break;
}
}
temp = 1;
temp2 = one_num;
non_work = 0;
total_height = 0;
for(j=1;j<=count;j++) /* count total height and number of non-worked cats */
{
one_num = one_num / i;
non_work = non_work + one_num;
temp = temp*(i+1);
total_height = total_height + one_num * temp;
}
printf("%d %d\n",non_work,total_height+temp2);
}
}

}