Facebook Hacker Cup 2015 Round 1 --- Winning at Sports-.Net-爱编程

Facebook Hacker Cup 2015 Round 1 --- Winning at Sports-.Net-爱编程

In the game of Sports, the object is have more points than the other team after a certain amount of time has elapsed. Scores are denoted by two hyphen-separated integers. For example, scores may include 3-2, 4-1, or 10-0. The first number is how many points you've scored, and the second is the number of points scored by the opposing team. You're very good at Sports, and consequently you always win. However, you don't always achieve victory the same way every time.

The two most extreme kinds of victory are called stress-free and stressful. In a stress-free victory, you score the first point and from then on you always have more points than your opponent. In a stressful victory, you never have more points than your opponent until after their score is equal to their final score.

Given the final score of a game of Sports, how many ways could you arrange the order in which the points are scored such that you secure a stress-free or stressful win?

Input

Input begins with an integer T, the number of games you'll play. For each game, there is one line containing the final score of the game in the format described above.

Output

For the ith game, print a line containing "Case #i: " followed by two space-separated integers, the number of ways you can achieve a stress-free or stressful win, respectively. Since these numbers may be very large, output them modulo 1,000,000,007.

Constraints

1 ≤ T ≤ 100

Since you always win, the first number in any final score will always be larger than the second. Both scores will be non-negative integers not exceeding 2000.

Explanation of Sample

In the third test case, you can get a stress-free win by scoring points 1, 2, and 4, or points 1, 2, and 3. You can get a stressful win by scoring points 2, 4, and 5, or points 3, 4, and 5.

Sample Input

5
2-1
3-1
3-2
10-5
1000-500

Sample Output

Case #1: 1 1
Case #2: 2 1
Case #3: 2 2
Case #4: 1001 42
Case #5: 70047606 591137401

给一个比赛的最终得分，前面的队总是赢了后面的队，有两种赢的方法，求两种方法数。
第一种是，最开始由你得分，此后你的得分总是比对手高。
第二种是，除非你的对手已经达到最高分了，你总是比你的对手分低。
简单dp。
X. http://joelantonio.me/post/2015/03/29/hacker-cup-round1-solution/

Then the problem asks us: Given the final score of a game of Sports, how many ways could you arrange the order in which the points are scored such that you secure a stress-free or stressful win?

We can resolve this problem using dynamic programming technique. The solution is both case are similar, but the conditions change.

Let A y B the final score, then for stress-free victory we have:

stress_free(a, b) if (a≤b) return 0, because it’s not a stress-free victory 
stress_free(a, b) if (a>A || b>B) return 0, becuase it’s not a stress-free victory 
stress_free(a, b) if (a==A && b==B) rerturn 1, because it’s a stress-free victory 
dp[a][b] = stress_free(a+1, b) + stress_free(a, b+1)

For stressful:

stress_free(a, b) if (a>b) return 0, because it’s not a stressful victory 
stress_free(a, b) if (a>A || b>B) return 0, becuase it’s not a stressful victory 
stress_free(a, b) if (b==B) rerturn 1, because it’s a stressful victory 
dp[a][b] = stressful(a+1, b) + stressful(a, b+1)

 4 int dp1[MAXN][MAXN], dp2[MAXN][MAXN];
 5 int A, B;
 6 
 7 int stress_free(int a, int b){
 8   if(a <= b) return 0;
 9   if(a > A || b > B) return 0;
10   if(a == A && b == B) return 1;
11 
12   int &r = dp1[a][b];
13 
14   if(r == -1){
15     r = stress_free(a+1, b) + stress_free(a, b+1);
16     r %= MOD;
17   }
18 
19   return r;
20 }
21 
22 int stressful(int a, int b){
23   if(a > b) return 0;
24   if(a > A || b > B) return 0;
25   if(b == B) return 1;
26 
27   int &r = dp2[a][b];
28 
29   if(r == -1){
30     r = stressful(a+1, b) + stressful(a, b+1);
31     r %= MOD;
32   }
33 
34   return r;
35 }
36 
37 int main(){
38   ios_base::sync_with_stdio(false);
39   int t;
40   char c;
41   for(int i = 1; i <= t; i++){
42     cin >> A >> c >> B;
43     memset(dp1, -1, sizeof(dp1));
44     memset(dp2, -1, sizeof(dp2));
45     cout << "Case #"  << i << ": " << stress_free(1, 0) << " ";
46     cout << stressful(0, 0) << "\n";
47   }
48   return 0;
49 }

const int maxn=2005;
const int mod=1000000007;
int dp[maxn][maxn],dp2[maxn][maxn];
int main()
{
    freopen("winning_at_sports.txt","r",stdin);
    freopen("outc.txt","w",stdout);
    int T,cas=1,n,m,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d-%d",&n,&m);
        memset(dp,0,sizeof dp);
        memset(dp2,0,sizeof dp2);
        dp[0][0]=dp2[0][0]=1;
        for(i=0;i<=n;i++)
        {
            for(j=0;j<=m;j++)
            {
                if(i+1>j) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
                if(i>j+1) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
                if(i+1<=j||j==m) dp2[i+1][j]=(dp2[i+1][j]+dp2[i][j])%mod;
                if(j+1<=m) dp2[i][j+1]=(dp2[i][j+1]+dp2[i][j])%mod;
            }
        }
        printf("Case #%d: %d %d\n",cas++,dp[n][m],dp2[n][m]);
    }
    return 0;
}

https://github.com/gshopov/competitive-programming-archive/blob/master/dmoj/facebook-hacker-cup/2015/round-1/winning_at_sports.cpp

	vector<vector<unsigned int>> compute_stressfree() {
	vector<vector<unsigned int>> stressfree(
	max_score + 1, vector<unsigned int>(max_score + 1)
	);
	for (unsigned int i {0}; i <= max_score; ++i)
	{
	stressfree[i][0] = 1;
	}
	for (unsigned int i {1}; i <= max_score; ++i)
	{
	for (unsigned int j {1}; j < i; ++j)
	{
	stressfree[i][j] = (stressfree[i][j - 1] +
	stressfree[i - 1][j]) % modulo;
	}
	}
	return stressfree;
	}
	vector<vector<unsigned int>> compute_stressfull()
	{
	vector<vector<unsigned int>> stressfull(
	max_score + 1, vector<unsigned int>(max_score + 1)
	);
	for (unsigned int i {0}; i <= max_score; ++i)
	{
	stressfull[0][i] = 1;
	}
	for (unsigned int j {1}; j <= max_score; ++j)
	{
	for (unsigned int i {1}; i <= j; ++i)
	{
	stressfull[i][j] = (stressfull[i - 1][j] +
	stressfull[i][j - 1]) % modulo;
	}
	}
	return stressfull;
	}

http://blog.csdn.net/lwfcgz/article/details/44102737

1. pair<int, int> get_score(const string& s) {  
2.     int sc1 = 0, sc2 = 0;  
3.     bool flag = false;  
4.     FOR(i, s.size()) {  
5.         if (s[i] == '-') {  
6.             flag = true;  
7.             continue;  
8.         }  
9.         if (!flag) sc1 = sc1 * 10 + (s[i] - '0');  
10.         else sc2 = sc2 * 10 + (s[i] - '0');  
11.     }  
12.     return make_pair(sc1, sc2);  
13. }  
14.   
15. typedef long long ll;  
16. const int MOD = 1000000007;  
17. vector<ll> dp1[2005], dp2[2005];  
18.   
19. void preprocess() {  
20.     dp1[0].push_back(1); dp2[0].push_back(1);  
21.     for (int i = 1; i < 2005; ++i) {  
22.         dp1[i].resize(i); dp2[i].resize(i + 1);  
23.         fill(dp1[i].begin(), dp1[i].end(), 0);  
24.         fill(dp2[i].begin(), dp2[i].end(), 0);  
25.         for (int j = 0; j < i; ++j) {  
26.             if (j == 0) dp1[i][j] = dp2[i][j] = 1;  
27.             else {  
28.                 if (i - j == 1) {  
29.                     dp1[i][j] = dp1[i][j - 1];  
30.                 }  
31.                 else dp1[i][j] = (dp1[i - 1][j] + dp1[i][j - 1]) % MOD;  
32.                 assert(i > j);  
33.                 dp2[i][j] = (dp2[i - 1][j] + dp2[i][j - 1]) % MOD;  
34.             }  
35.         }  
36.         dp2[i][i] = dp2[i][i - 1];  
37.     }  
38.     return;  
39. }  
40.   
41. int main() {  
42.     int T;  
43.     cin >> T;  
44.     preprocess();  
45.     FOR(tt, T) {  
46.         string s;  
47.         cin >> s;  
48.         pair<int, int> score = get_score(s);  
49.         assert(score.first > score.second);  
50.         ll r1 = dp1[score.first][score.second];  
51.         ll r2 = dp2[score.second][score.second];  
52.         cout << "Case #" << tt + 1 << ": " << r1 << " " << r2 << endl;  
53.     }  
54.     return 0;  
55. }

Read full article from Facebook Hacker Cup 2015 Round 1 --- Winning at Sports-.Net-爱编程