HackerRank Fundamentals – K Candy Store

Challenge: K Candy Store

Subdomeniu: Fundamentals (fundamentals)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464726150

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/k-candy-store/problem

Cerinta

Jim enters a candy shop which has N different types of candies, each candy is of the same price. Jim has enough money to buy K candies. In how many different ways can he purchase K candies if there are infinite candies of each kind? 

**Input Format**  
The first line contains an integer T, the number of tests.  
This is followed by 2T lines which contain T tests:  
The first line (of each testcase) is an integer N and the second line (of each testcase) is an integer K.   

**Output Format**  
For each testcase, print the number of ways Jim can buy candies from the shop in a newline. If the answer has more than 9 digits, print the last 9 digits.  

**Note**    
This problem may expect you to have solved [nCr Table](https://www.hackerrank.com/challenges/ncr-table)

**Constraints**  
1 <= T <= 200  
1 <= N < 1000  
1 <= K < 1000  

**Sample Input**  

    2
    4
    1
    2
    3

**Sample Output**  

    4
    4

**Explanation**  
There are 2 testcases, for the first testcase we have N = 4 and K = 1, as Jim can buy only 1 candy, he can choose to buy any of the 4 types of candies available. Hence, his answer is 4.
For the 2nd testcase, we have N = 2 and K = 3, If we name two chocolates as *a* and *b*, he can buy 

    aaa bbb aab abb 

chocolates, hence 4.

Cod sursa

#include <bits/stdc++.h>
#define ll long long int
#define cases int testcase; cin >> testcase; while(testcase--)
using namespace std;
const int N = 1e3 + 2;
const int MOD = 1e9;
ll dp[N][N];

int main() {
    int n,k,t;
    for(int i=1; i<N; i++) {
        for(int j=1; j<N; j++) {
            if(i==1) {
                dp[i][j] = 1;
            } else if(j==1) {
                dp[i][j] = i;
            } else {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD;
            }
        }
    }
    cases {
        cin >> n >> k;
        cout << dp[n][k] << endl;
    }
    return 0;
}