CodeForces - 200C: Football Championship

地址链接：

CF： http://codeforces.com/problemset/problem/200/C

HUSTVirtual Judge：http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=28923

题目：

C. Football Championship

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Any resemblance to any real championship and sport is accidental.

The Berland National team takes part in the local Football championship which now has a group stage. Let's describe the formal rules of the local championship:

• the team that kicked most balls in the enemy's goal area wins the game;
• the victory gives 3 point to the team, the draw gives 1 point and the defeat gives 0 points;
• a group consists of four teams, the teams are ranked by the results of six games: each team plays exactly once with each other team;
• the teams that get places 1 and 2 in the group stage results, go to the next stage of the championship.

In the group stage the team's place is defined by the total number of scored points: the more points, the higher the place is. If two or more teams have the same number of points, then the following criteria are used (the criteria are listed in the order of falling priority, starting from the most important one):

• the difference between the total number of scored goals and the total number of missed goals in the championship: the team with a higher value gets a higher place;
• the total number of scored goals in the championship: the team with a higher value gets a higher place;
• the lexicographical order of the name of the teams' countries: the country with the lexicographically smaller name gets a higher place.

The Berland team plays in the group where the results of 5 out of 6 games are already known. To be exact, there is the last game left. There the Berand national team plays with some other team. The coach asks you to find such scoreX:Y(whereXis the number of goals Berland scored andYis the number of goals the opponent scored in the game), that fulfills the following conditions:

• X>Y, that is, Berland is going to win this game;
• after the game Berland gets the 1st or the 2nd place in the group;
• if there are multiple variants, you should choose such scoreX:Y, where valueX - Yis minimum;
• if it is still impossible to come up with one score, you should choose the score where valueY(the number of goals Berland misses) is minimum.

Input

The input has five lines.

Each line describes a game as "team₁team₂goals₁:goals₂" (without the quotes), what means that teamteam₁played a game with teamteam₂, besides,team₁scoredgoals₁goals andteam₂scoredgoals₂goals. The names of teamsteam₁andteam₂are non-empty strings, consisting of uppercase English letters, with length of no more than 20 characters;goals₁, goals₂are integers from 0 to 9.

The Berland team is called "BERLAND". It is guaranteed that the Berland team and one more team played exactly 2 games and the the other teams played exactly 3 games.

Output

Print the required score in the last game asX:Y, whereXis the number of goals Berland scored andYis the number of goals the opponent scored. If the Berland team does not get the first or the second place in the group, whatever this game's score is, then print on a single line "IMPOSSIBLE" (without the quotes).

Note, that the result score can be very huge, 10:0 for example.

Sample test(s)

input

AERLAND DERLAND 2:1
DERLAND CERLAND 0:3
CERLAND AERLAND 0:1
AERLAND BERLAND 2:0
DERLAND BERLAND 4:0

output

6:0

input

AERLAND DERLAND 2:2
DERLAND CERLAND 2:3
CERLAND AERLAND 1:3
AERLAND BERLAND 2:1
DERLAND BERLAND 4:1

output

IMPOSSIBLE

Note

In the first sample "BERLAND" plays the last game with team "CERLAND". If Berland wins with score 6:0, the results' table looks like that in the end:

1. AERLAND (points: 9, the difference between scored and missed goals: 4, scored goals: 5)
2. BERLAND (points: 3, the difference between scored and missed goals: 0, scored goals: 6)
3. DERLAND (points: 3, the difference between scored and missed goals: 0, scored goals: 5)
4. CERLAND (points: 3, the difference between scored and missed goals: -4, scored goals: 3)

In the second sample teams "AERLAND" and "DERLAND" have already won 7 and 4 points, respectively. The Berland team wins only 3 points, which is not enough to advance to the next championship stage.

题目大意：

BERLAND参加一个比赛， 总共有4个队伍，6场比赛，一个队伍都要和其他队伍都有比赛，即每队都要打3场比赛。 排名规则详见题目。

给出了前5场的比赛结果。然后要你求最后一场的比赛的比分，这个比分必须让最后这场比赛胜利，而且让最后BERLAND队总排名在第一或者第二。而且这个比分X：Y， 要使得X-Y值最小，如果有几个相同的最小的，那么取其中Y最小的一个。

分析与总结：

题目较繁琐，理解好以后也不难做，主要就是排序。

被这题坑到的地方：Note, that the result score can be very huge, 10:0 for example. 也就是说最后一场的比分和之前的都不一样， 没有限制最大是9， 可能是非常大。

经测试， 最大取100就可以AC。

代码：

/*
 * CodeForces - 200C:  Football Championship
 * Time: 30 MS
 * Result: Accepted
 * Author: D_Double
 */
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 100
using namespace std;

struct Team{
    char name[30]; // 队名
    int point;     // 分数
    int score;     // 赢球个数
    int miss;      // 输球个数
    int time;      // 比赛场次
    
    friend bool operator < (const Team&a, const Team&b){
        if(a.point!=b.point) return a.point>b.point;
        if(a.score-a.miss!=b.score-b.miss) return a.score-a.miss > b.score-b.miss;
        if(a.score!=b.score) return a.score>b.score;
        return strcmp(a.name, b.name)<0;
    }
}arr[5], tmp[5];

int nTeam;

int addTeam(char *str){
    for(int i=0; i<nTeam; ++i)
        if(strcmp(arr[i].name, str)==0) {
           return -1;
        }
    strcpy(arr[nTeam].name, str);
    arr[nTeam].point=arr[nTeam].score=arr[nTeam].miss=arr[nTeam].time = 0;
    nTeam++;
    return nTeam-1;
}

int findTeam(char *str){
    for(int i=0; i<nTeam; ++i)
        if(strcmp(arr[i].name, str)==0) return i;
}

int main(){
    freopen("input.txt","r",stdin);
    char team1[30], team2[30];
    int score1, score2;
    nTeam = 0;
    for(int i=0; i<5; ++i){
        scanf("%s %s %d:%d",team1,team2,&score1,&score2);
        addTeam(team1); addTeam(team2);
        int t1 = findTeam(team1), t2 = findTeam(team2);
        arr[t1].time++, arr[t2].time++;
        
        if(score1>score2){ arr[t1].point += 3; }
        else if(score2>score1){ arr[t2].point += 3; }
        else if(score1==score2) { arr[t1].point++; arr[t2].point++; }

        arr[t1].score += score1,  arr[t2].score += score2;
        arr[t1].miss += score2,  arr[t2].miss += score1;
    }
    
    char name[30];
    strcpy(name, "BERLAND");
    
    sort(arr, arr+nTeam);

    bool flag=true;  
    int t=findTeam(name), opp;
    
    if(arr[t].point+3<arr[0].point && arr[t].point+3<arr[1].point){
        flag=false;
        printf("IMPOSSIBLE\n");
    }
    if(flag){
        flag=false;
        // 找到最后一次要和哪个队打
        for(int i=0; i<nTeam; ++i)if(i!=t){
            if(arr[i].time < 3){ opp=i; break;}
        }
        int min=10000;
        for(int i=0; i<=MAXN; ++i){ // 对手分数
            for(int j=i+1; j<=MAXN; ++j){ //  BERLAND队分数

                for(int k=0; k<nTeam; ++k){
                    tmp[k].miss = arr[k].miss;
                    strcpy(tmp[k].name, arr[k].name);
                    tmp[k].point = arr[k].point;
                    tmp[k].score = arr[k].score;
                    tmp[k].time = arr[k].time;
                }       
                tmp[opp].score+=i; tmp[opp].miss += j; 
                tmp[t].score += j; tmp[t].miss+=i;
                
                if(i==j) { tmp[t].point++; tmp[opp].point++; }
                else if(i<j) tmp[t].point+=3;
                sort(tmp, tmp+nTeam);
                int temp;
                for(int l=0; l<nTeam; ++l)
                    if(strcmp(tmp[l].name, name)==0) {
                        temp=l;break;
                    }
                if(temp<2){ 
                   if(j-i<min){
                       flag=true; score1=j; score2=i;
                       min = j-i;
                   }
                }
            }
        }
        if(flag){
            printf("%d:%d\n", score1, score2);
        }
        else printf("IMPOSSIBLE\n"); 
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。
    
  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)