107 - The Cat in the Hat
Moderator: Board moderators
HELP 107 WA
I pass every possible inputs I think. However I still get WA
Could anyone tell me what's wrong?
thanks.
[cpp]#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
void solve(double,double);
void divs(double,double&,double&);
double gcd(double,double);
int main() {
double n,k;
//FILE* fp = fopen("C://input.dat","r");
//fscanf(fp,"%d %d",&n,&k);
cin>>n>>k;
//cout<<n<<k;
while(n!=0 || k!=0) {
//cout<<n<<k;
solve(n,k);
//fscanf(fp,"%d %d",&n,&k);
cin>>n>>k;
}
//system("PAUSE");
return 0;
}
void divs(double n,double& ans,double& times) {
if(n==1) {
ans =1;
times =1;
}
int tmp[2][10] ={0};
int k=2;
int i=0;
while(n!=1) {
if(((unsigned long)n%k)==0) {
tmp[0][i]=k;
tmp[1][i]++;
n/=k;
}
else {
if(tmp[0][i]!=0) {
i++;
}
k++;
}
}
ans =1;
for(int j=0 ; j<=i ; j++) {
ans *= tmp [0][j];
}
times = tmp[1][0];
}
double gcd(double a, double b ){
return b==0 ? a : gcd( b, (unsigned long)a%(unsigned long)b);
}
void solve(double first,double total) {
double ans1,ans2=0;
double k,times,k1,times1;
if(first ==1) {
cout<<"0"<<" "<<total<<endl;
return;
}
divs(first,k,times);
divs(total,k1,times1);
if(total!=1) {
double gcd1 = gcd(times,times1);
k = (double)pow((double)k,(double)(times/gcd1));
times = gcd1;
}
double r= k-1;
if(r!=1)
ans1 = (double)((pow((double)r,(int)times)-1)/(r-1));
else
ans1 = times;
for(int i=0 ; i<=times ; i++) {
ans2+=(double)(first*pow((float)r,i));
first/=k;
}
cout<<(int)ans1<<" "<<(int)ans2<<endl;
}[/cpp]
Could anyone tell me what's wrong?
thanks.
[cpp]#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
void solve(double,double);
void divs(double,double&,double&);
double gcd(double,double);
int main() {
double n,k;
//FILE* fp = fopen("C://input.dat","r");
//fscanf(fp,"%d %d",&n,&k);
cin>>n>>k;
//cout<<n<<k;
while(n!=0 || k!=0) {
//cout<<n<<k;
solve(n,k);
//fscanf(fp,"%d %d",&n,&k);
cin>>n>>k;
}
//system("PAUSE");
return 0;
}
void divs(double n,double& ans,double& times) {
if(n==1) {
ans =1;
times =1;
}
int tmp[2][10] ={0};
int k=2;
int i=0;
while(n!=1) {
if(((unsigned long)n%k)==0) {
tmp[0][i]=k;
tmp[1][i]++;
n/=k;
}
else {
if(tmp[0][i]!=0) {
i++;
}
k++;
}
}
ans =1;
for(int j=0 ; j<=i ; j++) {
ans *= tmp [0][j];
}
times = tmp[1][0];
}
double gcd(double a, double b ){
return b==0 ? a : gcd( b, (unsigned long)a%(unsigned long)b);
}
void solve(double first,double total) {
double ans1,ans2=0;
double k,times,k1,times1;
if(first ==1) {
cout<<"0"<<" "<<total<<endl;
return;
}
divs(first,k,times);
divs(total,k1,times1);
if(total!=1) {
double gcd1 = gcd(times,times1);
k = (double)pow((double)k,(double)(times/gcd1));
times = gcd1;
}
double r= k-1;
if(r!=1)
ans1 = (double)((pow((double)r,(int)times)-1)/(r-1));
else
ans1 = times;
for(int i=0 ; i<=times ; i++) {
ans2+=(double)(first*pow((float)r,i));
first/=k;
}
cout<<(int)ans1<<" "<<(int)ans2<<endl;
}[/cpp]
107- The cat in the Hat. TLE. Inputs and outputs are ok!!!!!
ok...I am a beginner so my code is surely ugly and ineficient... but I don't understand what I have to do in this particular case because I have test all the sample input and output, and all the inputs/outputs that I have read in this forum and it seems to be ok....maybe I am forgetting some special case or something like this.
if any one can help me I would be eternallly grateful!!
Here is my code:
[c]
#include <stdio.h>
#include <math.h>
int main()
{
double height,workers,t,i,cant=1,temp,alt=0,x,n;
empieza:
cant=1, alt=0;
scanf("%lf %lf", &height, &workers);
if (height==0 && workers==0)
return 0;
else if (height==1 || height==0)
{
printf("0 %.0lf\n", workers);
goto empieza;
}
else
{
temp=height;
for (n=1; n<=4000; n++)
{
t=n;
for (i=1; i<=30; i++)
{
if (n*t==workers)
{
if (pow(n+1,i+1)==height)
{
for (x=1; x<i+1; x++)
{
temp=temp/(n+1);
cant+=pow(n, x);
alt+=pow(n,x)*temp;
}
printf("%.0lf %.0lf\n", cant, alt+height+workers);
goto empieza;
}
else
t=n*n;
}
else
{
for (t=1; t<=4000; t++)
{
for (x=1; x<=30; x++)
if (pow(t+1,x)==height)
{
if (pow(t,x)==workers)
{
for (n=1; n<x; n++)
{
temp=temp/(t+1);
cant+=pow(t, n);
alt+=pow(t,n)*temp;
}
printf("%.0lf %.0lf\n", cant,alt+height+workers);
goto empieza;
}
}
}
}
}
}
}
}
[/c]
any suggestions
if any one can help me I would be eternallly grateful!!

Here is my code:
[c]
#include <stdio.h>
#include <math.h>
int main()
{
double height,workers,t,i,cant=1,temp,alt=0,x,n;
empieza:
cant=1, alt=0;
scanf("%lf %lf", &height, &workers);
if (height==0 && workers==0)
return 0;
else if (height==1 || height==0)
{
printf("0 %.0lf\n", workers);
goto empieza;
}
else
{
temp=height;
for (n=1; n<=4000; n++)
{
t=n;
for (i=1; i<=30; i++)
{
if (n*t==workers)
{
if (pow(n+1,i+1)==height)
{
for (x=1; x<i+1; x++)
{
temp=temp/(n+1);
cant+=pow(n, x);
alt+=pow(n,x)*temp;
}
printf("%.0lf %.0lf\n", cant, alt+height+workers);
goto empieza;
}
else
t=n*n;
}
else
{
for (t=1; t<=4000; t++)
{
for (x=1; x<=30; x++)
if (pow(t+1,x)==height)
{
if (pow(t,x)==workers)
{
for (n=1; n<x; n++)
{
temp=temp/(t+1);
cant+=pow(t, n);
alt+=pow(t,n)*temp;
}
printf("%.0lf %.0lf\n", cant,alt+height+workers);
goto empieza;
}
}
}
}
}
}
}
}
[/c]
any suggestions
107 TL in CATS
Help! Need a LITTLE help. I have got TL in problem 107 (about cats and hats). Maybe my algorithm is really slow?
I present height of initional cat as prime numbers degrees. After than finding all possible n's
[pascal]
program zzz;
var i,j,k,m,s,min,gcd : longint;
h,num,l,sum,r,n,t : int64;
p,x : array [1..100000] of longint;
procedure faht(h : int64);
var i,s : longint;
begin
fillchar(x,sizeof(x),0);
m := 0;
s := trunc(sqrt(h))+1;
for i := 2 to s do begin
if h mod i = 0 then begin
inc(m);
p[m] := i;
end;
while h mod i = 0 do begin
h := h div i;
inc(x[m]);
end;
end;
if h > 1 then begin
inc(m);
p[m] := h;
x[m] := 1;
end;
if m = 0 then begin
inc(m);
x[m] := 1;
p[m] := 1;
end;
end;
function euqlid(a,b : longint) : longint;
var r : longint;
begin
if a > b then begin
r := a;
a := b;
b := r;
end;
r := b mod a;
if r = 0 then euqlid := a else euqlid := euqlid(a,r);
end;
function count(k : longint) : int64;
var i,j : longint;
y : int64;
begin
y := 1;
for i := 1 to m do begin
for j := 1 to (x div gcd)*k do begin
y := y*p;
end;
end;
count := y;
end;
begin
while true do begin
readln(h,num);
if (h = 0) and (num = 0) then break;
if h = 1 then begin
writeln('0 1');
continue;
end;
faht(h);
gcd := x[1];
for i := 2 to m do begin
gcd := euqlid(gcd,x);
end;
k := gcd div (x[1] div gcd);
for i := 1 to k do begin
if k mod i <> 0 then continue;
n := count(i);
n := n-1;
r := 1;
for j := 1 to k div i do begin
r := r*n;
end;
if r = num then begin
s := k div i;
break;
end;
end;
l := 1;
sum := h;
r := 1;
t := h;
for i := 1 to s do begin
r := r*n;
if i <> s then begin
l := l+r;
end;
t := t div (n+1);
sum := sum+r*t;
end;
writeln(l,' ',sum);
end;
end.
[/pascal]
I present height of initional cat as prime numbers degrees. After than finding all possible n's
[pascal]
program zzz;
var i,j,k,m,s,min,gcd : longint;
h,num,l,sum,r,n,t : int64;
p,x : array [1..100000] of longint;
procedure faht(h : int64);
var i,s : longint;
begin
fillchar(x,sizeof(x),0);
m := 0;
s := trunc(sqrt(h))+1;
for i := 2 to s do begin
if h mod i = 0 then begin
inc(m);
p[m] := i;
end;
while h mod i = 0 do begin
h := h div i;
inc(x[m]);
end;
end;
if h > 1 then begin
inc(m);
p[m] := h;
x[m] := 1;
end;
if m = 0 then begin
inc(m);
x[m] := 1;
p[m] := 1;
end;
end;
function euqlid(a,b : longint) : longint;
var r : longint;
begin
if a > b then begin
r := a;
a := b;
b := r;
end;
r := b mod a;
if r = 0 then euqlid := a else euqlid := euqlid(a,r);
end;
function count(k : longint) : int64;
var i,j : longint;
y : int64;
begin
y := 1;
for i := 1 to m do begin
for j := 1 to (x div gcd)*k do begin
y := y*p;
end;
end;
count := y;
end;
begin
while true do begin
readln(h,num);
if (h = 0) and (num = 0) then break;
if h = 1 then begin
writeln('0 1');
continue;
end;
faht(h);
gcd := x[1];
for i := 2 to m do begin
gcd := euqlid(gcd,x);
end;
k := gcd div (x[1] div gcd);
for i := 1 to k do begin
if k mod i <> 0 then continue;
n := count(i);
n := n-1;
r := 1;
for j := 1 to k div i do begin
r := r*n;
end;
if r = num then begin
s := k div i;
break;
end;
end;
l := 1;
sum := h;
r := 1;
t := h;
for i := 1 to s do begin
r := r*n;
if i <> s then begin
l := l+r;
end;
t := t div (n+1);
sum := sum+r*t;
end;
writeln(l,' ',sum);
end;
end.
[/pascal]
-
- New poster
- Posts: 19
- Joined: Tue Jul 16, 2002 5:56 pm
- Location: Seoul
- Contact:
[107] I can't understand...ToT Plz help me.
I am a primer.
I want to solve a problem of 107.
However, I can't understand this problem unfortunately.
What do follow sentences mean?
I want to solve a problem of 107.
However, I can't understand this problem unfortunately.
What do follow sentences mean?
Plz help a primer...ToTThe number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is 1/(N+1) times the height of the cat whose hat they are in.
Homepage : http://www.sozu.pe.kr
This means, suppose the height of the tallest cat is 16 and N is 1.
So the number of cats inside this cats hat is 1( the value of N ). The height of this cat is 1*16/(N+1) or 16/(1+1) = 8;
This cat will have more cats( in this case 1 ) inside its hat.
Of course this is a simple example, because the value of N could be larger than this. However, be assured that the input will be valid, that is the formula will ultimately lead to the smallest cat(s) height to be 1.
So the number of cats inside this cats hat is 1( the value of N ). The height of this cat is 1*16/(N+1) or 16/(1+1) = 8;
This cat will have more cats( in this case 1 ) inside its hat.
Of course this is a simple example, because the value of N could be larger than this. However, be assured that the input will be valid, that is the formula will ultimately lead to the smallest cat(s) height to be 1.
Plz help me out for 107
I just don't know why i am getting time exceed error
any one plz point out the error...
i have tried all possible inputs that i could find on this site
and ALL of them go just like any thing...
i simply cann't understand what the hech is wrong ...
[cpp]#include<iostream>
#include<stdio>
#include<stdlib>
#include<math>
typedef unsigned long int ui;
ui pw(ui n,ui ex)
{
if(ex==1)
return n;
return n*pw(n,ex-1);
}
ui ch(ui h,int m)
{
if(h==1)
{
return h;
}
else{
ui s=h;
for(int i=0;i<m;i++)
{
s+=ch(h/(m+1),m);
}
return s;
}
}
void exp(ui b,ui a)
{
ui volatile num=a;
volatile ui ex=0;
ui x,s=b;
//for the case of leaf==1
if(a==1)
{
for(volatile int i=1;pw(2,i)<=b;)
{
if(s%2==0)
{
ex=i;
i++;
s/=2;
}
else if( (s%2) != 0 )
{
return ;
}
}
if(ex<1)
return;
if(pw(2, ex )==b)
{
ui sa=ex;
cout<<sa<<" "<<ch(b,1)<<endl;
return ;
}
return ;
}
//for any other case
x=2;
while(x<=num)
{
if(num%x==0)
{
num/=x;
ex++;
}
else if((num%x)!=0)
{
x++;
if(ex>0)
{
ex=0;
num=a;
}
}
}
if(pw(x+1,ex)==b)
{
ui s=( (a-1) / (x-1) );
// cout<<endl<<(ui)(log((double)a)/log((double)x))<<endl;/*levels of tree*/
cout<<s<<" "<<ch(b,x)<<endl;
return ;
}
return;
}
int main(){
ui h=1,l=1;
for (;l && h;)//while(l!=0 && h!=0)
{
cin>>h>>l;
if(h==0 && l==0)
{
return 0;
}
else if(h==0 || l==0)
{
l++;
h++;
}
else
{
exp(h,l);
}
}
return 0;
}[/cpp]


any one plz point out the error...
i have tried all possible inputs that i could find on this site
and ALL of them go just like any thing...
i simply cann't understand what the hech is wrong ...

[cpp]#include<iostream>
#include<stdio>
#include<stdlib>
#include<math>
typedef unsigned long int ui;
ui pw(ui n,ui ex)
{
if(ex==1)
return n;
return n*pw(n,ex-1);
}
ui ch(ui h,int m)
{
if(h==1)
{
return h;
}
else{
ui s=h;
for(int i=0;i<m;i++)
{
s+=ch(h/(m+1),m);
}
return s;
}
}
void exp(ui b,ui a)
{
ui volatile num=a;
volatile ui ex=0;
ui x,s=b;
//for the case of leaf==1
if(a==1)
{
for(volatile int i=1;pw(2,i)<=b;)
{
if(s%2==0)
{
ex=i;
i++;
s/=2;
}
else if( (s%2) != 0 )
{
return ;
}
}
if(ex<1)
return;
if(pw(2, ex )==b)
{
ui sa=ex;
cout<<sa<<" "<<ch(b,1)<<endl;
return ;
}
return ;
}
//for any other case
x=2;
while(x<=num)
{
if(num%x==0)
{
num/=x;
ex++;
}
else if((num%x)!=0)
{
x++;
if(ex>0)
{
ex=0;
num=a;
}
}
}
if(pw(x+1,ex)==b)
{
ui s=( (a-1) / (x-1) );
// cout<<endl<<(ui)(log((double)a)/log((double)x))<<endl;/*levels of tree*/
cout<<s<<" "<<ch(b,x)<<endl;
return ;
}
return;
}
int main(){
ui h=1,l=1;
for (;l && h;)//while(l!=0 && h!=0)
{
cin>>h>>l;
if(h==0 && l==0)
{
return 0;
}
else if(h==0 || l==0)
{
l++;
h++;
}
else
{
exp(h,l);
}
}
return 0;
}[/cpp]
-
- New poster
- Posts: 19
- Joined: Tue Jul 16, 2002 5:56 pm
- Location: Seoul
- Contact:
-
- New poster
- Posts: 19
- Joined: Tue Jul 16, 2002 5:56 pm
- Location: Seoul
- Contact:
^-^
I can't read your code...ToT It is difficult to me...;;
I guess that your solution is brute force.
I got Accepted using brute force, but I optimize a fomula.
I used log function.
Of course, Brute force is not good solution.
Newton's method is better solution than brute force.
I guess that your solution is brute force.
I got Accepted using brute force, but I optimize a fomula.
I used log function.
Of course, Brute force is not good solution.
Newton's method is better solution than brute force.
Homepage : http://www.sozu.pe.kr
Good but WA
here good solution but WA what wrong:
get x y
where x==a^b (1) and y==(a-1)^b (2)
sheach b with this property: exp(ln(exp(ln(x)/b) -1)*b)==y
then out is:
((a-1)^b-1)/(a-1-1) and (a^(b+1)-(a-1)^(b+1))/(a-(a-1)) or same
(y-1)/(a-2) and a*x-(a-1)*y
[pascal]var x,y,a,b:int64;begin repeat
readln(x,y);
if(x=0)and(y=0)then break;
if x>1 then begin
b:=0;
repeat inc(b);
a:=round(exp(ln(x)/b));
until round(exp(ln(a-1)*b))=y;
end;
if x<3 then write(x-1)else write((Y-1)div(a-2));
writeln(' ',x*a-y*(a-1));
until 1=0;
end.[/pascal]
get x y
where x==a^b (1) and y==(a-1)^b (2)
sheach b with this property: exp(ln(exp(ln(x)/b) -1)*b)==y
then out is:
((a-1)^b-1)/(a-1-1) and (a^(b+1)-(a-1)^(b+1))/(a-(a-1)) or same
(y-1)/(a-2) and a*x-(a-1)*y
[pascal]var x,y,a,b:int64;begin repeat
readln(x,y);
if(x=0)and(y=0)then break;
if x>1 then begin
b:=0;
repeat inc(b);
a:=round(exp(ln(x)/b));
until round(exp(ln(a-1)*b))=y;
end;
if x<3 then write(x-1)else write((Y-1)div(a-2));
writeln(' ',x*a-y*(a-1));
until 1=0;
end.[/pascal]