107 - The Cat in the Hat

[Moni]

[cpp]
#include<iostream.h>
#include<math.h>

typedef unsigned long int ulong;

int main()
{
ulong H,N;

ulong h_t = 0;

while(cin >> H >> N)
{
ulong h = H,sum = 0;

while(ceil(h)!=1)
{
sum += h * pow(N,h_t);
h *= 1.0/double(N+1);
h_t++;
}

ulong Non_worker_cat = (pow(N,h_t)-1)/(N-1);

cout << Non_worker_cat << ' ' << sum << endl;
}

return 0;
}
[/cpp]

[kmhasan]

There has been a good number of posts on this particular problem. Many critical test cases have been discussed there. It would be better if you would check your code with those I/O.

Use the search option to find posts related to 107.

[Moni]

I just want to know why can't I tell it as a tree which has degree N. And the non working cats are those which are not leaf in the tree. The sum of heights of the cats are the heigthts gained from the internal nodes.

[Arreis]

Can anyone help me? I've tried every possible input and get what think is correct, but still the compiler says "WA". Any ideas? Please?

import java.util.*;

class Main
{
public static void main(String[] args)
{
String s, salida="";
StringTokenizer tok;
long h0, wc;
long h, hu, nwc;

long hx=1;
while (!fin(s = readln()))
{
tok = new StringTokenizer(s);
h0= Long.parseLong(tok.nextToken());
wc= Long.parseLong(tok.nextToken());

int N=1, iter=0;
boolean encontrado=false;

if (h0==1)
{
nwc=0;
h=wc;
}

else
{
if (wc==1)
{
N=1;
for (int i = 1; i<1000 && !encontrado; i++)
{
if (Math.pow(2,i)==(double)h0)
{
iter=i;
encontrado=true;
}
}

}

else
{

for (int i=1; i<1000 && !encontrado; i++)
{
for (int j=1; j<1000 && !encontrado; j++)
{
if (Math.pow(i,j)==wc)
{
hx=1;
for (int k=0; k<j; k++)
{
hx *= i+1;
}

if (hx==h0)
{

N=i;
iter=j;
encontrado=true;
}
}
}
}
}

hu=h0;
h=h0;
nwc=1;
for (int i=1; i<iter; i++)
{
nwc+=Math.pow(N, i);
}

for (int i=1; i<=iter; i++)
{
h+=Math.pow(N,i)*(hu/(N+1));
hu=hu/(N+1);
}
}

salida += nwc+" "+h+"\n";
}
System.out.print (salida);
}

static boolean fin (String s)
{
return (s.length()==3 && s.charAt(0)=='0' && s.charAt(1)==' ' && s.charAt(2)=='0')?true:false;
}

static String readln()
{
char ch;
String s = new String();

try
{
ch = (char)System.in.read();

while (ch!=0 && ch!='\n')
{
s = s+ch;
ch = (char)System.in.read();
}
}

catch(Exception e)
{
System.out.println("Error");
}

return (s==null||((int)(s.toCharArray())[0])==13?null:s.substring(0,s.length()-1));
}
}

[Abednego]

Thank you, Hisoka. Your test cases have found two special conditions I didn't handle. However, there is another one that is still slipping away. Do you have more test cases? ;-) What I do is test for boundary conditions and then try all possible N with the property that (N-1) divides (i2 - 1), where i2 is the second input number.

[kate]

I've tried all the sample tests I could find and every one of them produce the correct answer but I'm still getting a WA. Any suggestions? Here is my code:

Code: Select all

#include <iostream>
#include <cmath>
using namespace std;

void main()
{
	int i, w, n, h, hc;
	int height = 1, workers=1;
	

	cin >> i >> w;
	while ((i!=0)||(w!=0))
	{
		int b = 2;
		if(w==0) {
			n = 0;
			h = 0;
		}
		else if(i==1) {
			n = 0;
			h = w;
		}
		else if (w==1) {
			n = 1;
			h = i + 1;
		}
		else
		{
			do
			{
				n=0; h=i; workers=1; height=1; 	hc = i;
				do
				{
					hc=hc/(b+1);
					n+=workers;
					height=height*(b+1);
					workers=workers*b;
					h+=hc*workers;
				} while(height<i && workers<w);
				b++;
			} while(height!=i || workers!=w);
		}
		cout << n << " " << h << endl;
		cin >> i >> w;
	}
	
}

[kate]

I just realized my solutions for "# 1" are incorrect.

[Ruberik]

I'm not quite sure I understand how contexts like (1, #) can happen. If the cat is initially of height one, should he not be the only worker? (1, 18) seems to me to be an invalid input within the constraints of the problem.

I special cased that sucker out, and my output agrees with Hisoka's now. The problem is, I've still got something wrong; and I think it must have something to do with a fundamental misunderstanding of the problem. Just to make sure I've got a vaguely correct idea, the two numbers (h and w) given must be of the form
h=n^a
w=(n-1)^a
For some n, a integers: is that correct?

I'd appreciate any input you've got.

Cheers,
Bartholomew

[amir2099]

Hi
I'm a beginner and it would be greatly appreciated if someone could tell me what the mistake in the following program is:

[cpp]

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long u64;
typedef long double ld;

ld round(ld number)
{
return (fmod(number, 1) >= 0.5f) ? ceil(number) : floor(number);
}


int main(){

u64 init_h,n_small_cat;
while (cin >> init_h >> n_small_cat)
{
if (init_h==0 && n_small_cat==0) break;
//find factorizaiton;
u64 N; u64 A; bool foundn=false;
u64 tmpi,tmpi2;
u64 maxpos=int((log(n_small_cat) / log(2)))+1;
for (int possibleA=maxpos; possibleA > 0; possibleA--)
{
tmpi2=round(pow(init_h,(1/(ld)possibleA)));
tmpi=pow(tmpi2,possibleA);
if (tmpi==init_h){
A=possibleA;
N=tmpi2-1;
break;
}
}

//cout << N << " " << A << endl;

u64 notworking=0;
u64 height=0;

for (int i=0; i < A; i++)
{
tmpi=pow(N,i);
notworking+=tmpi;
height+=tmpi*pow(N+1,A-i);
}

height+=n_small_cat;
if (n_small_cat==1){
notworking=round((log(init_h)/log(2)));
height=(1 << (notworking+1))-1;

}
if (init_h==1)
{
notworking=0;
height=n_small_cat;
}



cout << notworking << " " << height << endl;
}

return 0;
}


[/cpp]

thank you

[amir2099]

someone please help, this program is driving me absolutely nuts. I've spent so many hours on it....

[shamim]

see if u can derive the equations,

(1+N)^x=a
N^x=b

where a and b are the input and N has the meaning as described in the problem statement.

[amir2099]

(1+N)^x=a
N^x=b

where a and b are the input and N has the meaning as described in the problem statement.

Thanks for the reply,
I've already derived those equations and my program uses the property.
I've also handled every special case i could think of (i.e. N=1, etc.)

I was wondering if someone with a working program could tell me about a case which I have missed.

Thanks again

[Abednego]

Ruberik, I'm making the same assumption about the form of h and w, and I'm getting WA. So I can shed no light on that issue.

I think I can answer the (1, #) question though. If the first cat is of height 1, then it has no sub-cats, but it doesn't mean that it's the only worker. (1, 18) is the case where there are 18 worker cats, all of height 1.

[Krzysztof Duleba]

I've already tried all the tests that are on this board, all ok. However, the online judge returns "time limit exceeded" answer. Does anyone can help?
Here you have my code:

#include <iostream>
#include <cmath>

using namespace std;

unsigned long long round1000(const double x)
{
unsigned long long result=(unsigned long long)(1000*x);
if(1000*x-result>=0.5)result++;
return result;
}

unsigned long long roundd(const double x)
{
unsigned long long t=(unsigned long long)x;
if(x-t>=0.5)t++;
return t;
}

int main()
{
unsigned long long a; unsigned long long b;
do
{
cin>>a;cin>>b;
if((a>1)&&(b>1))
{
unsigned long long N=1;
double c,d;
long lc,ld, wyk;
do
{
N++;
c=log((double) a)/log((double) N+1);
d=log((double) b)/log((double) N);
lc=round1000(c);
ld=round1000(d);
wyk=roundd(c);
}while((lc!=ld)||(pow((double)N, (double)wyk)!=b));
cout<<(b-1)/(N-1)<<" ";
unsigned long long result=0;

for(int i=0;i<=c;i++)
result+=(unsigned long long)(pow((double)N,(double)i)*pow((double)N+1,c-i));

cout<<result<<endl;
}
if(a==1)cout<<"0 "<<b<<endl;
if((a>1)&&(b==1))cout<<roundd(log((double)a)/log(2.0))<<" "<<2*a-1<<endl;

}while(a!=0);
}

Thanks in advance

[Krzysztof Duleba]

No ideas? I've just made a new version which does pretty much the same, but is a bit clearer.
I guess that the problem is caused by the inner loop in which I look for such number N and exponent, that N^exponent is equal to the second given number. Is it possible that sometimes it won't end? I've tried all the inputs in quite a big range and everything was ok.

#include <iostream>
#include <cmath>

using namespace std;

inline unsigned long long roundd(const double x)
{
unsigned long long t=(unsigned long long)x;
if(x-t>=0.5)t++;
return t;
}

int main()
{
unsigned long long a; unsigned long long b;
do
{
cin>>a;cin>>b;
if((a>1)&&(b>1))
{
unsigned long long N=1;
long exponent;
do exponent=roundd(log((double) a)/log((double) (++N)+1));
while(pow((double)N, (double)exponent)!=b);

cout<<(b-1)/(N-1)<<" ";
unsigned long long result=0;

for(int i=0;i<=wyk;i++)
result+=(unsigned long long)(pow((double)N,(double)i)*pow((double)N+1,(double)exponent-i));

cout<<result<<endl;
}
if(a==1)cout<<"0 "<<b<<endl;
if((a>1)&&(b==1))cout<<roundd(log((double)a)/log(2.0))<<" "<<2*a-1<<endl;

}while(a!=0);
}