Roy and Alfi are playing a game with **three 1000-sided** dice. Each die has 1000 faces and all the faces are marked from 1 to 1000 on each die.

Alfi rolls all three dice together and sums up the score on all three dice. Total score of Alfi is denoted by **A**. Now it is Roy’s turn to roll them. Let us denote Roy’s score as **R**, which is sum of scores on all 3 dice.

You have to find the number of ways in which **R ≥ A**.

**Input:**

First line contains **T** – number of test cases.

Each of the next T lines contains a single integer **A** – total score of Alfi.

**Output:**

For each test case output the result in a new line.

**Constraints:**

1 ≤ **T** ≤ 10

3 ≤ **A** ≤ 3000

For three 1000-sided dice, the sample space would consist of 1000000000 ways.

These ways are (1,1,1), (1,1,2), (1,2,1), (2,1,1), … , … , … , (1000,1000,1000).

Test #1:

Sum of three dices such that it is greater than equal to 3.

This is satisfied by all the ways in the sample space. So the answer is 1000000000.

Test #2:

Sum of three dices such that it is greater than equal to 4.

This is not satisfied by only way (1,1,1) out of 1000000000 ways. So the answer is 1000000000 – 1 = 999999999.

Test #3:

Sum of three dices such that it is greater than equal to 3000.

Only way that satisfied this is (1000,1000,1000). Hence the answer is 1.

my answer

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int findWays(int m, int n, int x)

{

int table[n + 1][x + 1];

memset(table, 0, sizeof(table)); // Initialize all entries as 0

for (int j = 1; j <= m && j <= x; j++)

table[1][j] = 1;

for (int i = 2; i <= n; i++)

for (int j = 1; j <= x; j++)

for (int k = 1; k <= m && k < j; k++)

table[i][j] += table[i-1][j-k];

/* Uncomment these lines to see content of table

for (int i = 0; i <= n; i++)

{

for (int j = 0; j <= x; j++)

cout << table[i][j] << ” “;

cout << endl;

}*/

return table[n][x];

}

double solve(int m, int n, int x) //m : range; n , dices, x threshold.

{

if (x > m*n || x < n)

return 0;

vector<vector<int>> dp(2, vector<int>(m * n + 1));

for (int i = 0; i <= m * n; ++i)

dp[0][i] = min(i, m);

for (int i = 1; i < n; ++i)

{

fill(&dp[i%2][0], &dp[i%2][i], 0);

for (int j = i; j <= m * n; ++j)

dp[i%2][j] = dp[i%2][j – 1] + dp[(i – 1)%2 ][j – 1] – dp[(i – 1)%2 ][j – 1 – min(j – 1 , m)];

}

return double(dp[(n – 1)%2][m*n] – dp[(n-1)%2][x]) / dp[(n – 1)%2][m*n];

}

int main()

{

ll n,a,r,sum=0;

cin>>n;

while(n–)

{

cin>>a;

if(a==3000)

{

cout<<1<<endl;

continue;

}

for(int i=0;i<a;i++)

{

sum+=findWays(1000,3,i);

}

cout<<solve(1000,3,a);

cout<<1000000000-sum<<endl;

}

return 0;

}

## Leave a Reply