hdu 1338 Game Prediction
3284 ワード
タイトルの住所:
http://acm.hdu.edu.cn/showproblem.php?pid=1338
テーマの説明:
Game Prodion
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：803 Acceepted Submission(s)：440
Problem Description
Suppose there re re M people，including you，playing a special card game.At the begining，each player receives N cards.The pip of a positive integer which is at most*M.And there re re re re re re re No.tcards theris.with。each player choses one card to compre with others.The player whose card with the bigust pip winds the round，and the n the next round begins.After N rounds，when all the cards of each player have beve the the the moners
Gven 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==m==20)and n(1==n==50)representing the number of plears and the number of cards the atneserepresenting the pips of cards you received at the beginning.The n a blank line follows to separate the cases.
The input is terminated by a line with two zros.
Output
For each test case、output a line consisting of the test case number follo wed by the number of rounds you will at least wind during the game.
Sample Input
Sample Output
クイズ:
欲張りを並べる。少なくとも、他のn-1人の相手は十分に頭がいいということです。油断してあなたを勝者にするべきではない試合を勝ちとさせません。本当にしょうがない局こそ、あなたが少なくとも勝つゲームです。
では、本当に仕方のない局は何ですか？きっと私の持っているカードは他の人の持っているどのカードよりも大きいです。
だから策略はこのようにして、毎回私は自分の一番大きなカードを出します。上の条件に合うなら、このゲームは少なくとも勝ちとなります。反対に相手の勝ちとなります。ここでm-1の相手を相手にして、彼らの任務は私を勝ちとさせないことです。私が一番大きいカードを出すと、彼らは一人で私より少し大きいカードを出すだけで、他の人はみんな小さいカードを出します。今度他の相手を変えて大きなカードを出して私を抑えます。だから実際にm-1の相手を合体させることができます。
コード:
http://acm.hdu.edu.cn/showproblem.php?pid=1338
テーマの説明:
Game Prodion
Time Limit：2000/1000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：803 Acceepted Submission(s)：440
Problem Description
Suppose there re re M people，including you，playing a special card game.At the begining，each player receives N cards.The pip of a positive integer which is at most*M.And there re re re re re re re No.tcards theris.with。each player choses one card to compre with others.The player whose card with the bigust pip winds the round，and the n the next round begins.After N rounds，when all the cards of each player have beve the the the moners
Gven 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==m==20)and n(1==n==50)representing the number of plears and the number of cards the atneserepresenting the pips of cards you received at the beginning.The n a blank line follows to separate the cases.
The input is terminated by a line with two zros.
Output
For each test case、output a line consisting of the test case number follo wed by the number of rounds you will at least wind 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
クイズ:
欲張りを並べる。少なくとも、他のn-1人の相手は十分に頭がいいということです。油断してあなたを勝者にするべきではない試合を勝ちとさせません。本当にしょうがない局こそ、あなたが少なくとも勝つゲームです。
では、本当に仕方のない局は何ですか？きっと私の持っているカードは他の人の持っているどのカードよりも大きいです。
だから策略はこのようにして、毎回私は自分の一番大きなカードを出します。上の条件に合うなら、このゲームは少なくとも勝ちとなります。反対に相手の勝ちとなります。ここでm-1の相手を相手にして、彼らの任務は私を勝ちとさせないことです。私が一番大きいカードを出すと、彼らは一人で私より少し大きいカードを出すだけで、他の人はみんな小さいカードを出します。今度他の相手を変えて大きなカードを出して私を抑えます。だから実際にm-1の相手を合体させることができます。
コード:
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
int m=0,n=0;
int map_num[1000+5]={0};//1 is used 0 is not used for opposite
int my_num[100]={0};
int cases=0;
bool comp(int a,int b) {return(a>b);}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&(m+n)>0)
{
memset(map_num,0,sizeof(map_num));
int cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&my_num[i-1]);
map_num[my_num[i-1]]=1;
}
sort(my_num,my_num+n,comp);
for(int i=0;i<=n-1;i++)
{
int j=0;
for(j=my_num[i]+1;j<=n*m;j++)
{
if(!map_num[j])
{
map_num[j]=1;
break;
}
}
if(j>n*m) cnt++;
}
printf("Case %d: %d
",++cases,cnt);
}
return(0);
}