Code forces 200C---Football Championship

点击打开链接

题目：

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 score X:Y (where X is the number of goals Berland scored and Y is 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 score X:Y, where value X - Y is minimum;
• if it is still impossible to come up with one score, you should choose the score where value Y (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 team team₂, besides, team₁ scored goals₁ goals and team₂ scored goals₂ goals. The names of teams team₁ and team₂ 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 as X:Y, where X is the number of goals Berland scored and Y is 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.

题目意思：   有4支足球队进行足球比赛，其中有一支是BERLAND，现在这支队伍要和剩下的队伍三支队伍中还少一场比赛的队伍进行最后一场比赛，已知前面的5场比赛的结果，要求能否找到一个比分X：Y，使得BERLAND赢球，并且X-Y的差值最小，如果存在输出X：Y，否则输出IMPOSSIBLE.

满足以下条件：

• 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 score X:Y, where value X - Y is minimum; if it is still impossible to come up with one score, you should choose the score where value Y (the number of goals Berland misses)is minimum.

解题思路：模拟整个过程即可（对名有可能会和样列不同所以我加了一个处理对名的操作）、

1：将读入的数据处理存到一个s[4]数组对于四个队，默认BERLAND为s[3]

2：我们用两个for去枚举所以可能的X Y的比值，然后去处理排名，如果最后BERLAND是前两名即可.

3：当遇到相同分数时候判断条件为3个优先级从上往下先比较第一个不行比第二个最后看第三个

1：进球数-失球数的差值，差值小的优先

2：进球数多的优先

3：对名的字典序小的优先

代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
using namespace std;

string s[4];
string str1 , str2 , str3;
int score[4];//存储前面5个队伍的得分
int num[4];//记录队伍比赛次数
int s_goals[4] , m_goals[4];//记录每个队伍的进球数和失球数
int ts_goals[4] , tm_goals[4];
int minnum;//X-Y最小值
int ans_x , ans_y;
map <string , int>m;

//判断当前是否能够进入前2
int judge(int tmp_score[]){
    int t[4] , rank[4] , vis[4];//t数组记录排序后的得分高到底，rank是排名，vis是标记数组
    memcpy(t , tmp_score , sizeof(t));//将数组赋值给t
    memset(rank , 0 , sizeof(rank));
    memset(vis , 0 , sizeof(vis));
    sort(t , t+4);//排序，从小到大

    for(int i = 0 ; i < 4 ; i++){
        for(int j = 0 ; j < 4 ; j++){
            if(t[i] == tmp_score[j] && !vis[j]){
                rank[i] = j ; vis[j] = 1 ; break;
            }
        }
    }
    int r;//记录这个时候的B的排名在
    for(int i = 0 ; i < 4 ; i++){
        if(rank[i] == 3) r = i;
    }
    
    for(int i = 0 ; i < 4 ; i++){
        if(i != r && t[i] == t[r]){//找到分数和B相同的
           if((ts_goals[3]-tm_goals[3]) > (ts_goals[rank[i]]-tm_goals[rank[i]])){//B得分失分差比较大
              if(i > r){//交换排名
                swap(rank[i] , rank[r]) ; r = i;     
              }
           }
           
           if((ts_goals[3]-tm_goals[3]) == (ts_goals[rank[i]]-tm_goals[rank[i]])){
               if(ts_goals[3] > ts_goals[rank[i]]){//B进球数多
                   if(i > r){
                       swap(rank[i] , rank[r]) ; r = i;  
                   }
               }
               
               if(ts_goals[3] == ts_goals[rank[i]]){//进球相同
                   if(s[3] < s[rank[i]]){
                       if(i > r){
                          swap(rank[i] , rank[r]) ; r = i; 
                       }
                   }
                   
                   if(s[3] > s[rank[i]]){
                       if(i < r){
                           swap(rank[i] , rank[r]) ; r = i;
                       }
                   }
               }
               
               if(ts_goals[3] < ts_goals[rank[i]]){//B进球少
                   if(i < r){
                      swap(rank[i] , rank[r]) ; r = i;  
                   } 
               }
           }
           
           if((ts_goals[3]-tm_goals[3]) < (ts_goals[rank[i]]-tm_goals[rank[i]])){//B得分失分差比较小
               if(i < r){
                   swap(rank[i] , rank[r]) ; r = i;  
               }
           }
        }
    }
    
    //判断当前r
    if(r >= 2) return 1;
    return 0;
}

//处理函数
void solve(){
    int i , j , x ,y;
    int k;//记录球队和B比赛
    for(i = 0 ; i < 4 ; i++){  
         if(i != 3 && num[i] != 3) k = i; 
    }
    
    //printf("k: %d\n" , k);
    int tmp_score[4];//记录6个比赛后的所有队伍的得分
    
    //枚举每一种可能的进球数,B在前面
    for(i = 0 ; i <= 100 ; i++){
        for(j = 0 ; j <= 100 ; j++){
             if(i <= j) continue;
            x = i ; y = j; //x是B的进球数 ， y是k的进球数
            memcpy(tmp_score , score , sizeof(tmp_score));
            memcpy(ts_goals , s_goals , sizeof(s_goals));
            memcpy(tm_goals , m_goals , sizeof(m_goals));
            ts_goals[3] += i ; tm_goals[3] += j;
            ts_goals[k] += j ; tm_goals[k] += i;
            if(x == y) {//平局
                tmp_score[3]++ ; tmp_score[k]++;
            }
            if(x > y) tmp_score[3] += 3;//B赢
            if(x < y) tmp_score[k] += 3;//K赢
            
            if(judge(tmp_score)){
                if(minnum > i - j) {
                    ans_x = i ; ans_y = j;
                    minnum = i-j;
                }
            }
        }
    }
}

//主函数
int main(){
    //freopen("input.txt" , "r" , stdin);
    int i , x , y , c1 , c2;
    while(cin>>str1){
        m.clear() ; 
        for(i = 0 ; i < 3 ; i++) s[i] = "";
        s[3] = "BERLAND";
        for(int k = 0 ; k < 5 ; k++){
            if(k > 0) cin>>str1>>str2>>str3;
            else cin>>str2>>str3;
            //处理数据
            if(str1 == s[3]) c1 = 3;
            if(str2 == s[3]) c2 = 3;
            
            if(str1 != s[3]){
                for(i = 0 ; i < 3 ; i++){
                   if(s[i] == str1) { c1 = i ; break;}
                }
                if(i == 3){
                   for(i = 0 ; i < 3 ;i++){
                       if(s[i] == ""){
                           s[i] = str1 ; c1 = i;
                           break;
                       }
                   }
                }
            }
            if(str2 != s[3]){
                for(i = 0 ; i < 3 ; i++){
                   if(s[i] == str2) { c2 = i ; break;}
                }
                if(i == 3){
                   for(i = 0 ; i < 3 ;i++){
                       if(s[i] == ""){
                           s[i] = str2 ; c2 = i;
                           break;
                       }
                   }
                }
            }
            x = str3[0]-'0' ; y = str3[2]-'0';
            num[c1]++ ; num[c2]++;
            s_goals[c1] += x ; m_goals[c1] += y;
            s_goals[c2] += y ; m_goals[c2] += x;
            if(x == y) {
                score[c1]++ ; score[c2]++;
            }
            if(x > y) score[c1] += 3;
            if(x < y) score[c2] += 3;
        }
        
        minnum = 999999999 ; 
        solve();
        if(minnum != 999999999) printf("%d:%d\n" , ans_x , ans_y);
        else printf("IMPOSSIBLE\n");
        memset(score , 0 , sizeof(score));
        memset(num , 0 , sizeof(num));
        memset(s_goals , 0 , sizeof(s_goals));
        memset(m_goals , 0 , sizeof(m_goals));
    }
    return 0;
}