# TALIA - Editorial

Talia and Chocolates

Setter: sayan_kashyapi

Tester: debrc , mishra_roshan

Editorialist: sayan_kashyapi

Simple

# PREREQUISITES:

Binomial Coefficients

# PROBLEM:

You are given the number of chocolates, K and the number of pockets N. You have to distribute all the K chocolates in the N pockets. All the chocolates are identical but all pockets are distinct and can be empty.

# EXPLANATION

Suppose, the no. of pockets = N and the no. of chocolates = K.

n_1, n_2, n_3, ... N pockets

then, n_1 + n_2 + n_3 + ... = K where n_1, n_2, n_3, ... \le 0.

So, you have to return the value i.e. the total number of ways = \binom {k + n - 1}{n - 1}.

# TIME COMPLEXITY

Time complexity is O(KlogN) for each test case.

# SOLUTIONS:

Setter's Solution
C++
``````#include <bits/stdc++.h>
using namespace std;
void printNcR(int n, int r) {
long long p = 1, k = 1;
if (n - r < r) r = n - r;
if (r) {
while (r) {
p *= n;
k *= r;
long long m = __gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else p = 1;
cout << p << endl;
}
int main()
{
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
printNcR(k + n - 1, n - 1);
}
return 0;
}
``````
Tester's Solution
Java
``````import java.util.*;
public class Main {
static long gcd(long a,long b){
if(b==0)
return a;
return gcd(b,a%b);
}
static void printNcR(int n, int r) {
long p = 1, k = 1;
if (n - r < r) r = n - r;
if (r>0) {
while (r>0) {
p *= n;
k *= r;
long m = gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else p = 1;
System.out.println(p);
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();

while (t-->0) {
int n=sc.nextInt();
int k=sc.nextInt();
printNcR(k + n - 1, n - 1);
}
}
}
``````
Python
``````#import modules here
import math,sys,os
#from itertools import permutations, combinations
# from collections import defaultdict,deque,OrderedDict,Counter
# import bisect as bi
#import heapq
from io import BytesIO, IOBase
mod=10**9+7

# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

while True:
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0

while self.newlines == 0:
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

#input functions
def inp(): return int(input())
def print_list(l):
print(' '.join(map(str,l)))
def yes():
print("YES")
def no():
print("NO")

# functions
# def BinarySearch(a,x):
#     i=bi.bisect_left(a, x)
#     if i != len(a) and a[i] == x:
#         return i
#     else:
#         return -1

# def gcd(a,b):
#     return math.gcd(a,b)

# def is_prime(n):
#     """returns True if n is prime else False"""
#     if n < 5 or n & 1 == 0 or n % 3 == 0:
#         return 2 <= n <= 3
#     s = ((n - 1) & (1 - n)).bit_length() - 1
#     d = n >> s
#     for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
#         p = pow(a, d, n)
#         if p == 1 or p == n - 1 or a % n == 0:
#             continue
#         for _ in range(s):
#             p = (p * p) % n
#             if p == n - 1:
#                 break
#         else:
#             return False
#     return True

# def mulinverse(a):
#     return pow(a,mod-2,mod)

####################Let's Go Baby########################
for _ in range(inp()):
n,k=minp()
print(int(math.factorial(n+k+-1)/(math.factorial(n-1)*math.factorial(k))))
``````

Feel free to Share your approach.
Suggestions are welcomed as always had been.