AE2A - AC code

ae2a-draft.cpp

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;


#define MAXN 1000

bool done[MAXN+10][MAXN*6+10];
long double dp[MAXN+10][MAXN*6+10];
int n, s;

long double solve(int r, int sum)
{
	
	if(done[r][sum])
		return dp[r][sum];
	
	if(r == 1) 
	{
		if(sum > 0 && sum <= 6)
		{
			done[r][sum] = 1;
			return dp[r][sum] = 1.0/6.0;
		}
		else
		{
			done[r][sum] = 0;
			return dp[r][sum] = 0;
		}
	}

	dp[r][sum] = 0;
	for(int i = 1; i <= 6; i++)
		dp[r][sum] += solve(r-1, sum-i);
	dp[r][sum] /= 6.0;
	
	done[r][sum] = 1;
	return dp[r][sum];
}

int main()
{
	int t;
	scanf("%d", &t);
	memset(dp, 0, sizeof(dp));
	memset(done, 0, sizeof(done));

	while(t--)
	{
		scanf("%d%d", &n, &s);
		if(n > MAXN) 
		{
			printf("0\n");
			continue;
		}
		
		long double ans = solve(n,s) * 100.0;
		printf("%d\n", (int)ans);
	}
}