Marbles problem | spoj

#1

I am failing the test cases but i am getting the right answers when i put some custom input.
Here is my code, please tell the error.

https://ide.codingblocks.com/#/s/16565

#2

As you know its anwer is going to be n-1Ck-1 , so you need to calculate this efficiently . But you are calculating factorial which is not possible as factorial of large nos may not fit in long long . So try to calculate this other way.
i have modified ur code , you can take help of this code if you want
https://ide.codingblocks.com/#/s/16574

#3

#include
#include
using namespace std;

long long int C(int x, int y)
{
if(x==y)return 1;
if(y==0) return 1;
if(y==1) return (long long int)x;
long long int ans=1;
if(y>x-y)
** y=x-y;**
** for(int i=0;i<y;i++){**
** ans=ans*(x-i)/(i+1);**
** }**
return ans;
}

int main() {
int t,n,k;
scanf("%d",&t);
while(t–)
{
scanf("%lld%lld",&n,&k);
printf("%lld\n",C(n-1,k-1));
}
return 0;
}

The Code written in **…**symbols is not clear.
Please explain what it is doing

#4

Hey Manoj,

    if(y>x-y)y=x-y;
	for(int i=0;i<y;i++)
	{
		ans=ans*(x-i)/(i+1);
	}

this code is for simply calculating nCk, for more clearance you can see this

C(n, k) = n! / (n-k)! * k!
        = [n * (n-1) *....* 1]  / [ ( (n-k) * (n-k-1) * .... * 1) * 
                                    ( k * (k-1) * .... * 1 ) ]
After simplifying, we get
C(n, k) = [n * (n-1) * .... * (n-k+1)] / [k * (k-1) * .... * 1]

Also, C(n, k) = C(n, n-k)  // we can change r to n-r if r > n-r
3 Likes