蝈蝈式的记分

2006 年百度之星程序设计大赛初赛题目 2

题目名称：蝈蝈式的记分

内容描述：

蝈蝈小朋友刚刚 学会了 0-9 这十个数字 , 也跟爸爸妈妈来参加百度每周进行的羽毛球活动。但是他还没有球拍高，于是大人们叫他记录分数。聪明的蝈蝈发现只要记录连续得分的情况就可以了，比如用“ 3 2 4 ” 可以表示一方在这一局中连得三分后，输了两分，接着又连得到四分。可是，后来大人们发现蝈蝈只会用 0-9 这十个数字，所以当比赛选手得分超过 9 的时候，他会用一个 X 来表示 10 完成记分。但问题是，当记录为“ X 3 5 ” 的时候，蝈蝈自己也记不起来是一方连续得到十三分后，再输五分；还是先赢十分输三分再赢五分。

因为百度内部就要开始进行羽毛球联赛了，要先摸清大家的实力才好分组比赛呢～于是，大人们想知道以前每局的比分是怎样的，以及谁获得了胜利。要是遇到了根据比赛记录无法确认比赛进程的情况，也要输出相应的提示哦。

需 要帮蝈蝈进一步说明的是，比赛是五局三胜的，每局先获得二十一分的为胜，但是胜方必须领先对手两分或以上，否则必须继续比赛直到一方超出对手两分为止，比 分多的一方获胜。任何一方先获得三局的胜利后就获得胜利，比赛也相应的结束。而且蝈蝈保证是完整的无多余信息的记录了比赛。

输入数据：

以 point.in 为输入文件，文件中首行只有一个整数 M ，表示蝈蝈记录了多少场比赛的分数。每场比赛用两行记录，第一行是一个整数 N(N<=1000) 表示当前这个记录中有多少个字符，第二行就是具体的 N 个字符表示记录的分数。

输出数据：

相 应的内容将输出到 point.out 文件中，对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用 ":" 分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测的时候，以” Unknown “一个单词独占一行表示。

输入和输出结果数据样例：

输入样例

3

23

9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X 1 X 1 1

25

9 3 8 5 4 8 3 9 8 4 X X X X 2 X X X X 2 8 4 9 2 4

43

7 7 7 7 7 3 4 5 6 7 6 5 4 2 1 3 5 7 9 7 5 3 1 3 0 9 9 3 9 3 2 1 1 1 5 1 5 1 5 1 5 5 1

输出样例

21:17

24:22

21:3

Unknown

21:14

20:22

21:23

21:16

21:9
*******************************************************************************************

分析：
首先取出每个比分，根据比分X（后面的比分跟他一起算或者不一起算）穷举所有可能性。
对于每一个可能性的比分结果，进行判断do_it
如果比赛场次大于5次，还有比分没有计算完，则这个结果不可能。
如果所有比分计算完了，但是最后一个场次的结果并没有决出胜负，则这个结果也不可能。
否则可能性+1

当所有结果出现重复可能性的话，就不能确定结果。

注意：根据题目和样例数据，30,5表示A连胜30下，负5下，表示第一局A 21比0胜了，第二局一开始又胜了9下，然后输了5下。

代码：
#include
#include

int scores_nr;
int *scores;
int *tmp_scores;
int results = 0;

void do_it() {

        printf("\n******do it: ");
        int i;
        for (i=0; i                printf("%d ", tmp_scores[i]);
        }
        printf("******\n");

        int rounds_nr = 0;
        int rounds_result[5][2];
        memset(rounds_result, 0, sizeof(rounds_result));

        int  score1, score2;

        score1 = score2 = 0;
        int add_score1 = 1;

        for (i=0; i                if (rounds_nr >= 5) {
                        printf("\t can't play more than 5 rounds\n");
                        return;
                }
                int score = tmp_scores[i];
                if (score == 11)
                        score = 10;
                if (add_score1) {
                        rounds_result[rounds_nr][0] += score;
                } else {
                        rounds_result[rounds_nr][1] += score;
                }

                if (tmp_scores[i] != 10) {
                        add_score1 = add_score1 == 1 ? 0 : 1;
                }

                if (rounds_result[rounds_nr][0] >= 21 || rounds_result[rounds_nr][1] >= 21) {
                        if (abs(rounds_result[rounds_nr][0] - rounds_result[rounds_nr][1])  >= 2) {
                                if (rounds_result[rounds_nr][0] > rounds_result[rounds_nr][1] > 0) {
                                        //player 1 win
                                        int delta = 0;
                                        if (rounds_result[rounds_nr][1] <= 19) {
                                                printf("\tround %d result, %d : %d\n", rounds_nr, 21, rounds_result[rounds_nr][1]);
                                                score1 = rounds_result[rounds_nr][0] - 21;
                                                score2 = 0;
                                                rounds_nr++;
                                                continue;
                                        } else {
                                                printf("\tround %d result, %d : %d\n", rounds_nr, rounds_result[rounds_nr][1]+2, rounds_result[rounds_nr][1]);
                                                score1 = rounds_result[rounds_nr][0] - rounds_result[rounds_nr][1] - 2;
                                                score2 = 0;
                                                rounds_nr++;
                                                continue;
                                        }
                                } else {
                                        //player 2 win
                                        if (rounds_result[rounds_nr][0] <= 19) {
                                                printf("\tround %d result, %d : %d\n", rounds_nr, rounds_result[rounds_nr][0], 21);
                                                score1 = 0;
                                                score2 = rounds_result[rounds_nr][1] - 21;
                                                rounds_nr++;
                                                continue;
                                        } else {
                                                printf("\tround %d result, %d : %d\n", rounds_nr, rounds_result[rounds_nr][0], rounds_result[rounds_nr][0]+2);
                                                score1 = 0;
                                                score2 = rounds_result[rounds_nr][1] - rounds_result[rounds_nr][0] - 2;
                                                rounds_nr++;
                                                continue;
                                        }
                                }
                        }
                }
        }

        if (rounds_nr < 5 &&(rounds_result[rounds_nr][0] != 0 || rounds_result[rounds_nr][1] != 0)) {
                printf("\tincomplete round %d result [%d : %d]\n", rounds_nr, rounds_result[rounds_nr][0], rounds_result[rounds_nr][1]);
                return;
        }

        results++;
}


void func(int score_id) {
        if (score_id == scores_nr) {
                //do it
                do_it();
        } else {
                if (scores[score_id] == -1) {
                        //this x score and  subsquent score are combined socres
                        tmp_scores[score_id] = 10;
                        func(score_id+1);
                        //this x score and  subsquent score are seperated socres
                        tmp_scores[score_id] = 11;
                        func(score_id+1);
                } else {
                        tmp_scores[score_id] = scores[score_id];
                        func(score_id+1);
                }
        }
}


int main(int argc, char **argv) {


        FILE *fp = fdopen(0, "r");
        char line[1024];
        char *p;
        p = fgets(line, sizeof(line), fp);

        scores_nr = atoi(line);

        fgets(line, sizeof(line), fp);
        scores = (int *)malloc(sizeof(int) * scores_nr);
        tmp_scores = (int *)malloc(sizeof(int) * scores_nr);
        int i;
        for (i=0; i                sscanf(p, "%c ", &scores[i]);
                p += 2;
                if (scores[i] == 'X' || scores[i] == 'x') {
                        scores[i] = -1;
                } else if (scores[i] >= '0' && scores[i] <= '9') {
                        switch(scores[i]) {
                                case '0': scores[i]=0;break;
                                case '1': scores[i]=1;break;
                                case '2': scores[i]=2;break;
                                case '3': scores[i]=3;break;
                                case '4': scores[i]=4;break;
                                case '5': scores[i]=5;break;
                                case '6': scores[i]=6;break;
                                case '7': scores[i]=7;break;
                                case '8': scores[i]=8;break;
                                case '9': scores[i]=9;break;
                                default: break;
                        }
                } else {
                        printf("socre = %c input error\n", scores[i]);
                        return 0;
                }
        }

        printf("socre nr = %d\n", scores_nr);
        for (i=0; i                printf("%d ", scores[i] );
        }
        printf("\n");


        func(0);


        if (results == 0) {
                printf("impossible\n");
        } else if (results == 1) {
                printf("yes, we got result\n");
        } else {
                printf("too much possibilities, can't determine\n");
        }
        return 0;
}