107 - The Cat in the Hat

[I LIKE GN]

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;
}

please help...
thx...

[Sedefcho]

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 !

[Fadia Ismael]

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;
	}
}

Thanks in advance..

[Fadia Ismael]

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

Thanks in advance,,

[tan_Yui]

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...

[Fadia Ismael]

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...

[tan_Yui]

Hi, Fadia Ismael.

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]

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=]

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]

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

instead of

Code: Select all

10 271

.

[totobogy]

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]

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]

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).

[Mohammad Mahmudur Rahman]

Are you sure this program gives correct output for the sample inputs?

[totobogy]

Yes. I have tested it a couple of times.