Soluție HackerRank pentru Coinage, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Coinage
- Domeniu: Combinatorics
- Limbaj: C++14
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
Cerință
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 sursă
#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;
}