107 - The Cat in the Hat

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:
hello all
i can't figure the reason for WA...
(got over 15 WAs)

Code: Select all

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

//void find_base(__int64 worker, int height, __int64 *base, __int64 *expo){
void find_base(long long worker, int height, long long *base, long long *expo){
long long i,j,k = sqrt( worker )+1, x;
//__int64 i,j,k = sqrt( worker )+1, x;

j = (worker&1)?3:2;
for(; j<=k; j += 2){
i = worker;
x = 0;
while( !(i%j) ){
i /= j;
x++;
}
//if( i == 1 && ( (int)pow(j+1,x)==height) ){
//if( i == 1 && ( (__int64)(pow(j+1,x)+0.5)==height) ){
if( i == 1 && ( (long long)(pow(j+1,x)+0.5)==height) ){
*base = j;
*expo = x;
return ;
}
}
*base = worker;
*expo = 1;
}

void main(void){
//freopen("d:\\a\\107.txt","rb",stdin);

//__int64 worker, non_worker, hight, total_hight, base, expo, i,j,k;
long long worker, non_worker, hight, total_hight, base, expo, i,j,k;

//while( 2 == scanf("%I64d %I64d", &hight,&worker) &&(hight ||worker) ){
while( 2 == scanf("%lld %lld", &hight,&worker) &&(hight ||worker) ){
if( worker == 1 ){
//printf("0 %I64d\n\n", hight);
printf("0 %lld\n", hight);
continue;
}

find_base( worker, hight, &base, &expo);

if( expo == 1 ){
//printf("1 %I64d\n\n",hight+worker);
printf("1 %lld\n",hight+worker);
continue;
}
/* hight at a particular level */
k = hight/(base+1);

/* storing base^1 base^0 */
non_worker = base + 1;
total_hight = k*base + hight;

j = base;
for(i = 2; i<expo; i++){
/* all the internal nodes at that hight */
j = j*base ;
k = k/(base+1);
total_hight += j*k;
non_worker += j;
}
total_hight += worker;

//printf("%I64d %I64d\n\n", non_worker, total_hight);
printf("%lld %lld\n", non_worker, total_hight);
}
//return 0;
}
thx...
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
In Judge's Input Date there're inputs " of the form "
100 1 and if you do not print 7 199 for them
you will get WA. I came to this conclusion via experiments
( experiments == about 20 WAs and 1 ACC ).

Let me be more precise. Suppose you read the numbers N1 and N2
( in this order ) for a given test case. Then you have:

Code: Select all

N1 == (N+1)^K
N2 == N^K
and you want to find N and K.

Well what I want to say is that
if N2==1 you should find N and K in the following way:

Code: Select all

N = 1;
K = (NAT)( logAB(2,n1) + 0.5);
Here K is biggest "level number" we have in the hirerchy/tree of cats
( we assume that the first cat is at level 0 ). N on the other hand is
the number given in the problem statement ( the count of smaller
cats in a given cat's hat ).
The function logAB(A,B) returns the logarithm of B base A. So in
the code above logAB(2,N1) is the logarithm of N1 base 2. And
finally NAT could be defined as long long for example.

Just to note that first I was doing it this way:

Code: Select all

N = 1;
K = (NAT)( logAB(2,n1) );
which was giving 6 199 for a test case like 100 1.
And after that by just adding 0.5 as shown above
I got 7 199 as an answer to the test case 100 1.
And the program also got ACC immediately from the Judge.

Although I do not know what the test cases of the Judge are
and I also do not know if there are similar cases to the test
case 100 1, I hope the remarks above could be of some
help to someone.

Good luck !

New poster
Posts: 22
Joined: Wed Aug 17, 2005 3:04 pm

107-WA, Can you give me cases that fail the program??

Why WA????

It worked for a lot of tests. still it gives WA...
Any Help??

The code(C++):

Code: Select all

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

void main(){
unsigned int H, W, N, x, C, sum,height, j,t;
double R;
unsigned int i;
cin>>H>>W;
while(!(H==0 && W==0)){
if(H==1){
cout<<'0'<<' '<<W<<endl;
cin>>H>>W;
continue;
}

for(x=1;; x++){
N=(unsigned int)pow(W,(double)(1.0/x));
R=1;
for(j=0; j<x; j++)
R*=(N+1);
if(H==R)
break;
if(ceil(R)==H)
break;
if(floor(R)==H)
break;
if(R+0.00001>H)
break;
}

if(R>H){
cout<<'0'<<' '<<'0'<<endl;
cin>>H>>W;
continue;
}

C=0;
t=1;
for(i=0; i<=x; i++){
C+=t;
t*=N;
}

sum=0;
height=H;
i=0;
t=1;
while(height>1){
sum+=t*height;
t*=N;
height=(unsigned int)(height/((N+1)*1.0));
i++;
}

sum+=W;
cout<<C-W<<' '<<sum<<endl;
cin>>H>>W;
}
}
It's lack of faith that makes people afraid of meeting challanges, and I believe in myself.

New poster
Posts: 22
Joined: Wed Aug 17, 2005 3:04 pm

Any quote.. is this case correct??

Is this a correct case, if yes, why? and what are the values of x and N...etc, please, give me the case that makes my code WA...

input
1771561 64

output
7 17715034

It's lack of faith that makes people afraid of meeting challanges, and I believe in myself.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: Any quote.. is this case correct??

My Accepted code could not find the answer for your input.
Because you might catch misunderstanding the meaning of this problem,
I explain details to you.

Code: Select all

N = 5                                                                    number of cats | height of cats
|
o                                          1...(a)  |    216...(a')
|                                                   |
+------------+------------+------------+------------+                         |
|            |            |            |            |                         |
|            |            |            |            |                         |
o            o            o            o            o              1*5...(b)  |     36...(b')
|            |            |            |            |                         |
|            |            |            |            |                         |
----+----    ----+----    ----+----    ----+----    ----+----                     |
| | | | |    | | | | |    | | | | |    | | | | |    | | | | |                     |
o o o o o    o o o o o    o o o o o    o o o o o    o o o o o          5*5...(c)  |      6...(c')
|                                                           |                     |
|                                                           |                     |
|                                                           |                     |
----+----                                                   ----+----                 |
| | | | |                                                   | | | | |                 |
o o o o o                                                   o o o o o     25*5...(d)  |      1...(d')
|
_______________________________________________________________________________________________________

(a)  = initial cat
(a') = height of initial cat
(d)  = number of worker cat

(a) + (b) + (c) = number of cats that are not working
= 31

(a') + (b')*5 + (c')*25 + (d')*125 = height of the stack of cats
= 671

Above is a image which I drew.
(Although I wanted to paste real image (.png or .gif), I had no upload server space...)

This image shows about the first sample input.
If N==5, initial cat have small 5 cats which height is 36 ( = 216/(5+1) ).
Next, 5 cats have small 5 cats each other.
Their height is 6 ( = 36/(5+1) ).
Finally, 25 cats have small 5 cats each other.
Their height is 1 ( = 6/(5+1) ).

so, the number of cats that are not working is : 1 + 5 + 25 = 31.
And, the height of the stack of cats is : 216 + 36*5 + 6*25 + 1*125 = 671 .

If you imagine above relation, you will find the answer by calculating N.

Best regards.

p.s.
Sorry for my crude image... New poster
Posts: 22
Joined: Wed Aug 17, 2005 3:04 pm

...

Hello,

this input crashes my program also, I found it in the board, and the algorithm you have talken about is similar to that I have used, I tried alot of inputs but still either I have TLE, or WA..

It seems that the problem is in the floating point, or in a case that I didn't take care of.. so, What is your opinion???

Thanks another time...
It's lack of faith that makes people afraid of meeting challanges, and I believe in myself.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: ...

I said about above comment
because your code couldn't find the answer even for sample input.

I think this part of your code isn't perfect.
Check again by using sample input.

Code: Select all

for(x=1;; x++){
N=(unsigned int)pow(W,(double)(1.0/x));
R=1;
for(j=0; j<x; j++)
R*=(N+1);
if(H==R)
break;
if(ceil(R)==H)
break;
if(floor(R)==H)
break;
if(R+0.00001>H)
break;
}
And following is the input which I found in this board.
Input :

Code: Select all

1 1
216 125
5764801 1679616
1024 243
2 1
4 1
1024 1
371293 248832
11 10
1 1
1048576 59049
483736625 481890304
125 64
64 1
81 64
0 0
Output should be :

Code: Select all

0 1
31 671
335923 30275911
121 3367
1 3
2 7
10 2047
22621 1840825
1 21
0 1
29524 4017157
615441 1931252289
21 369
6 127
9 217
Best regards.

WhiteBrother
New poster
Posts: 1
Joined: Fri Dec 02, 2005 9:28 pm
Contact:

107

Help me plz! I don`t understand, why wrong answer @_@ ???

#include <iostream>
int main(void) {
using namespace std;
long iS2;
long iS1;

long iN1;
long iN2;
long iX1,iX2;
long it1,it2;
long isch;
long isum1,isum2;

while (1) {
cin >> iS2 >> iS1;

if ((iS1 == 0) & (iS2==0)) break;

iN1 = 2;
iN2 = 3;
isch = 0;
it1 = iS1;
it2 = iS2;
// cout <<"IN1="<<iN1<<" iN2="<<iN2<<endl;
while (iN1<100){
iX1 = it1%iN1;
iX2 = it2%iN2;
if ((iX1 == 0) & (iX2 == 0)){

it1 = it1/iN1;
it2 = it2/iN2;
isch = isch + 1;
} else {

iN1 = iN1 + 1;
iN2 = iN1 + 1;
// cout <<"IN1="<<iN1<<" iN2="<<iN2<<endl;
it1 = iS1;
it2 = iS2;
isch = 0;

}

if ((it1 == 1) & (it2 == 1)){

it1=1;
isum1=1;
for (int i=1; i < isch ; i++){
it1 = it1*iN1;
isum1 = isum1 + it1;
}
it1=1;
it2=iS2;
isum2=it1*it2;
for (int i=0; i < (isch ); i++){
it1 = it1*iN1;
it2 = it2/iN2;
isum2 = isum2 + it1*it2;
}

cout << isum1 << " " << isum2 << endl;
break;
}
}
}
return(0);
}

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

107 WA (getting output for the sample input with the prob)

im getting the correct output for the inputs provided with the problem

but WA when submiting plz help me..

Code: Select all

#include <stdio.h>

int main(void)
{
unsigned long workerCats, maxHeight;
unsigned long N, tempCount, stackHeight, uselessCats, catsInLevel, heightOfCatsInLevel;
int level, i;

scanf("%ld %ld", &maxHeight, &workerCats);
while( maxHeight || workerCats)	{
for(N = 2; N <= workerCats / 2; N++)	{
tempCount = workerCats;
if( !(workerCats % N))	{
level = 1;
while( tempCount > 1 && !(tempCount % N))	{
tempCount /= N;
level += 1;
}
}

if( tempCount == 1)
break;
}

heightOfCatsInLevel = stackHeight = maxHeight;
uselessCats = 1;
catsInLevel = 1;
for(i = 2; i < level; i++)	{
catsInLevel *= N;
heightOfCatsInLevel /= (N + 1);

uselessCats += catsInLevel;
stackHeight += catsInLevel * heightOfCatsInLevel;
}
stackHeight += workerCats;

printf("%ld %ld\n", uselessCats, stackHeight);
scanf("%ld %ld", &maxHeight, &workerCats);
}
return 0;
}

whats wrong here plz help....

Dmitry R
New poster
Posts: 7
Joined: Sat Sep 17, 2005 10:42 am
Contact:
Does your program work corectly if N has prime divisors of power more than one?
For example, it returns

Code: Select all

40 337
for input of

Code: Select all

100 81

Code: Select all

10 271
.

totobogy
New poster
Posts: 7
Joined: Wed Jan 11, 2006 10:08 pm
Location: India
Contact:

107 - Precision Issue?

Plz help me with this. I have checked the test cases on the forum too. This works for all of them except - 1048576 59049 . Is there a precision issue or some fault otherwise?

Code: Select all

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

int main()
{
unsigned long h,n; /*Height of Root Cat, No. of leaf cats*/
unsigned long N,d,nw;/*N-ary tree, depth*/
unsigned long sum;
int i;

scanf("%lu%lu",&h,&n);
while(!(h==0 && n==0))
{
sum = 0; /*reset sum*/

if(n==1 && h==1) /*Exception*/
{
nw = 0;
sum = 1;
}
else if(n == 1 && h%2 == 0) /*Exception(s)*/
{
nw = 0;
while(h!=0)
{
sum += h;
nw++;
h /= 2;
}
nw--; /*don't include workers*/
}
else
{
for(d=1;;d++) /*CAUTION - Can cause infinite loop*/
{
if((unsigned long) pow(n,(double)1/d)+1 == (unsigned long) pow(h,(double)1/d))
break;
}

N = (unsigned long) ((pow(n,(double)1/d))+ 0.5);
nw = (unsigned long)(pow(N,d)-1)/(N-1);/*non workers*/

/*calculate sum of heights*/

for(i=0;i<=d;i++)
sum += (unsigned long) ((pow(N,i) * h / pow(N+1,i))+0.5); /*not h * pow(N+1,-i)*/

}

printf("%lu %lu\n",nw,sum);
scanf("%lu%lu",&h,&n);
}
return 0;
}

zero_cool
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am
how can I get 199 for 100 1. can anyone explain it to me? because I get 197. It's a very weird problem. I think the judge should change the test case.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
My accepted program isn't able to do anything with input

Code: Select all

100 1
I believe it's invalid. Previous posts would tell the same (with reasons).

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
Are you sure this program gives correct output for the sample inputs? You should never take more than you give in the circle of life.

totobogy
New poster
Posts: 7
Joined: Wed Jan 11, 2006 10:08 pm
Location: India
Contact:
Yes. I have tested it a couple of times.