百度Astar2006程序设计大赛预赛题--蝈蝈计分

主题：百度Astar2006程序设计大赛预赛题--蝈蝈计分

zwj1207 [专家分：40] 发布于 2006-05-27 10:38:00

注册过的朋友请到http://star.baidu.com 答题

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

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

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

输入要求：
1．文件中第一行只有一个整数M，表示蝈蝈记录了多少场比赛的分数；
2．在接下来的2M行里，每场比赛用两行记录，第一行是一个整数N(N<=1000)表示当前这个记录中有多少个字符，第二行就是具体的N个字符表示记录的分数（相邻字符用空格隔开）。例：
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

输出要求：
对应每一个分数记录，输出相应的每局分数，每局分数都使用两个整数表示，表示两个选手的得分，中间用":"分隔开；每组分数记录间使用一个空行分隔开。如果相应的比赛结果无法预测，以“UNKNOWN”一个单词独占一行表示（请全部使用大写字母）。例：
21:17
24:22
21:3

UNKNOWN

21:14
20:22
21:23
21:16
21:9

评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有4个测试数据集，每个测试数据集为一个输入文件。各测试数据集占该题目分数的比例分别为20%，30%，40%，10%；
4．该题目10分。

本帖地址： http://bbs.pfan.cn/post/169783.html

回复列表（共15个回复）

沙发

xiady [专家分：0] 发布于 2006-05-29 02:40:00

#include <vector>
#include <fstream>
#include <iostream>
#include <sstream>
#include <map>
#include <string>
using namespace std;
int mat[2];
bool judge()
{
    if (mat[0]>=21 && mat[0] - mat[1]>=2)
    {
        return true;
    }
    if (mat[1]>=21 && mat[1] - mat[0]>=2)
    {
        return true;
    }
    return false;
}

int main(int argc, char* argv[])
{
    ifstream fin(argv[1]);
    int n,m;
    char a;
    fin >> n;
    vector<string> vs;
    bool bb = true;
    bool bc = true;
    for (int i=0;i<n;i++)
    {
        fin >> m;
        bool b = false;
        for (int j=0;j<m;j++)
        {
            fin >> a;
            if(!bc)
                continue;

            if (a == 'X'&& bb)
            {
                bc = false;
            }
            bb = false;
            if (!b)
            {
                if(a!='X')
                    mat[0] += a-'0';
                else
                    mat[0] += 10;
            }
            else
            {
                if(a!='X')
                    mat[1] += a-'0';
                else
                    mat[1] += 10;
            }
            b = !b;
            if (judge())
            {
                ostringstream os;
                os << mat[0] << ":" << mat[1];
                vs.push_back(os.str());
                memset(mat,0,sizeof(mat));
                bb = true;
            }
        }
        if (bc)
        {
            for (int j = 0;j<vs.size();j++)
            {
                cout << vs[j]<<endl;
            }

        }
        else
            cout << "UNKNOWN"<<endl;
        if (i!=n-1)
        {
            cout << endl;
        }
        vs.clear();
        bc = true;
        memset(mat,0,sizeof(mat));
    }

    return 0;
}

板凳

npu007 [专家分：0] 发布于 2006-05-30 15:02:00

上面的程序还是有问题的.
例如用这组数据测试:
23
9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X X X X 1
结果应该是UNKNOWN

但上面的程序返回的却是:
21:17
24:22

另外,这道题出得不明确,我解答的所有题中，这道10分的花的时间却是最长的.

另外,感觉给的例子有问题.例如给的第二组数据:
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
题目中认为这组数据的答案应该是:
UNKNOWN
但是我的程序得到的答案是:
21:8
11:21
22:20
20:22
21:6
这个答案也是合理的.

我在求解中用到递归,实在找不到正确的简便方法了.程序近300行,累死了。

3 楼

xiady [专家分：0] 发布于 2006-05-31 22:38:00

是的，我的程序确实有问题，
baidu的4组测试数据，我只过了2组，对了一半
希望全对的人贴代码出来，3xs

4 楼

eastcowboy [专家分：25370] 发布于 2006-05-31 22:55:00

#include<stdio.h>
#include<assert.h>

#define MaxNumber 1000

static int nNumber;
static int Numbers[MaxNumber];

enum SIDE{A=0, B=1, AB=1};
enum Result{Failed=0, Success=1, Finished=2};
static int unknown;
static int a,b;
static int aWin,bWin;
static int nMatch;
static int ScoreTab[5][2];

static int hasOldAnswer;
static int Old_nMatch;
static int Old_ScoreTab[5][2];

int Win(int x, int y)
{
    if( x>=21 && x-y>1 )
        return 1;
    else
        return 0;
}

enum Result AddScore(enum SIDE side, int score)
{
    if( side == A )
    {
        a += score;
        if( Win(a,b) )
        {
            if( Win(a-1,b) )
                return Failed;
            else
            {
                ++aWin;
                ScoreTab[nMatch][A] = a;
                ScoreTab[nMatch][B] = b;
                ++nMatch;
                a = b = 0;
                if( aWin == 3 )
                    return Finished;
                else
                    return Success;
            }
        }
    }
    else
    {
        b += score;
        if( Win(b,a) )
        {
            if( Win(b-1,a) )
                return Failed;
            else
            {
                ++bWin;
                ScoreTab[nMatch][A] = a;
                ScoreTab[nMatch][B] = b;
                ++nMatch;
                a = b = 0;
                if( bWin == 3 )
                    return Finished;
                else
                    return Success;
            }
        }
    }
    return Success;
}

void Solve(int start, enum SIDE side)
{
    if( unknown )
        return;
    if( start == nNumber )
    {
        if( a!=0 || b!=0 )
            return;
        if( !hasOldAnswer )
        {
            int i;
            hasOldAnswer = 1;
            Old_nMatch = nMatch;
            for(i=0; i<nMatch; ++i)
            {
                Old_ScoreTab[i][A] = ScoreTab[i][A];
                Old_ScoreTab[i][B] = ScoreTab[i][B];
            }
        }
        else
        {
            if( Old_nMatch != nMatch )
                unknown = 1;
            else
            {
                int i;
                for(i=0; i<nMatch; ++i)
                {
                    if( Old_ScoreTab[i][A] != ScoreTab[i][A] )
                    {    unknown = 1;    break;    }
                    else if( Old_ScoreTab[i][B] != ScoreTab[i][B] )
                    {    unknown = 1;    break;    }
                }
            }
        }
        return;
    }

5 楼

eastcowboy [专家分：25370] 发布于 2006-05-31 22:55:00

    if( Numbers[start] != 10 )
    {
        enum Result tmp = AddScore(side, Numbers[start]);
        if( tmp == Failed )
            return;
        else if( tmp==Finished && nNumber-start!=1 )
            return;
        else /* Success || Finished */
            Solve(start+1, (enum SIDE)(AB-side));
    }
    else
    {
        enum Result tmp;
        int ta,tb,taWin,tbWin,tnMatch;
        ta = a;
        tb = b;
        taWin = aWin;
        tbWin = bWin;
        tnMatch = nMatch;

        tmp = AddScore(side,10);
        if( tmp == Failed )
            return;
        else if( tmp==Finished && nNumber-start!=1 )
            return;
        else
            Solve(start+1, (enum SIDE)(AB-side));

        a = ta;
        b = tb;
        aWin = taWin;
        bWin = tbWin;
        nMatch = tnMatch;
        tmp = AddScore(side,10+Numbers[start+1]);
        if( tmp == Failed )
            return;
        else if( tmp==Finished && nNumber-start!=2 )
            return;
        else
            Solve(start+2, (enum SIDE)(AB-side));
    }
}

int main(int argc, char *argv[])
{
    int nCase;
    FILE *fin;
    fin = fopen(argv[1], "r");
    if( !fin )
    {
        printf("Error: cannot open input file.\n");
        return 1;
    }
    fscanf(fin, "%d", &nCase);
    while( nCase-- )
    {
        int i;
        fscanf(fin, "%d", &nNumber);
        for(i=0; i<nNumber; ++i)
        {
            char tmp[2];
            fscanf(fin, "%s", tmp);
            if( *tmp == 'X' )
                Numbers[i] = 10;
            else
                Numbers[i] = (*tmp-'0');
        }
        hasOldAnswer = 0;
        a = b = aWin = bWin = nMatch = 0;
        unknown = 0;
        Solve(0,A);
        assert( hasOldAnswer );
        if( unknown )
            printf("UNKNOWN\n");
        else
        {
            for(i=0; i<Old_nMatch; ++i)
                printf("%d:%d\n", Old_ScoreTab[i][A], Old_ScoreTab[i][B]);
        }
        if( nCase != 0 )
            printf("\n");
    }
    fclose(fin);
    return 0;
}

6 楼

xiady [专家分：0] 发布于 2006-06-01 01:47:00

寒，还真是长啊！！

7 楼

npu007 [专家分：0] 发布于 2006-06-01 13:39:00

确实,我的也很长.

但是,4组测试数据,我也只过了两组.这道10分的题目很不值得,花费的时间最多.

要是百度公布测试数据就好,大家好明白错在哪里.

8 楼

太没劲了 [专家分：2050] 发布于 2006-06-08 18:33:00

看了下 @eastcowboy 4 楼的代码，感觉有点不对劲，象下面

[quote]
俺想错了
[/quote]

如果在 A 处 a==21, b==19, A 处 if 能过（即 Win(21,19) 返回 1），而 B 处就是 Win(20,19) 就返回 0，导致返回 Failed，实际应该进 C 处，即 A 又赢了一场。另外实际 A、B 是完全对称的，可能也有点利用价值（提高速度方面），只需要有 >=3 场 <=5 胜利且正好到尾部结束就应该算能成功，无所谓谁胜谁负。

前面关于 @eastcowboy 处想错了，不必理。又试了下，对于题目中例子 @eastcowboy 给出的答案和百度给出来的一模一样，但是我做了个就不一样，输出如下：

21:6
21:3
21:10
5:21

21:8
21:11
22:20
20:22
6:21

21:14
21:19
21:18
19:21
13:21

其中的第二个输入所得到和二楼 @npu007 的一样，得出对应拆分式

9 3 8 5 4 (9+3+5+4 =21, 8)
8 3 9 8 4 (8+3=11, 9+8+4=21)
X X X X 2 (X+X=20, X+X+2=22)
X X X X 2 (X+X=20, X+X+2=22)
8 4 9 2 4 (8+9+4=21, 4+2=6)

不明白其中有啥问题，@eastcowboy 能否指点一二（又琢磨一下好像有点明白了，如果连赢超过 10 分，比如 13，只可能记录成 X 3，而不会是 8 5 什么的，如果是 8 5，就必定是赢了 8 分丢了 5 分，或者相反，又按这个试了试，第二组还是不是 Unknown，再假定每次记录的起始得分都是固定在某边，结果把 1、2 组都给搞成 Unknown 了）。另外二楼提到的

[quote]
例如用这组数据测试:
23
9 7 3 6 2 4 7 8 3 2 7 9 X 2 2 1 2 1 X X X X 1
结果应该是UNKNOWN
[/quote]

用俺的程序试了下，得如下：

21:6
21:3
21:10
2:21
0:21

对应拆分

9 7 3 6 2   (9+7+3+2=21,6)
4 7 8 3 2   (4+7+8+2=21,3)
7 9 X 2 2 1 (7+9+2+2+1=21, 10)
2 1 X X     (2, 1+10+10)
X X 1       (10+10+1=21,0)

为啥二楼说是 UNKNOWN？

9 楼

xjy1204 [专家分：2250] 发布于 2006-06-14 15:13:00

抽空试着写了个,也不知道到哪去找测试数据了...
哪位兄弟有的话,告诉一声,也想测试一下自己写的到底有没有问题..

//--------Score.h-----------//

#pragma once

#include <vector>
#include <deque>

using namespace std;

typedef pair<int,int> Score;

typedef struct _RESULT_
{
    bool Result;
    vector<Score> resultVec;
}RESULT;

typedef struct _ALL_RESULT_
{
    int PossibleCase;
    vector<RESULT> allResults;
}ALL_RESULT;

class CScore
{
public:
    void GetData(deque<int> dataDeq);
    bool GetScore(RESULT &result);

private:
    deque<int> dataDeq;

    bool GetResult(Score curScore,bool bFlag,deque<int> restData,ALL_RESULT &result);
    bool CheckResult(RESULT &result);
    int CheckScore(Score score);
};

10 楼

xjy1204 [专家分：2250] 发布于 2006-06-14 15:21:00

//--------Score.cpp-----------//

#include "Score.h"

void CScore::GetData(deque<int> dataDeq)
{
    this->dataDeq.clear();

    this->dataDeq.insert(this->dataDeq.begin(),dataDeq.begin(),dataDeq.end());
}

bool CScore::GetScore(RESULT &result)
{
    ALL_RESULT all_result;

    all_result.PossibleCase = 0;

    Score score;
    score.first = 0;
    score.second = 0;

    GetResult(score,true,dataDeq,all_result);

    if(1 == all_result.PossibleCase)
    {
        result = all_result.allResults[0];
        return true;
    }
    else
    {
        result.Result = false;
        return false;
    }
}

我来回复

您尚未登录，请登录后再回复。点此登录或注册

主题：百度Astar2006程序设计大赛预赛题--蝈蝈计分

回复列表（共15个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：百度Astar2006程序设计大赛预赛题--蝈蝈计分

回复列表 （共15个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共15个回复）