第33次编程比赛第2题结果 — 编程爱好者论坛http://bbs.pfan.cn

主题：第33次编程比赛第2题结果

[所有回帖] [只看作者帖] [只看得分帖]

作者：iAkiak

专家分：8460

级别:43

会员信息

发短消息

所属博客

发表时间：2006-6-30 13:51:00 [回复]

楼主

一共有41组数据，已经按胡牌牌型分割开，最后5手不胡。
每行第一列是百搭牌，后面3n+2张是手牌+1张牌。

引用：
41
0x03, 0x00,0x01
0x30, 0x01,0x02,0x03, 0x01,0x01,
0x30, 0x01,0x01,0x01, 0x01,0x00,
0x90, 0x01,0x02,0x03, 0x30,0x00,
0x90, 0x01,0x02,0x03, 0x00,0x00,
0x90, 0x01,0x02,0x00, 0x13,0x00,
0x01, 0x01,0x00,0x00, 0x11,0x12,0x13, 0x30,0x30,
0x03, 0x01,0x02,0x00, 0x11,0x12,0x13, 0x13,0x14,0x15, 0x14,0x15,0x16, 0x21,0x21,
0x01, 0x02,0x03,0x04, 0x11,0x12,0x13, 0x14,0x15,0x00, 0x17,0x18,0x19, 0x06,0x06,0x06, 0x05,0x16,
0x01, 0x02,0x03,0x04, 0x11,0x12,0x13, 0x14,0x15,0x00, 0x17,0x18,0x19, 0x06,0x06,0x06, 0x05,0x05,
0x30, 0x01,0x01,0x01, 0x02,0x02,0x02, 0x03,0x03,0x03, 0x04,0x04,0x04, 0x11,0x11,0x11, 0x00,0x00,
0x40, 0x01,0x01,0x01, 0x02,0x02,0x02, 0x03,0x03,0x03, 0x04,0x04,0x04, 0x11,0x11,0x11, 0x30,0x30,
0x04, 0x01,0x01,0x01, 0x02,0x02,0x02, 0x03,0x03,0x03, 0x00,0x00,0x00, 0x11,0x11,0x11, 0x30,0x30,
0x40, 0x01,0x01,0x01, 0x02,0x02,0x02, 0x03,0x03,0x03, 0x11,0x11,0x11, 0x03,0x04,0x05, 0x30,0x30,
0x30, 0x01,0x01,0x01, 0x02,0x02,0x02, 0x03,0x03,0x03, 0x11,0x11,0x11, 0x03,0x04,0x05, 0x00,0x00,
0x05, 0x01,0x01,0x01, 0x02,0x02,0x02, 0x03,0x03,0x03, 0x11,0x11,0x11, 0x03,0x04,0x05, 0x30,0x30,
0x30, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x00,0x00,
0x01, 0x00,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x02, 0x01,0x00,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x03, 0x01,0x02,0x00, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x04, 0x01,0x02,0x03, 0x00,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x05, 0x01,0x02,0x03, 0x04,0x00,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x06, 0x01,0x02,0x03, 0x04,0x05,0x00, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x11, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x00,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x12, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x00,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x30,0x30,
0x13, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x00, 0x12,0x00,0x14, 0x00,0x14,0x15, 0x30,0x30,
0x14, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x00, 0x13,0x00,0x15, 0x30,0x30,
0x15, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x00, 0x30,0x30,
0x14, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x00, 0x13,0x00,0x15, 0x00,0x00,
0x30, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x11,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x14,0x14,
0x11, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x00,0x12,0x13, 0x12,0x13,0x14, 0x13,0x14,0x15, 0x00,0x00,
0x30, 0x01,0x01,0x01, 0x11,0x11,0x11, 0x21,0x22,0x23, 0x25,0x25,0x25, 0x40,0x40,0x40, 0x24,0x24,
0x11, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x07,0x08,0x09, 0x00,0x00,0x00, 0x00,0x12,0x12, 0x12,0x12,
0x01, 0x02,0x03,0x04, 0x11,0x12,0x13, 0x14,0x15,0x16, 0x17,0x18,0x19, 0x06,0x06,0x06, 0x05,0x05,
0x30, 0x01,0x02,0x00, 0x11,0x12,0x13, 0x13,0x14,0x15, 0x14,0x15,0x16, 0x21,0x22,0x23, 0x21,0x21,
0x17, 0x01,0x02,0x03, 0x04,0x04,0x04, 0x00,0x04,0x05, 0x07,0x08,0x09, 0x07,0x08,0x09, 0x02,0x02,
0x30, 0x01,0x02,0x00, 0x11,0x12,0x13, 0x13,0x14,0x15, 0x14,0x15,0x16, 0x21,0x21,0x21, 0x24,0x23,
0x30, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x07,0x08,0x09, 0x11,0x11,0x11,0x11,0x12,0x12,0x12,0x12,
0x30, 0x01,0x02,0x03, 0x04,0x05,
0x90, 0x01,0x12,0x23,0x00,0x00,
0x90, 0x01,0x02,0x13,0x30,0x00,

下面是测试结果，我的代码还根据温州麻将计算了翻数，这里只要看是否为0就可以了。
从左往右依次是：天边蓝,sllone,ccpp,ccpp2,yxs0001,太没劲了,iAkiak

引用：
1 1 1 1 1 1 4
1 1 1 1 0 1 2
1 1 1 1 1 1 4
1 1 1 1 1 1 1
0 1 1 1 1 1 2
1 1 1 1 0 1 1
1 1 1 1 0 1 2
0 0 0 0 0 1 2
1 1 1 1 0 1 2
1 1 1 1 0 1 1
0 1 1 1 1 1 4
1 1 1 1 1 1 4
1 1 1 1 1 1 4
1 1 1 1 1 1 2
0 1 1 1 1 1 2
1 1 1 1 1 1 2
0 0 0 0 1 1 2
0 0 0 0 0 1 2
0 0 0 0 0 0 2
0 0 0 0 0 1 2
0 0 0 0 0 1 2
0 0 0 0 0 0 2
0 0 0 0 0 1 2
0 0 0 0 0 1 2
0 0 0 0 0 1 2
1 1 1 1 1 1 4
0 1 0 0 0 1 2
0 1 0 0 0 1 2
1 1 1 1 1 1 4
0 0 0 0 0 1 2
1 1 1 1 1 1 4
1 1 1 1 1 0 2
1 1 1 1 1 1 4
1 1 1 1 1 1 2
0 0 0 0 0 0 1
0 0 0 0 1 1 1
0 0 0 0 0 0 0
1 1 0 0 0 0 0
1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 0 0 0 0 0
21 26 26 26 23 37

太没劲了的程序强制修改了参数内容- -不过得分很高37分
yxs0001的程序，第二参当作n了。其实这里count就是3n+2。

真的挺难选择的。魔掌伸向太没劲了，太没劲了胜出，请准备34次比赛第2题。

走～我们去写程序！
tankwar
lumines
CurvedAni

来打我啊猛击这里打我,已经至少53级了，年轻慎入！

0

我要推荐

作者：iAkiak

专家分：8460

级别:43

会员信息

发短消息

所属博客

发表时间：2006-6-30 13:33:00 [回复] [引用]

1楼

测试使用的代码：

#include <cassert>
#include <vector>
#include <algorithm>
using namespace std;

struct Wenzhou_Mj
{
    char baida_pai; // 财神是什么牌
protected:
    struct Node
    {
        Node(char _p, char _c):pai(_p), count(_c){}
        char pai;
        char count;
    };
    int total_baida; // 是否有百搭
    int isEightPair(const vector<Node> &pai, int baida)
    {
        int count = 0, rest = 0;
        for (int i = 0; i < (int)pai.size(); i++)
        {
            if (pai[i].pai == 0)
            {
                assert(0);
            }
            else
            {
                count += pai[i].count / 2;
                rest += pai[i].count % 2;
            }
        }
        assert(count <= 8);
        assert(count * 2 + rest + baida <= 17);
        if (count * 2 + rest + baida < 17)
            return 0;
        if (count == 8)
            return 1; // 硬八对
        if (baida / 2 + count >= 8 && baida % 2 == 0)
            return 2; // 财神归位，硬八对
        int pair = min(rest, baida);
        if (baida > pair)
            pair += (baida - pair) / 2;
        if (pair + count >= 8)
            return 3; // 软八对
        return 0;
    }
    // baida数量
    // guiwei是否还有可能归位
    int TwoPai(const vector<Node> &pai, int baida, bool guiwei)
    {
        switch(baida)
        {
        case 0:
            assert(pai.size() <= 2);
            if (pai.size() == 1)
            {
                assert(pai[0].count == 2);
                return total_baida > 0 && !guiwei ? 1 : 2; // 有财神返回1倍，无财神，胡
            }
            else
            {
                return 0;
            }
            break;
        case 1:
            assert(pai.size() == 1);
            assert(pai[0].count == 1);
            return guiwei && pai[0].pai == baida_pai ? 2 : 1; // 如果最后一张财神也归位，算财神归位
            break;
        case 2:
            return guiwei ? 2 : 1; // 如果财神归位，那么余下2个财神也算归位，否则不算归位
        case 3:
        case 4:
            assert(0 && "should have been already checked");
        default:
            assert(0);
            break;
        }

        return 0;
    }
    int dfs_hu(vector<Node> &pai, int baida, int hu_max, bool guiwei, bool penonly)
    {
        int i;
        int count = baida;
        for (i = 0; i < (int)pai.size(); i++)
        {
            count += pai[i].count;
        }
        assert(count >= 2 && (count - 2) % 3 == 0);
        if (count == 2)
        {
            i = TwoPai(pai, baida, guiwei);
            if (i > 0 && penonly)
                return 4;
            return i;
        }

        for (i = 0; i < (int)pai.size() && hu_max < 4; i++)
        {
            if (pai[i].count > 3) // 刻子
            {
                pai[i].count -= 3;
                hu_max = max(hu_max, dfs_hu(pai, baida, hu_max, guiwei, penonly));
                pai[i].count += 3;
            }
            else if (pai[i].count == 3) // 刻子
            {
                vector<Node> p(pai);
                p.erase(&p[i]);
                hu_max = max(hu_max, dfs_hu(p, baida, hu_max, guiwei, penonly));
            }
        }
        for (i = 2; i < (int)pai.size() && hu_max < 4; i++)
        {
            if (pai[i].pai - pai[i - 2].pai == 2) // 顺子
            {
                if (pai[i].count > 1 && pai[i - 1].count > 1 && pai[i - 2].count > 1)
                {
                    pai[i].count--, pai[i - 1].count--, pai[i - 2].count--;
                    hu_max = max(hu_max, dfs_hu(pai, baida, hu_max, guiwei, false));
                    pai[i].count++, pai[i - 1].count++, pai[i - 2].count++;
                }
                else
                {
                    vector<Node> p(pai);
                    if (pai[i].count == 1) // 先删靠后面的
                        p.erase(&p[i]);
                    else
                        p[i].count--;
                    if (pai[i - 1].count == 1)
                        p.erase(&p[i - 1]);
                    else
                        p[i - 1].count--;
                    if (pai[i - 2].count == 1)
                        p.erase(&p[i - 2]);
                    else
                        p[i - 2].count--;
                    hu_max = max(hu_max, dfs_hu(p, baida, hu_max, guiwei, false));
                }
            }
        }
        if (hu_max < 4 && baida > 0)
        {
            // 尝试配财神
            for (i = 0; i < (int)pai.size() && hu_max < 4; i++)
            {
                bool still_guiwei = pai[i].pai == baida_pai;
                if (pai[i].count > 2) // 刻子
                {
                    pai[i].count -= 2;
                    hu_max = max(hu_max, dfs_hu(pai, baida - 1, hu_max, still_guiwei && guiwei, penonly));
                    pai[i].count += 2;
                }
                else if (pai[i].count == 2) // 刻子
                {
                    vector<Node> p(pai);
                    p.erase(&p[i]);
                    hu_max = max(hu_max, dfs_hu(p, baida - 1, hu_max, still_guiwei && guiwei, penonly));
                }
            }
            for (i = 1; i < (int)pai.size() && hu_max < 4; i++)
            {
                if (pai[i].pai - pai[i - 1].pai == 1 || pai[i].pai - pai[i - 1].pai == 2) // 顺子
                {
                    bool still_guiwei = false;
                    if (pai[i].pai - pai[i - 1].pai == 1)
                    {
                        if (baida_pai == pai[i].pai + 1 || baida_pai == pai[i - 1].pai - 1)
                            still_guiwei = true;
                    }
                    else
                    {
                        if (baida_pai == pai[i].pai - 1)
                            still_guiwei = true;
                    }
                    if (pai[i].count > 1 && pai[i - 1].count > 1)
                    {
                        pai[i].count--, pai[i - 1].count--;
                        hu_max = max(hu_max, dfs_hu(pai, baida - 1, hu_max, still_guiwei && guiwei, false));
                        pai[i].count++, pai[i - 1].count++;
                    }
                    else
                    {
                        vector<Node> p(pai);
                        if (pai[i].count == 1) // 先删靠后面的
                            p.erase(&p[i]);
                        else
                            p[i].count--;
                        if (pai[i - 1].count == 1)
                            p.erase(&p[i - 1]);
                        else
                            p[i - 1].count--;
                        hu_max = max(hu_max, dfs_hu(p, baida - 1, hu_max, still_guiwei && guiwei, false));
                    }
                }
            }
            if (hu_max < 4 && baida >= 2)
            {
                // 2百搭归位在一刻内
                for (i = 0; i < (int)pai.size(); i++)
                {
                    if (pai[i].pai == baida_pai)
                    {
                        if (pai[i].count > 1)
                        {
                            pai[i].count--;
                            hu_max = max(hu_max, dfs_hu(pai, baida - 2, hu_max, guiwei, penonly));
                            pai[i].count++;
                        }
                        else
                        {
                            vector<Node> p(pai);
                            assert(pai[i].count == 1);
                            p.erase(&p[i]);
                            hu_max = max(hu_max, dfs_hu(p, baida - 2, hu_max, guiwei, penonly));
                        }
                        break;
                    }
                }
            }
        }
        return hu_max;
    }
public:
    int GetHuCount(vector<char> shoupai, char in, bool bZiMo, bool bZhuang, bool bFirstRound, bool bPengOnly)
    {
        vector<Node> pai;
        shoupai.push_back(in);
        sort(shoupai.begin(), shoupai.end());
        int baida = 0;
        while(!shoupai.empty() && shoupai.front() == 0)
        {
            shoupai.erase(shoupai.begin());
            baida++;
        }
        int i, count = 1;
        total_baida = baida;
        if (baida == 4)
        {
            return 4; // 4张财神，不必判断，直接返回4
        }
        if (shoupai.size() == 0)
        {
            assert(baida == 2); // 余下2财神
            return 4;
        }
        else if (shoupai.size() == 1)
        {
            assert(baida == 1);
            if (in == 0) // 最后一张是财神，不算财神单吊
                return bPengOnly ? 4 : 2;
            return 4; // 财神单吊
        }
        for (i = 1; i < (int)shoupai.size(); i++)
        {
            if (shoupai[i] != shoupai[i - 1])
            {
                pai.push_back(Node(shoupai[i - 1], count));
                count = 1;
            }
            else
                count++;
        }
        pai.push_back(Node(shoupai.back(), count));
        int max_hu = 0;
        switch(isEightPair(pai, baida))
        {
        default:
            assert(0);
        case 0:
            break;
        case 1:// 硬八对
        case 2:// 财神归位，硬八对
            return 4;
        case 3:// 软八对
            max_hu = 2;
        }

        int hu = dfs_hu(pai, baida, 0, true, bPengOnly);
        switch(hu)
        {
        default:
            assert(0);
        case 0:
            if (baida == 3)
                hu = 2;
            break;
        case 1:
        case 2:
            if (baida == 3)
                hu = 4;
        case 4:
            break;
        }
        max_hu = max(max_hu, hu);
        if (max_hu > 0 && bFirstRound) // 天胡,地胡不看庄
            max_hu = 4;
        return max_hu;
    }
};

最后修改于2006-6-30 13:33:00

作者：iAkiak

专家分：8460

级别:43

会员信息

发短消息

所属博客

发表时间：2006-6-30 13:35:00 [回复] [引用]

2楼

测试使用的代码，续

// 选手代码
namespace p1
{
#include "p1.cpp"
}
// ... 其他选手同上

#include <cstdio>
int main()
{
    Wenzhou_Mj a;
    freopen("pai.txt", "r", stdin);
    int n;
    char buf[1024];
    scanf("%d\n", &n);
    int score[6] = {0};

    for (int i = 0; i < n; i++)
    {
        fgets(buf, sizeof(buf), stdin);
        vector<char> pai, p2;
        for (char *b = strtok(buf, ","); b; b = strtok(NULL, ","))
        {
            int data;
            if (sscanf(b, "%x", &data) == 1)
                pai.push_back((char)data);
        }
        a.baida_pai = pai.front();
        pai.erase(pai.begin());
        char last = pai.back();
        p2 = pai;

        sort(pai.begin(), pai.end());

        int res[6];
        printf("%d ", res[0] = p1::TestHu(pai.begin(), pai.size(), a.baida_pai));
        printf("%d ", res[1] = sllone::TestHu(pai.begin(), pai.size(), a.baida_pai));
        printf("%d ", res[2] = ccpp::TestHu(pai.begin(), pai.size(), a.baida_pai));
        printf("%d ", res[3] = ccpp2::TestHu(pai.begin(), pai.size(), a.baida_pai));
        printf("%d ", res[4] = yxs0001::TestHu(pai.begin(), pai.size()/3, a.baida_pai));
        printf("%d ", res[5] = p_5::TestHu(pai.begin(), pai.size(), a.baida_pai)); //edit data

        p2.pop_back();
        int r;
        printf("%d\n", r=a.GetHuCount(p2, last, false, false, false, true));

        if (r==0)
        {
            res[0] || score[0]++;
            res[1] || score[1]++;
            res[2] || score[2]++;
            res[3] || score[3]++;
            res[4] || score[4]++;
            res[5] || score[5]++;
        }
        else
        {
            res[0] && score[0]++;
            res[1] && score[1]++;
            res[2] && score[2]++;
            res[3] && score[3]++;
            res[4] && score[4]++;
            res[5] && score[5]++;
        }
    }
    printf("%d %d %d %d %d %d\n", score[0], score[1], score[2], score[3], score[4], score[5]);
    return 0;
}

作者：太没劲了

专家分：2050

级别:11

会员信息

发短消息

所属博客

发表时间：2006-6-30 13:43:00 [回复] [引用]

3楼

引用：
真的挺难选择的。魔掌伸向太没劲了，太没劲了胜出，请准备34次比赛第2题。

错了四个还是俺啊，

，如果还有下次千万千万千万别这样，俺先看看错了的四个错在那先．

19，22 行是因为顺可以中间加百搭，这地方我没能处理对。32、35 还需要再查查看。

又查了一下错，发现俺错的太多太离谱了，结果能对那么多纯属误打误撞，贴个修改后的代码，也更简练点，如下（把杠也补上了）：

bool solve(char pai[], int count,int pos,int baidanum)
{
    int type,i,j,startpos;
    char backup[32];

    if( (count<=0 || pos>=count) ) return(baidanum>1 || 0==baidanum );

    for(i=pos;i<count && (unsigned char)pai[i] > (unsigned char)0x90 ; ++i);
    if( i==count ) return(baidanum>1 || 0==baidanum );
    startpos = i;
    memcpy(backup,&pai[startpos],count-startpos);
    for(type=0; type<2; ++type) /* 0 shun, 1 jiang,ke,gang */
    {
        int ipos[4],maxdeal=1,getv,mark=0,inum;

        ipos[0] = startpos;
        if( 0==type )
        {
            if( !((getv = pai[startpos]/0x10)>=0 && getv<3) ) continue;
            for(j=startpos+1; j<count && maxdeal<3; ++j)
            {
                if( !mark && ((unsigned char)pai[startpos]+1)==pai[j] )
                    mark=1, ipos[maxdeal++] = j;
                else if( ( (unsigned char)pai[startpos]+2) ==pai[j] )
                {
                    ipos[maxdeal++] = j;
                    break;
                }
            }
            if( maxdeal+baidanum <3 ) continue;
        }
        else
        {
            for(j=startpos+1; j<count && maxdeal<4; ++j)
                if( pai[startpos]==pai[j] ) ipos[maxdeal++] = j;
        }

        for(inum=maxdeal; inum>0 ; --inum)
        {
            int bnum=0,bitem[4];

            if( 0==type )
            {
                if( baidanum< (3-inum) ) break;
                bnum = 1, bitem[0] = 3-inum;
            }
            else
            {
                for(int k=0 ;k<=baidanum && (inum+k)<=4; ++k)
                {
                    if( inum+k <2 ) continue;
                    bitem[bnum++] = k;
                }
            }
            for(j=0; j<bnum; ++j)
            {
                for(int k=0; k<inum; pai[ ipos[k] ] = (unsigned char)0x91, ++k);
                if( solve(pai,count,startpos+1,baidanum-bitem[j]) ) return(true);
                memcpy(&pai[startpos], backup, count-startpos);
            }
        }
    }

    return(false);
}

bool TestHu(const char pai[], int count, char baida)
{
    char dealpai[32];
    int pos=0;

    for(int i=0;i<count; ++i)
        if( !(pai[i]==0 || ( (unsigned char)0x90==(unsigned char)baida && pai[i]==baida )) )
            dealpai[pos++] = pai[i];
    return( solve(dealpai,pos,0,count-pos) );
}

这个能对 40 组

@iAkiak，俺再问点事，运行修改后的程序发现如下组和标准不一样（倒数第四组）：

0x30, 0x01,0x02,0x03, 0x04,0x05,0x06, 0x07,0x08,0x09, 0x11,0x11,0x11,0x11,0x12,0x12,0x12,0x12,

这个按
0x01,0x02,0x03
0x04,0x05,0x06
0x07,0x08,0x09
0x11,0x11
0x11,0x11
0x12,0x12
0x12,0x12

或者
0x01,0x02,0x03
0x04,0x05,0x06
0x07,0x08,0x09
0x11,0x11,0x11,0x11
0x12,0x12,0x12,0x12

应该能胡，为啥你那标成 0．

最后发现这个对俺来说还是很复杂，开始说不复杂说错了．

最后修改于2006-7-1 9:50:00

作者：天边蓝

专家分：1810

级别:10