11115 - Uncle Jack

[kenneth]

Is this problem meant to be easy? As I keep getting WA! I am not too sure if it's because of the precision or my logic is wrong

I use the following to output the answer, is that correct?

Code: Select all

printf("%0.0Lf\n", pow((long double) n, d));

Can anyone provide sample output for the following cases by any chance?

Code: Select all

1	0
1	10
1	24
1	25
2	0
2	10
2	24
2	25
3	0
3	10
3	24
3	25
4	0
4	10
4	24
4	25
5	0
5	10
5	24
5	25
6	0
6	10
6	24
6	25
7	0
7	10
7	24
7	25
8	0
8	10
8	24
8	25
9	0
9	10
9	24
9	25
10	0
10	10
10	24
10	25
0	0

Thanks a lot

[arsalan_mousavian]

my AC prgram outputs, and i implemented a bigInt Class for this problem

Code: Select all

1
1
1
1
1
1024
16777216
33554432
1
59049
282429536481
847288609443
1
1048576
281474976710656
1125899906842624
1
9765625
59604644775390625
298023223876953125
1
60466176
4738381338321616896
28430288029929701376
1
282475249
191581231380566414401
1341068619663964900807
1
1073741824
4722366482869645213696
37778931862957161709568
1
3486784401
79766443076872509863361
717897987691852588770249
1
10000000000
1000000000000000000000000
10000000000000000000000000

[kenneth]

Thanks for the quick reply!

I got the same answers as you but got judged as WA......

the input handling case is easy

Code: Select all

int n, d;
cin >> n >> d;
while (n != 0 || d != 0)
{
    printf("%0.0Lf\n", pow((long double) n, d));
    cin >> n >> d;
}

Can anyone think of how else could I get it wrong? It's driving me nuts!

Thanks a lot

[Vexorian]

You got to use something like big ints. Think about it: the maximum result possible is 10^25 and that is enough to overflow 64 bits integers.

[kenneth]

The input that I have created includes cases of
9 24
9 25
10 24
10 25

So I think they should cover al of the extrem cases right???

Is there any special cases that I have missed out on?

[asif_rahman0]

Yes, missed.
For your 10^25 my compiler generates wrong answer when i used double.
so i think long double must be same as double.
So follow Vexorian.

[sakhassan]

Using double or long double makes precision error .... So try to handle it in BigInteger... U can check the other threads for Big Integer

[Emilio]

Only 13 values overflow, so, you can get this 13 values with a calculator and solve the problem. Well, I haven't in account power of 10 because can be got easily.

[marif]

it will be very helpful to use 'big integer'

[chetan]

hi all
could u people please tell me how you arrived at the formula a^b.
even i would like to learn
thank you very much

[DP]

This is primary level.

Think like:
Let, you have 3 marbles. Now, i tell you place those 3 marbles into 3 places. Repetition is always allowable. Then, what will be the answer?

27, right?

Code: Select all

Set={m1,m2,m3}
position={p1,p2,p3}
Now, you can place m1,m2,m3 marbles into p1,p2,p3 places.

So, compare CDs as places & nephews as marbles.
It is a permutation. So, order matters.

Hope your basic is now clear.

[mpi]

I can't understand the n^d approach neither. My approach is based on a recurrence formula that i think is more intuitive:

Code: Select all

for (k = 0..d)
   comb(n, d) = comb(n, d) +  c(n, k) * comb(n-1, d-k)

where c(n, k) stands for binomial coefficient:
http://mathworld.wolfram.com/Combination.html

By the way, anyone knows if i can post the formula above in some kind of "latex" source code?

[mf]

I can't understand the n^d approach neither.

It's very easy: for every disk you have N choices of which nephew to give it to.
For D disks, thus there are N^D possibilities to independently assign each disk to one of N nephews.

[mpi]

Oh my god!
How easy it was! The point is that i was facing the problem focusing only on the number of people.

Thanks, mf, your explanation was very clear.

[turcse143]

i use the algorithm of pow(n,d) by string multiplication:
here is my code. i don't whats problem.

Code: Select all

#include<stdio.h>

main()
{
	char d[35],c[35];
	int i,n,b,a,k,m,p,l,j,e,x;
	freopen("11115.in","rt",stdin);
	while(scanf("%d %d",&a,&x)==2)
	{
		if(a==0&&x==0)
			break;
		if(x==0||x==1&&a==1)
		{
			
			printf("1\n");
		}
		else
		{
	
			b=a;
			i=0;
			while(b)
			{
				e=b%10;
				d[i]=e-48;
				b=b/10;
				i++;
			}
			for(j=1;j<x;j++)
			{
				n=0;p=0;
				for(k=0;k<i;k++)
				{
					l=a*(d[k]+48)+n;
					m=l%10;
					c[p]=m-48;
					p++;
					n=l/10;
				}
				if(j!=x-1)
				{
					while(n)
					{
						e=n%10;
						c[p]=e-48;
						p++;
						n=n/10;
					}
				}
				i=p;	
				for(k=p-1;k>=0;k--)
					d[k]=c[k];
			}
			if(n!=0)
			printf("%d",n);
			for(k=p-1;k>=0;k--)
				printf("%d",c[k]+48);
			printf("\n");
		}
	}
}
	

plese help me.