URAL 1551. Sumo Tournament(数学啊 )
时间:2015-03-20 23:51:24
收藏:0
阅读:560
题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1551
1551. Sumo Tournament
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
A sumo tournament is held in Tokyo, in which 2N sportsmen take part. In each encounter there is a winner, and the
loser drops out of the tournament. Thus, in order to determine the winner of the tournament, it is necessary to conduct N rounds.
The organizers wish that in as many rounds as possible all encounters would be held between sumoists from different prefectures of Japan. For that they can forge the drawing results arbitrarily.
Input
The first line contains the number N (1 ≤ N ≤ 10). Each of the next 2N lines contains the name
of a sumouist and the prefecture which he presents. The name and prefecture are sequences of Latin letters of length not exceeding 30.
Output
Output the maximal number of rounds in which sumoists from the same prefecture will not fight each other regardless of the outcomes of encounters (that is, find the maximal possible K such
that in at least K rounds all encounters will be between sumoists from different prefectures). The organizers can control the initial arrangement of sportsmen but can‘t control results of encounters.
Sample
input | output |
---|---|
3 Homasho Ishikawa Tamakasuga Tokyo Futeno Tochigi Takekaze Tokyo Kasugao Yamaguchi Kotoshogiku Ishikawa Kotomitsuki Tokyo Miyabiyama Shizuoka |
1 |
代码如下:
//#pragma warning (disable:4786) #include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <climits> #include <ctype.h> #include <queue> #include <stack> #include <vector> #include <utility> #include <deque> #include <set> #include <map> #include <iostream> #include <algorithm> using namespace std; string a, b; map<string, int >m; int main() { int num[11] = {0,2,4,8,16,32,64,128,256,512,1024}; int n; while(~scanf("%d",&n)) { int nn = num[n]; int maxx = 0; for(int i = 0; i < nn; i++) { cin >> a >> b; m[b]++; if(m[b] > maxx) { maxx = m[b]; } } int ans = 0; while(1) { if(maxx <= nn/2) { ans++; nn/=2; } else { break; } } printf("%d\n",ans); } return 0; }
原文:http://blog.csdn.net/u012860063/article/details/44498371
评论(0)