Game with Pearls
Problem Description
Tom and Jerry are playing a game with tubes and pearls. The rule of the game is:
1) Tom and Jerry come up together with a number K.
2) Tom provides N tubes. Within each tube, there are several pearls. The number of pearls in each tube is at least 1 and at most N.
3) Jerry puts some more pearls into each tube. The number of pearls put into each tube has to be either 0 or a positive multiple of K. After that Jerry organizes these tubes in the order that the first tube has exact one pearl, the 2nd tube has exact 2 pearls, …, the Nth tube has exact N pearls.
4) If Jerry succeeds, he wins the game, otherwise Tom wins.
Write a program to determine who wins the game according to a given N, K and initial number of pearls in each tube. If Tom wins the game, output “Tom”, otherwise, output “Jerry”.
Input
The first line contains an integer M (M<=500), then M games follow. For each game, the first line contains 2 integers, N and K (1 <= N <= 100, 1 <= K <= N), and the second line contains N integers presenting the number of pearls in each tube.
Output
For each game, output a line containing either “Tom” or “Jerry”.
Sample Input
2
5 1
1 2 3 4 5
6 2
1 2 3 4 5 5
Sample Output
Jerry
Tom
题目大意：
Tom和Jerry做游戏，给定N个管子，每个管子上面有一定数目的珍珠。
现在Jerry开始在管子上面再放一些珍珠，放上的珍珠数必须是K的倍数，可以不放。
最后将管子排序，如果可以做到第i个管子上面有i个珍珠，则Jerry胜出，反之Tom胜出。
解题思路：
贪心：（15ms）
将N个管子按管子中的珍珠数量升序排序，则满足条件的时候第i个管子应该有i个珍珠。
每个管子开始遍历，如果第i个管子有i个珍珠，则进行下一次循环；
如果小于i个珍珠，则加上k个珍珠，重新按升序排序；
如果大于i个珍珠，则说明不满足条件 .
二分匹配：（125ms）
以 6 3 1 1 2 3为样例。
1 可以变成 {1,4}
1 可以变成 {1,4}
2 可以变成{2}
3 可以变成{3}
如果从集合{1,1,2,3}到集合{1,2,3,4}的最大匹配数为N，则代表这两两匹配，Terry胜出。
大牛的思路：（0ms）
用num数组记录每个数共有几种可能被组成出来。
同以6 3 1 1 2 3为样例。
num[1]=2,num[2]=1,num[3]=1,num[4]=2
从1到N遍历，如果num[i]不等于零，则固定下来它的管子，那么之后的num[i+n*k]应该相应的减少1，即可能性减少一。
如果遍历到i时，num[i]==0，则说明没有可以构成i的管子存在了，Tom胜出。
Code(匈牙利算法二分匹配)：
1 /************************************************************************* 2 > File Name: shanghai_1001.cpp 3 > Author: Enumz 4 > Mail: 369372123@qq.com 5 > Created Time: 2014年11月02日 星期日 12时07分00秒 6 ************************************************************************/ 7 8 #include<iostream> 9 #include<cstdio> 10 #include<cstdlib> 11 #include<string> 12 #include<cstring> 13 #include<list> 14 #include<queue> 15 #include<stack> 16 #include<map> 17 #include<set> 18 #include<algorithm> 19 #include<cmath> 20 #include<bitset> 21 #include<climits> 22 #define MAXN 1020 23 using namespace std; 24 int a[MAXN]; 25 bool edge[MAXN][MAXN]; 26 int N,K,M=0; 27 int link[MAXN]; 28 bool vis[MAXN]; 29 bool dfs(int x) 30 { 31 for (int y=N+1;y<=N*2;y++) 32 if(edge[x][y]&&!vis[y]) 33 { 34 vis[y]=1; 35 if (link[y]==0||dfs(link[y])) 36 { 37 link[y]=x; 38 return true; 39 } 40 } 41 return false; 42 } 43 void search(void) 44 { 45 for (int x=1;x<=N;x++) 46 { 47 memset(vis,0,sizeof(vis)); 48 if(dfs(x)) 49 M++; 50 } 51 return ; 52 } 53 int main() 54 { 55 int T; 56 cin>>T; 57 while (T--) 58 { 59 cin>>N>>K; 60 memset(link,0,sizeof(link)); 61 memset(edge,0,sizeof(edge)); 62 for (int i=1; i<=N; i++) 63 { 64 cin>>a[i]; 65 for (int j=a[i]; j<=N; j+=K) 66 { 67 edge[i][j+N]=1; 68 edge[j+N][i]=1; 69 } 70 } 71 M=0; 72 search(); 73 if (M==N) 74 printf("Jerry "); 75 else 76 printf("Tom "); 77 } 78 return 0; 79 }
Code（大牛的0ms）：
1 #include<stdio.h> 2 #include<string.h> 3 int main() 4 { 5 int a,num[105],i,j,k,n,flag,T; 6 scanf("%d",&T); 7 while(T--){ 8 scanf("%d%d",&n,&k); 9 memset(num,0,sizeof(num)); 10 for(i=1;i<=n;i++){ 11 scanf("%d",&a); 12 for(j=a;j<=n;j+=k) 13 num[j]++; 14 } 15 flag=1; 16 for(i=1;i<=n&&flag;i++){ 17 if(!num[i]) 18 flag=0; 19 else 20 for(j=i;j<=n;j+=k) 21 num[j]--; 22 } 23 if(flag) 24 printf("Jerry "); 25 else 26 printf("Tom "); 27 } 28 return 0; 29 }