Dutor

Description:

There is a special card game that one who wins least rounds gets the money from people who win more. Suppose there are M people, including you, playing this game. First of all, each player gets N cards. The number on each card is a positive integer which is at most N*M. Additionally, the number of the cards is unique. The game consists of N rounds; for each round every player chooses one card to compare with cards from others. The player whose card with the biggest number wins the set, and then the next round begins. After N sets, when all the cards have been chosen, the player who has won the least rounds domains the game.

Given your cards received at the beginning. Unquestionable, everyone wants to win least rounds of the game. However, winning 0 rounds sometimes is impossible for some reasons. Your mission is to write a program to determine the least rounds you might win.

Input:

The input contains many test cases. The first line of each case contains two integers M (1 <=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. Followed is a line with N positive integers, representing the numbers on the cards you received at the beginning in each round. Then a blank line is followed to separate the cases.
The input is terminated by a line with two zeros.

Output:

For each test case, you should output the rounds you win at least as the sample output.

Input Sample:

2 5
1 7 2 10 9

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

0 0

Output Sample:

Case 1: 2
Case 2: 4

Code Sample:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
 
int
main ()
{
    int m, n;
    int j = 1;
    vector < int >ivec;		//存放最初手中的牌
    ivec.reserve (100);
    while (cin >> m >> n && (m != 0 || n != 0))
      {
	  int tmp;
	  for (int i = 0; i < n; i++)
	    {
		cin >> tmp;
		ivec.push_back (tmp);
	    }
	  vector < int >::iterator itrb = ivec.begin ();
	  vector < int >::iterator itre = ivec.end ();
	  sort (itrb, itre);	//为便于计算进行排序
	  int cnt = 0;
	  int sum = 0,		//对手比当前牌大的个数
	      used = 0;		//用过的sum
	  for (int i = ivec.size () - 1; i >= 0; i--)	//从最大的牌算起
	    {
		sum = m * n - ivec[i] - (ivec.size () - 1 - i) - used;
		if (sum == 0)
		  {
		      cnt++;	//没有比当前牌大的 则win
		  }
		else
		  {
		      sum--;
		      used++;
		  }
	    }
	  cout << "Case " << j++ << ": " << cnt << endl;	//输出结果
	  ivec.clear ();	//清空向量 Attention！！！
      }
//system("pause");
    return 0;
}

[warning]This is original article, you could copy it freely with my site links!
此日志为dutor原创，您可以自由转载，添加原文链接我将万分感激！[/warning]