2015年1月20日 星期二

2015 Facebook Hacker Cup, Round 1, problem: (C) Winning at Sports

/*
    DP
*/
#include <iostream>
#include <cstdio>

using namespace std;

#define MOD 1000000007

int DP1[3000][3000], DP2[3000][3000];

int T;

int main()
{
    scanf("%d", &T);

    for(int Ti = 1; Ti <= T; Ti++)
    {
        int A, B;
        scanf("%d-%d", &A, &B);

        fill(DP1[0], DP1[2999]+3000, 0);
        DP1[1][0] = 1;

        for(int Ai = 2; Ai <= A; Ai++)
            for(int Bi = 0; Bi <= min(Ai-1, B); Bi++)
            {
                if( Ai-1 > Bi )  DP1[Ai][Bi] += DP1[Ai-1][Bi];
                if( Bi ) DP1[Ai][Bi] += DP1[Ai][Bi-1];

                DP1[Ai][Bi] %= MOD;
            }

        fill(DP2[0], DP2[2999]+3000, 0);

        DP2[0][0] = 1;

        for(int Bi = 0; Bi <= B; Bi++)
            for(int Ai = 0; Ai <= A; Ai++)
            {
                if( Bi != B && Ai > Bi ) break;

                if( Ai ) DP2[Ai][Bi] += DP2[Ai-1][Bi];
                if( Bi ) DP2[Ai][Bi] += DP2[Ai][Bi-1];

                DP2[Ai][Bi] %= MOD;
            }

        printf("Case #%d: %d %d", Ti, DP1[A][B], DP2[A][B]); puts("");
    }
}

沒有留言:

張貼留言