2013
12-09

# Game Prediction

Suppose there are M people, including you, playing a special card game. At the beginning, each player receives N cards. The pip of a card is a positive integer which is at most N*M. And there are no two cards with the same pip. During a round, each player chooses one card to compare with others. The player whose card with the biggest pip wins the round, and then the next round begins. After N rounds, when all the cards of each player have been chosen, the player who has won the most rounds is the winner of the game.
Given your cards received at the beginning, write a program to tell the maximal number of rounds that you may at least win during the whole game.

The input consists of several test cases. The first line of each case contains two integers m (2 <= m <= 20) and n (1 <= n <= 50), representing the number of players and the number of cards each player receives at the beginning of the game, respectively. This followed by a line with n positive integers, representing the pips of cards you received at the beginning. Then a blank line follows to separate the cases.

The input is terminated by a line with two zeros.

For each test case, output a line consisting of the test case number followed by the number of rounds you will at least win during the game.

2 5
1 7 2 10 9

6 11
62 63 54 66 65 61 57 56 50 53 48

0 0

Case 1: 2
Case 2: 4

http://acm.hdu.edu.cn/showproblem.php?pid=1338

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
int my[60];
bool vis[1100];

int main()
{
int n,m,ca=0;

while(scanf("%d%d",&m,&n)&&m+n)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
{
scanf("%d",&my[i]);
vis[my[i]]=true;
}
sort(my+1,my+n+1); //按自己手上的牌，从大到小排序
//如果其他人能赢，则只要有一张牌超过自己手上牌就行了，这时可以丢掉其他的小牌
//当没有比自己大的牌时，后面的一定自己赢了
int pos=1,ans=0;
for(int i=1;i<=n;i++)
{
int tt=my[i],j;
for(j=tt+1;j<=n*m;j++) //找到一张没出的比自己最靠近的大牌
if(!vis[j])
{
vis[j]=true;
break;
}
if(j>n*m) //找不到后面肯定自己赢
{
ans=n-i+1;
break;
}
if(m==2) //其他人已经出完了
continue;
for(int k=0;;) //其他人出较小的牌
{
if(!vis[pos])
{
vis[pos]=true;
k++;
}
pos++;
if(k>=m-2)
break;
}
}
printf("Case %d: %d\n",++ca,ans);

}
return 0;
}

1. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮

2. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1