HackerRank Combinatorics – Coinage

Challenge: Coinage

Subdomeniu: Combinatorics (combinatorics)

Scor cont: 40.0 / 40

Submission status: Accepted

Submission score: 1.0

Submission ID: 464728902

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/coinage/problem

Cerinta

The Indian bank issues coins in 4 denominations, ₹1, ₹2, ₹5 and ₹10. 

Given a limited supply of each of the above denominations, in how many ways can you sum them up to a total of ₹N?

**Input Format**  
The first line contains an integer T (number of testcases). 
Each testcase contains 2 lines. The first line contains integer N (sum to be achieved)  
A, B, C and D in the next line, each representing the number of ₹1, ₹2, ₹5 and ₹10 coins respectively. 

**Output Format**  
Output the number of ways in which we can achieve the sum N.   

**Constraints**  
1 <= T <= 150  
1 <= N <= 1000  
1 <= A <= 10000  
1 <= B,C,D <= 1000  

**Sample Input**  

    2
    15
    2 3 1 1
    12
    2 2 1 1

**Sample Output**

    2
    2

**Explanation**  
In the first case we need to find the different ways to total to 15. 
We can use one ₹10 coin and one ₹5 coin  or one ₹10 coin two ₹2 coin and one ₹1 coin. Proceed similarly for the second case.

Cod sursa

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    int t, n, a, b, c, d, i, j, k, count;
    scanf("%d", &t);
    do {
        scanf("%d", &n);
        scanf("%d %d %d %d", &a, &b, &c, &d);
        count = 0;
        for (i = 0; i <= d; ++i) {
            if (10*i >= n) {
                if (10*i == n) {
                    ++count;
                }
                break;
            }
            for (j = 0; j <= c; ++j) {
                if (10*i+5*j >= n) {
                    if (10*i+5*j == n) {
                        ++count;
                    }
                    break;
                }
                for (k = 0; k <= b; ++k) {
                    if (10*i+5*j+2*k >= n) {
                        if (10*i+5*j+2*k == n) {
                            ++count;
                        }
                        break;
                    } else if (n - (10*i+5*j+2*k) <= a) {
                        ++count;
                    }
                }
            }
        }
        printf("%d\n", count);
    } while (--t > 0);

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}