POJ——1323 Game Prediction

Game Prediction

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 10120	Accepted: 4860

Description

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. 

Input

The input consists of several test cases. The first line of each case contains two integers m (2?20) and n (1?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. 

Output

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. 

Sample Input

2 5
1 7 2 10 9

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

0 0
      

Sample Output

Case 1: 2
Case 2: 4      

Source

Beijing 2002

【題意】

總共n*m張面值為1..n*m的撲克，n個人，每個人m張撲克，一共m輪，每輪每人出一張撲克，最大的人獲勝，給出你的撲克，問你起碼能赢多少局

【輸入】

多組資料

第一行為n、m，若為兩個0表示資料結束

接下來一行m個數字，表示自己的手牌

【輸出】

對于每組資料，輸出一個數字表示起碼能赢多少局

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<ctype.h>

#include<stdlib.h>

#include<string>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

#include<list>

#include<queue>

#include<stack>

#include<iomanip>

#include<numeric>

#include <istream>　　　　 //基本輸入流

#include <ostream>　　　　 //基本輸出流

#include <sstream>　　　　 //基于字元串的流

#include <utility>　　　　 //STL 通用模闆類

#include <complex.h>　　 //複數處理

#include <fenv.h>　　　　//浮點環境

#include <inttypes.h>　　//整數格式轉換

#include <stdbool.h>　　 //布爾環境

#include <stdint.h>　　　//整型環境

#include <tgmath.h>　　　//通用類型數學宏

#define L(a,b,c) for(int a = b;a >= c;a --)

#define M(a,b,c) for(int a = b;a < c;a ++)

#define N(a,b) memset(a,b,sizeof(a));

const int MAX=100000000;

const int MIN=-MAX;

typedef int T;

typedef double D;

typedef char C;

using namespace std;

int a[100010];

int main()

{

    int n,m;

    int t=0;

    while(~scanf("%d%d",&n,&m))

    {

        if(n==0&&m==0)

            break;

        M(i,1,m+1)

        scanf("%d",&a[i]);

        sort(a+1,a+m+1);

        int sum=0,ans=0;    ///sum用來判斷目前數的前面自己沒有的數，ans用來統計自己可能赢得情況

        for(int i=m*n; i>=1,m>=1; i--)

        {

            if(a[m]!=i)     ///比較是否第m個數與i相同，相同用sum累加

                sum++;

            else

            {

                if(sum)

                    sum--;

                else

                    ans++;

                m--;

            }

        }

        printf("Case %d: %d\n",++t,ans);

    }

    return 0;

}