11115 - Uncle Jack

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

Moderator: Board moderators

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

11115 - Uncle Jack

Post by kenneth » Tue Oct 10, 2006 2:18 am

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

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian » Tue Oct 10, 2006 2:40 am

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

Post by kenneth » Tue Oct 10, 2006 3:02 am

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
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » Tue Oct 10, 2006 4:05 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

Post by kenneth » Tue Oct 10, 2006 4:51 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

Post by asif_rahman0 » Tue Oct 10, 2006 8:23 am

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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Fri Oct 13, 2006 9:46 am

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

Post by Emilio » Fri Oct 13, 2006 12:56 pm

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
Location: BANGLADESH
Contact:

Post by marif » Sun Oct 22, 2006 8:12 am

it will be very helpful to use 'big integer'

chetan
New poster
Posts: 43
Joined: Sun Sep 24, 2006 2:39 pm

Post by chetan » Sat Apr 28, 2007 10:04 am

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
Location: Bangladesh
Contact:

Post by DP » Sat Apr 28, 2007 10:43 am

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. :D
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
Location: Madrid

Post by mpi » Fri Jul 20, 2007 3:13 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:

Post by mf » Fri Jul 20, 2007 3:39 pm

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
Location: Madrid

Post by mpi » Fri Jul 20, 2007 5:09 pm

Oh my god! :o
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
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Feb 22, 2008 11:05 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''

Post Reply

Return to “Volume 111 (11100-11199)”