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(匈牙利算法二分匹配)：
/*************************************************************************
> File Name: shanghai_1001.cpp
> Author: Enumz
> Mail: 369372123@qq.com
> Created Time: 2014年11月02日 星期日 12时07分00秒
************************************************************************/ #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<list>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<climits>
#define MAXN 1020
using namespace std;
int a[MAXN];
bool edge[MAXN][MAXN];
int N,K,M=;
int link[MAXN];
bool vis[MAXN];
bool dfs(int x)
{
for (int y=N+;y<=N*;y++)
if(edge[x][y]&&!vis[y])
{
vis[y]=;
if (link[y]==||dfs(link[y]))
{
link[y]=x;
return true;
}
}
return false;
}
void search(void)
{
for (int x=;x<=N;x++)
{
memset(vis,,sizeof(vis));
if(dfs(x))
M++;
}
return ;
}
int main()
{
int T;
cin>>T;
while (T--)
{
cin>>N>>K;
memset(link,,sizeof(link));
memset(edge,,sizeof(edge));
for (int i=; i<=N; i++)
{
cin>>a[i];
for (int j=a[i]; j<=N; j+=K)
{
edge[i][j+N]=;
edge[j+N][i]=;
}
}
M=;
search();
if (M==N)
printf("Jerry\n");
else
printf("Tom\n");
}
return ;
}
Code（大牛的0ms）：
#include<stdio.h>
#include<string.h>
int main()
{
int a,num[],i,j,k,n,flag,T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
memset(num,,sizeof(num));
for(i=;i<=n;i++){
scanf("%d",&a);
for(j=a;j<=n;j+=k)
num[j]++;
}
flag=;
for(i=;i<=n&&flag;i++){
if(!num[i])
flag=;
else
for(j=i;j<=n;j+=k)
num[j]--;
}
if(flag)
printf("Jerry\n");
else
printf("Tom\n");
}
return ;
}