Tanu and Shree are friends. They love playing dice games. They also like to experiment and invent new things. They have invented a mechanism whereby upon a click of a button the number of faces on the die and the value of every face on the die gets decided.
Their invention allows the die to have a minimum of 2 faces and a maximum of 12 faces. All faces of the die have an equal probability of being rolled over.
For example, if the button has generated the number 2, then the die will have 2 faces printed with numbers 1 and 2.
The rules of the game are as follows:
• The two players of the game will play alternately
• They can throw the dice any number of times in their turn to come up with the sum as exactly S
• The player who comes up with the sum S in a smaller number of throws will win the game
• S <m is valid; hence it is possible that the second player may not get a chance to roll the dice.
Your task is to compute the number of ways in which the sum (S) can be achieved with dice throws. Refer Examples section for better understanding.
Constraints:
2<S <= 10^5
1 <m<= 12
Input:
The first line of input contains an integer T which denotes the number of test cases. Next T lines contain two space separated integers S and m where
• S denotes the sum to be achieved
• m denotes the number of faces on the dice
Output:
For every test case print a single integer corresponding to the number of ways in which a sum of S can be achieved. Print answer to every test case on a new line.
Time Limit (secs):
1
Example1:
Input:
3
4 2
5 2
5 3
Output:
5
8
13
Explanation:
For Test case 1, we have S as 4 and m as 2. So, the number generated on the dice is 1 and 2. And the possible ways to get the sum as 4 from 1 and 2 are (1,1,1,1), (1,1,2), (1,2,1), (2,1,1) and (2,2). So, the output here is 5.
For Test case 2, we have S as 5 and m as 2. So, the number generated on the dice is 1 and 2. And the possible ways to get the sum as 5 from 1 and 2 are (1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1), (2,1,1,1), (2,2,1), (2,1,2) and (1,2,2). So, the output here is 8.
For Test case 3, we have S as 5 and m as 3. So, the number generated on the dice is 1, 2 and 3. If it is expanded as shown in test cases 1 and 2 above, the total number of possible ways to get sum as 5 is 13.
Example2:
Input:
1
3 2
Output:
3
Explanation:
For Test case 1, we have S as 3 and m as 2. So, the number generated on the dice is 1 and 2. And the possible ways to get the sum as 3 from 1 and 2 are (1,1,1), (1,2) and (2,1). So, the output here is 3.
#include <iostream>
#include <vector>
using namespace std;
vector<int> dp;
int find(int n, int fac) {
if (n == 0) {
return 1; // Base case: If the sum is 0, there is one way (no dice throws).
}
if (dp[n] != -1) {
return dp[n]; // If we've already calculated this value, return it to avoid recalculating.
}
int ans = 0;
for (int i = 1; i <= fac; i++) {
if (n - i >= 0) {
ans += find(n - i, fac); // Recursively calculate the number of ways to achieve the sum.
}
}
dp[n] = ans; // Store the calculated result in the DP table to avoid recalculating.
return ans;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, fac;
cin >> n >> fac;
dp.assign(n + 1, -1); // Initialize the DP table with -1 values.
int ans = find(n, fac); // Call the find function to calculate the result.
cout << ans << "n"; // Print the result for each test case.
}
return 0;
}import java.util.Scanner;
public class Main {
static int[] dp;
public static int find(int n, int fac) {
if (n == 0) {
return 1; // Base case: If the sum is 0, there is one way (no dice throws).
}
if (dp[n] != -1) {
return dp[n]; // If we've already calculated this value, return it to avoid recalculating.
}
int ans = 0;
for (int i = 1; i <= fac; i++) {
if (n - i >= 0) {
ans += find(n - i, fac); // Recursively calculate the number of ways to achieve the sum.
}
}
dp[n] = ans; // Store the calculated result in the DP array to avoid recalculating.
return ans;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t-- > 0) {
int n = scanner.nextInt();
int fac = scanner.nextInt();
dp = new int[n + 1]; // Initialize the DP array with 0 values.
for (int i = 0; i <= n; i++) {
dp[i] = -1; // Set initial values to -1 to indicate that results haven't been calculated yet.
}
int ans = find(n, fac); // Call the find function to calculate the result.
System.out.println(ans); // Print the result for each test case.
}
}
}
def find(n, fac, dp):
if n == 0:
return 1 # Base case: If the sum is 0, there is one way (no dice throws).
if dp[n] != -1:
return dp[n] # If we've already calculated this value, return it to avoid recalculating.
ans = 0
for i in range(1, fac + 1):
if n - i >= 0:
ans += find(n - i, fac, dp) # Recursively calculate the number of ways to achieve the sum.
dp[n] = ans # Store the calculated result in the DP list to avoid recalculating.
return ans
def main():
t = int(input())
for _ in range(t):
n, fac = map(int, input().split())
dp = [-1] * (n + 1) # Initialize the DP list with -1 values.
ans = find(n, fac, dp) # Call the find function to calculate the result.
print(ans) # Print the result for each test case.#include <stdio.h>
int dp[100001]; // A global array for dynamic programming
int find(int n, int fac) {
if (n == 0) {
return 1; // Base case: If the sum is 0, there is one way (no dice throws).
}
if (dp[n] != -1) {
return dp[n]; // If we've already calculated this value, return it to avoid recalculating.
}
int ans = 0;
for (int i = 1; i <= fac; i++) {
if (n - i >= 0) {
ans += find(n - i, fac); // Recursively calculate the number of ways to achieve the sum.
}
}
dp[n] = ans; // Store the calculated result in the DP array to avoid recalculating.
return ans;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, fac;
scanf("%d %d", &n, &fac);
for (int i = 0; i <= n; i++) {
dp[i] = -1; // Initialize the DP array with -1 values.
}
int ans = find(n, fac); // Call the find function to calculate the result.
printf("%dn", ans); // Print the result for each test case.
}
return 0;
}
Leave a Reply