## 11115 - Uncle Jack

Moderator: Board moderators

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

### 11115 - Uncle Jack

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
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
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``````
In being unlucky I have the record.

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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.
Last edited by Vexorian on Thu Oct 12, 2006 6:05 am, edited 1 time in total.

kenneth
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am
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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
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.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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
New poster
Posts: 11
Joined: Sat Jun 24, 2006 11:42 am
Contact:
it will be very helpful to use 'big integer'

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm
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
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
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
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
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
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
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.
''I want to be most laziest person in the world''