您当前位置：首页 > php开源 > 综合技术 > Facebook Hacker Cup 2015 Round 1 Winning at Sports (附带测试数据)

Facebook Hacker Cup 2015 Round 1 Winning at Sports (附带测试数据)

来源：程序员人生发布时间：2015-02-27 08:36:00 阅读次数：3119次

题目描写：

Winning at Sports25 points

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⑵, 4⑴, 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.

Example input

Example output ・

5 2⑴ 3⑴ 3⑵ 10⑸ 1000⑸00

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

解题思路：

简单DP，注意特殊情况，具体转移进程见代码.

题目代码：

#include <set> #include <map> #include <queue> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <cctype> #include <algorithm> #define eps 1e⑴0 #define pi acos(⑴.0) #define inf 107374182 #define inf64 1152921504606846976 #define lc l,m,tr<<1 #define rc m + 1,r,tr<<1|1 #define zero(a) fabs(a)<eps #define iabs(x) ((x) > 0 ? (x) : -(x)) #define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (min(SIZE,sizeof(A)))) #define clearall(A, X) memset(A, X, sizeof(A)) #define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE)) #define memcopyall(A, X) memcpy(A , X ,sizeof(X)) #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; int map1[2005][2005]; int map2[2005][2005]; const int mod = 1000000007; int main() { //freopen("data.in","r",stdin); //freopen("data.txt","w",stdout); for(int i=1;i<=2000;i++) { map1[i][0]=1; map2[0][i]=1; } for(int i=1;i<=2000;i++) { for(int j=1;j<=2000;j++) { if(i!=j)map1[i][j]=map1[i][j⑴]; map1[i][j]+=map1[i⑴][j]; map2[i][j]=map2[i⑴][j]; if(i<j)map2[i][j]+=map2[i][j⑴]; map1[i][j]%=mod; map2[i][j]%=mod; } } int t,case1=1; while(scanf("%d",&t)!=EOF) { while(t--) { int a,b; scanf("%d-%d",&a,&b); printf("Case #%d: %d %d ",case1++,map1[a][b],max(1,map2[a][b])); } } return 0; }

题目终究测试数据：

链接: http://pan.baidu.com/s/1mgxFSNI

密码: suiw

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 mysql高并发性能的关键要素

下一篇 TinyOS学习 - Ubuntu 12.04LTS安装TinyOS 2.1.1后make telosb报错之解决方案

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点