Game with Pearls
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 145 Accepted Submission(s): 96
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”.
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
题意:
给出 T 组样例,后给出 N 和 K,代表有 N 条管子,后给出 N 条管子上面的初始状态珍珠数。可以向任意一条管子添加 K 的珍珠数,问能否使管子分别出现 1 ~ N 的数量。
思路:
二分图,N 最大值才100,所以建图也是非常方便的。将每个数 ans 加 K 循环至 ans > N 来建图,最后判断二分匹配后是否满配即可。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX = 105; int n, k; int num[MAX]; int G[MAX][MAX]; int linker[MAX]; bool vis[MAX]; void build () { memset(G, 0, sizeof(G)); for (int i = 1; i <= n; ++i) { for (int j = num[i]; j <= n; j += k) { G[i][j] = 1; } } } bool dfs (int x) { for (int i = 1; i <= n; ++i) { if (G[x][i] && !vis[i]) { vis[i] = 1; if (linker[i] == -1 || dfs(linker[i])) { linker[i] = x; return true; } } } return false; } int hungary () { int res = 0; memset(linker, -1, sizeof(linker)); for (int i = 1; i <= n; ++i) { memset(vis, 0, sizeof(vis)); if (dfs(i)) ++res; } return res; } int main () { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &k); for (int i = 1; i <= n; ++i) { scanf("%d", &num[i]); } build(); if (n == hungary()) printf("Jerry\n"); else printf("Tom\n"); } return 0; }
相关推荐
Programming Pearls 2nd Edition,比较老的一本书。有的结论仅供参考,已经不合时宜。
Programming Pearls
《more progamming pearls,编程珠玑续》是继《progamming pearls,编程珠玑》的后续书籍,只是有的地方不是很清晰。
Distributed Computing Pearls Gadi Taubenfeld 2018 Copyright © 2018 by Morgan & Claypoo
Programming Pearls 2nd edition Paperback: 256 pages Publisher: Addison-Wesley Professional; 2 edition (October 7, 1999) Language: English ISBN-10: 0201657880 ISBN-13: 978-0201657883
Programming Pearls(2nd) 英文epub 第2版 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
编程珠玑II(More programming Pearls) pdf编程珠玑II(More programming Pearls) pdf
High Performance Parallelism Pearls shows how to leverage parallelism on processors and coprocessors with the same programming – illustrating the most effective ways to better tap the computational ...
More programming pearls
本书给出了一些精心设计的有趣而且颇具指导意义的程序,书中充满了对实用程序设计技巧及基本设计原则的清晰而机智的描述。《编程珠玑》(第2版)(英文版)增加了3个方面的新内容:测试、调试和计时;...
More+Programming+Pearls以及source code for 1
编程珠玑 作者20年前(从1983年到1987年)在communications of the ACM 上连载发表的30篇文章,比《编程珠玑》书写的要详细。很启发人的。
值得一看的好书,学到很多程序设计技巧
北大POJ1260-Pearls 解题报告+AC代码
北大POJ1260-Pearls
programming pearlsprogramming pearls
Pearls of discrete mathematics Pearls of discrete mathematicsPearls of discrete mathematicsPearls of discrete mathematicsPearls of discrete mathematicsPearls of discrete mathematicsPearls of discrete ...
目前最完美的英文版(文字版),支持复制粘贴。