Dice Game – TCS CodeVita

Calculate the number of ways to achieve a target sum S using dice with m faces.

Understand the Problem

Problem Statement

Tanu and Shree have invented a dice game with variable faces (2 to 12). The die shows numbers 1 through m, where m is the number of faces. Players take turns rolling the dice, aiming to achieve exactly a target sum S using any number of throws. Your task is to compute how many different sequences of dice rolls can sum exactly to S.

Example: For S=4 and m=2 (faces 1,2), the possible sequences are (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), and (2,2). Thus, there are 5 ways.

Constraints

2 < S ≤ 10^5 (target sum)
1 < m ≤ 12 (number of dice faces)
Time limit: 1 second

Examples

Example 1

Input

Output

5
8
13

Explanation

For S=4, m=2: sequences are (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2) = 5 ways. For S=5, m=2: 8 ways including (1,1,1,1,1), (1,1,1,2), etc. For S=5, m=3: 13 ways with additional sequences using face 3.

Example 2

Input

1
3 2

Output

Explanation

For S=3, m=2: sequences are (1,1,1), (1,2), (2,1) = 3 ways.

Solution

#include <stdio.h>

long long solve(int S, int m) {
    long long dp[S + 1];
    dp[0] = 1;
    
    for (int i = 1; i <= S; i++) {
        dp[i] = 0;
        for (int j = 1; j <= m && j <= i; j++) {
            dp[i] += dp[i - j];
        }
    }
    
    return dp[S];
}

int main() {
    int T;
    scanf("%d", &T);
    
    while (T--) {
        int S, m;
        scanf("%d %d", &S, &m);
        printf("%lld\n", solve(S, m));
    }
    
    return 0;
}

Time:O(S*m) - We iterate through each sum up to S, and for each sum, we check up to m dice values.

Space:O(S) - We use a DP array of size S+1 to store intermediate results.

Approach:

C Solution Explanation:
1. The solve() function implements dynamic programming using a long long array to handle large results.
2. dp[0] = 1 initializes the base case (one way to achieve sum 0).
3. For each sum i from 1 to S, we iterate through all possible dice values j (1 to m).
4. If j ≤ i, we add dp[i-j] to dp[i] (ways to reach i-j plus one throw of j).
5. The main function reads T test cases and calls solve() for each, printing results.

Visual Explanation

Loading diagram...

All Problems