## 107 - The Cat in the Hat

Moderator: Board moderators

QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am

### Good solution in 107 but get WA!!! What wrong in algo?

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
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]
QulinXao
New poster
Posts: 29
Joined: Mon Apr 05, 2004 11:12 am
sorry to all cose I test on all test here and get some hint what was wrong in my "Good sol...",now I get acccepted 107 problem.
And what amazing the algo more simple then pred I post kec
New poster
Posts: 1
Joined: Sat May 15, 2004 8:21 pm

### 107 Cat in the hat

I tried to solve 107 problem, but unfortunetlly I've got few TLE, when I change some of the varible types (to smaller - dword) I've got a WA. That is wrong ??? Please HELP ME.
[pascal]
program p107;
{\$APPTYPE CONSOLE}
var
poziom: integer;
vn: integer;
wea,web: longword;
wya,wyb: longword;

function pwr(x,n: real): real;
begin
pwr:=exp(n*ln(x));
end;

function root(x,n: real): real;
begin
n:=1/n;
root:=exp(n*ln(x));
end;

function Findinhatcat(a,b: longword): longword;
var
x: longword;
begin
x:=1;
while (trunc(10000*(root(a,x)-1))<>trunc(10000*(root(b,x)))) and (x<100) do inc(x);

findinhatcat:=x;
vn:=round(root(b,x));
end;

function ilekotow(poz,n: integer): longword;
var
a: integer;
x: longword;
begin
x:=0;
for a:=0 to poz-1 do
x:=x+trunc(pwr(n,a));
ilekotow:=x;
end;

function wys(poz,n: integer): longword;
var
a: integer;
x: real;
ile: integer;
w: real;
begin
x:=0;
w:=wea*(1+n);
for a:=0 to poz do
begin
ile:=trunc(pwr(n,a));
w:=w/(n+1);
x:=x+ile*w;
end;
wys:=round(x);
end;

begin
while (wea<>0) or (web<>0) do
begin
if (wea>1) then
begin
poziom:=findinhatcat(wea,web);
wya:=ilekotow(poziom,vn);
wyb:=wys(poziom,vn);
end
else
if wea=1 then begin wya:=0; wyb:=1 end;
writeln(wya,' ',wyb);
end;
end.[/pascal]
Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Very less number of people use pascal . So better to post your algorithm or discuss where you face some problem.

Discussion is better than debuging. People have no much time to find the bug in your code... shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
There are several threads regarding this problem, with many critical input. You should look into one of them.
Stas
New poster
Posts: 5
Joined: Sat Jul 03, 2004 5:15 pm
Location: Kyrgyzstan
Contact:

### at last i got ac!

sory for my english :)

my program had a problem with comparing 2 real type variables.
the solution is
abs(a-b)<0.00000001 or something like that.
I hope this will help.
hiloshi
New poster
Posts: 20
Joined: Fri Aug 27, 2004 8:15 am
Location: Kanagawa, Japan
hi yiuyuho.

I have got WA, so I checked output for your input.

390625 65535

It's more than probable that program run for endless loop becase it can't find the value of N.
But I got Accept now.

I think your input is invalid.
This problem is undifficult, but everyone think any input is valid, and get WA.
My program is very simple.
I deleted some process for invalid input in my WA program, then I got Accept.
I hope you can understand my poor English.
yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
It was my mistake.
raghav
New poster
Posts: 3
Joined: Mon Sep 13, 2004 3:11 pm
81 64 is correct input and it's a beautiful one too! Kudos to the creator!!!
9^2 8^2 is what it should be interpreted as. It could also be 3^4 2^6, which is why the test case is subtly different Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:
Have you tried the input format 64 1. The output should be 6 127. I'll try your code on my pc. Good luck. We will, We will BREAK LOOP!!!!
Heartattack!
New poster
Posts: 45
Joined: Fri Jan 16, 2004 7:02 pm
Location: CSE::BUET
Contact:

### Re: WA! 107 Please .. Help me

einstain000 wrote:

Code: Select all

``````#include<stdio.h>

/* special condition ( 1,x)*/
if( height == 1 ) {
printf("0 %d\n",works);
continue;
}

[/quote]
Deary me, the special condition has the initial cat at height=1. So, no workers, good. Height of total cats=works....BAD 8) If there's only one cat of height 1 then the total height is of course 1. Everything else is ok. Hope you get AC.....Silly einstain :P  :P  :P  :P``````
We will, We will BREAK LOOP!!!!
ioriyagami
New poster
Posts: 5
Joined: Sun Jan 30, 2005 2:27 pm

I can't understand this problem. what does this mean?

"The number of cats inside each (non-smallest) cat's hat is a constant, N. The height of these cats-in-a-hat is times the height of the cat whose hat they are in.

The smallest cats are of height one;
these are the cats that get the work done.
All heights are positive integers."

who can help me ?thanks.
Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Hello ioriyagami.
Lets initial cat hight be P.There is some number N(wich is not given) that each cat have N small cats in his hat.And each cat in hat of biggest cat has hight p/(N+1).It means that cat in hat of cat wich is in hat of biggest cat will have hight p/(n+1)^2.And so one until hight=1.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
ioriyagami
New poster
Posts: 5
Joined: Sun Jan 30, 2005 2:27 pm

### thank you very much. thanks.
sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

### 107 wa

what's the limit of the input number?
shall i use BigInteger??