In a conference, attendees are invited for a dinner after the conference. The Coordinator, Sagar arranged round tables for dinner and want to have an impactful seating experience for the attendees. Before finalizing the seating arrangement, he want to analyze all possible arrangements. There are R round tables and N attendees. In case where N is an exact multiple of R, the number of attendees must be exactly N/R. If N is not an exact multiple of R, then the distribution of attendees must be as equal as possible. Please refer Example section for better understanding.
For example, R =2 and N=3
All possible seating arrangements are
(1,2) & (3)
(1,3) & (2)
(2,3) & (1)
Attendees are numbered from 1 to N.
Constraints:
0 < R <= 10 (Integer)
0 < N <= 20 (Integer)
Input Format:
One line containing two space delimited integers R and N, where R denotes the number of round tables and N denotes the number of attendees.
Output Format:
Single integer S denoting number of possible unique arrangements.
Example:
Input:
2 5
Output:
10
Explanation:
R=2, N=5
1. (1,2,3) & (4,5)
2. (1,2,4) & (3,5)
3. (1,2,5) & (3,4)
4. (1,3,4) & (2,5)
5. (1,3,5) & (2,4)
6. (1,4,5) & (2,3)
7. (2,3,4) & (1,5)
8. (2,3,5) & (1,4)
9. (2,4,5) & (1,3)
10. (3,4,5) & (1,2)
Arrangements like
(1,2,3) & (4,5)
(2,1,3) & (4,5)
(2,3,1) & (4,5), etc.
But, as it is a round table, all the above arrangements are same.
Solution: In C
#include<stdio.h>
int ncr(int n, int r)
{
int ans = 1;
for (int i = 1; i <= r; i += 1)
{
ans *= (n - r + i);
ans /= i;
}
return ans;
}
int main()
{
int r,n,ini,extra,t1,t2,com;
scanf("%d %d",&r,&n);
ini = n/r;
extra = n%r;
t1 = ini + 1;
t2 = ini;
com = 1;
for(int i = 0; i < extra; i++)
{
com = com*ncr(n,t1);
n = n-t1;
}
for(int i = extra; i < r; i++)
{
com = com*ncr(n,t2);
n = n - t2;
}
printf("%d",com);
}Solution: In Java
import java.util.*;
class Combination
{
static int ncr(int n, int r)
{
int ans = 1;
for (int i = 1; i <= r; i += 1)
{
ans *= (n - r + i);
ans /= i;
}
return ans;
}
public static void main(String[] args)
{
int r,n,ini,extra,t1,t2,com;
Scanner sc = new Scanner(System.in);
r = sc.nextInt();
n = sc.nextInt();
ini = n/r;
extra = n%r;
t1 = ini + 1;
t2 = ini;
com = 1;
for(int i = 0; i < extra; i++)
{
com = com*ncr(n,t1);
n = n-t1;
}
for(int i = extra; i < r; i++)
{
com = com*ncr(n,t2);
n = n - t2;
}
System.out.println(com);
}
}Solution: In Python 3
def fact(n):
f=1
for i in range(1,n+1):
f=f*i
return f
def ncr(n,r):
if n==r or r==0:
return 1
if r==1:
return n
res=fact(n)//fact(r)
res=res//fact(n-r)
return res
r,n=list(map(int,input().split()))
ini=n//r
extra=n%r
t1=ini+1
t2=ini
com=1
for i in range(0,extra):
com=com*ncr(n,t1)
n=n-t1
for i in range(extra,r):
com=com*ncr(n,t2)
n=n-t2
print(com)Also Checkout