地址：http://codeforces.com/contest/200/problem/C
模拟题
题意：模拟足球小组赛的排名变化。规定只有4个球队，我方球队为BERLAND，一定会有的，然后另外3个球队的名字不一定。4个球队，两两球队间打且仅打一场比赛（所以可以知道一共是打了6场）。输入中给出5行，即5场比赛的信息，还剩下一场的信息没有给出。保证最后一场一定是BERLAND打某个队的，对手是谁要找出来（这个不难），而且也规定这场比赛一定是BERLAND胜利。你的任务是，要令BERLAND在这场比赛后，排在第1名或第2名，满足这个条件下，这场比赛的净胜球数最少，如果净胜球数一样，要令对方的进球数最少。如果无论怎样都无法让BERLAND排在前2名，则输出IMPOSSIBLE
输出最后一场比赛的比分，例如sample中6:0，6是BERLAND的进球数
排名规则：
1.两队比赛，胜方得积分3，败方得积分0。平局两方各得积分1
2.按积分排名，高积分排前面
3.如果积分相同，按6场比赛之后的净胜球排，净胜球高的排前面
4.净胜球相同，则按进球数多的排前面
5.如果进球数都相同，则名字字典序小的排前面（不用考虑失球数了，因为净胜球数，进球数都相同的话，失球数一定相同的）
6.保证球队名字各异，所以6场比赛结束后，排名是可以唯一确定的
模拟过程
1.得到了5场比赛的信息，那么先录入，并且处理好，然后按上面的规则排序。
记住一点：最后一场比赛，是保证BERLAND一定胜利的！！！！！
2.看看BERLAND在5场比赛后排在哪里
如果是前2名，又因为最后一场比赛一定是BERLAND胜利，所以无论对手是谁，结束后BERLAND一定是前2名，所以要保证最后一场净胜球最少，失球最少，所以结果是1:0
3.如果不是排在前2名
和第2名的积分差大于3，那么这场比赛BERLAND胜利，得到3积分，最后积分还是无法超过第2名，所以无论怎么胜利都不行了，输出IMPOSSIBLE
如果和第2名的积分差小于3，且这场球一定是BERLAND赢的，那么赢了之后得3积分，一定超过第2名，所以比分只需要1:0
如果和第2名的积分等于3，那么这种情况是一定有解的，因为保证是BERLAND赢，那么积分就会 = 第二名的积分 ， 只要赢球赢得比较猛，就可以在净胜球等方面超过对方，就可以保证在
然后以第2名为目标，枚举最后一场比赛的净胜球，每次枚举，就改变球队的信息，然后重新排序，看看是否能排在前2名，直到可以为之
要注意枚举最后一场的净胜球，处理不好会掉进死循环，要设置一个条件让它break，具体看代码
代码写得不好，太长了
/* 排名规则 1.先按积分排名，赢球得3分，平局得1分，输球得0分 2.如果两球积分相同，看净胜球，净胜球高的排前面。 净胜球=进球数-失球数 3.净胜球数相同的，进球数高的排前面 4.进球数都相同的，队名字典序小的排前面 输出，要保证berland */ #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 10 #define LEN 25 const char T[LEN]="BERLAND"; bool g[N][N]; struct team{ char name[LEN]; int point; int diff; int score; int miss; }a[N]; int tot; int cmp(struct team x ,struct team y) { if(x.point == y.point) { if(x.diff == y.diff) { if(x.score == y.score) return strcmp(x.name , y.name) < 0; return x.score > y.score; } return x.diff > y.diff; } return x.point > y.point; } int search_team(char *str) { for(int i=0; i<tot; i++) if(!strcmp(str , a[i].name)) return i; strcpy(a[tot].name , str); return tot++; } void fun(int pa , int pb) //本队不在前2名 { //本队在本次比赛中一定是胜利的 //BERLAND已经是前两位了，而且比赛一定是胜利，那么比赛后也一定是在前两位，比赛结果直接判断为1:0 if(pa <= 1) { printf("1:0\n"); return ; } //就算胜利得到3积分也不能升到第2位 if(a[1].point - a[pa].point > 3) { printf("IMPOSSIBLE\n"); return ;} //因为一定是赢球的，一定得3积分，那么一定超过了第2名 if(a[1].point - a[pa].point < 3) { printf("1:0\n"); return ;} //剩下来的情况就是，第二名比自己多3积分，自己一定赢，赢了之后积分至少与第2名相同的 int D = a[1].diff - a[pa].diff; //和第二名的净胜球差差 //还没打之前，我们队的净胜球就大于等于第2名了，那么打了之后净胜球一定大于它，我方胜 if(D <= 0) { printf("1:0\n"); return ; } //剩下来就是净胜球不够第2名大，那么就枚举比赛我方的净胜球 int k , d , p , q ; struct team b[N]; for(d=(D+1)/2; ; d++) //净胜球数 for(p=d; ; p++) //我方进球数 { q = p - d; //对方进球数 for(k=0; k<4; k++) b[k] = a[k]; b[pa].diff += d; b[pa].score += p; b[pa].miss += q; b[pa].point += 3; b[pb].diff -= d; b[pb].score += q; b[pb].miss += p; sort(b,b+4,cmp); for(k=0; k<4; k++) if(!strcmp(b[k].name , T)) break; if(k<=1) { printf("%d:%d\n",p,q); return ;} if(b[k].diff < b[1].diff) break; } } void solve() { int x ,y; char temp[LEN],teama[LEN],teamb[LEN]; for(int i=0; i<4; i++) for(int j=0; j<4; j++) if(i!=j && !g[i][j]) { x = i; y = j; break; } strcpy(teama,a[x].name); strcpy(teamb,a[y].name); if(!strcmp(teamb,T)) { strcpy(temp,teama); strcpy(teama,teamb); strcpy(teamb,temp); } /*找出了还没最后一场比赛的两个队伍，并且让teama是BERLAND*/ sort(a,a+4,cmp); // printf("%s %s\n",teama,teamb); // for(int i=0; i<tot; i++) // printf("%s point=%d diff=%d score=%d miss=%d\n", // a[i].name,a[i].point,a[i].diff,a[i].score,a[i].miss); int pa = search_team(teama); int pb = search_team(teamb); fun(pa , pb); //BERLAND不在前两位，另外处理 } int main() { tot = 0; memset(a,0,sizeof(a)); memset(g,false,sizeof(g)); for(int i=1; i<=5; i++) { char s1[LEN],s2[LEN]; int p,q; scanf("%s%s%d:%d",s1,s2,&p,&q); int x = search_team(s1); a[x].score += p; a[x].miss += q; a[x].diff = a[x].score - a[x].miss; int y = search_team(s2); a[y].score += q; a[y].miss += p; a[y].diff = a[y].score - a[y].miss; if(p > q) a[x].point += 3; else if(p == q) { a[x].point += 1; a[y].point += 1; } else a[y].point += 3; g[x][y] = g[y][x] = true; } solve(); return 0; }