回 帖 发 新 帖 刷新版面

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

注册过的朋友请到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分。

回复列表 (共15个回复)

沙发

#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;
}

板凳

上面的程序还是有问题的.
例如用这组数据测试:
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 楼


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

4 楼

#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 楼

    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 楼

寒,还真是长啊 !!

7 楼

确实,我的也很长.

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

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

8 楼

看了下 @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 楼

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

//--------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 楼

//--------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;
    }
}

我来回复

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