现在的位置: 首页 > 综合 > 正文

剪刀石头布游戏

2013年01月20日 ⁄ 综合 ⁄ 共 4402字 ⁄ 字号 评论关闭

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

N 个小孩正在和你玩一种剪刀石头布游戏。 N 个小孩中有一个是裁判,其余小孩分成三组(不排除某些组没有任何成员的可能性),但是你不知道谁是裁判,也不知道小孩们的分组情况。然后,小孩们开始玩剪刀石头布游戏,一共玩 M 次,每次任意选择两个小孩进行一轮,你会被告知结果,即两个小孩的胜负情况,然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势(因而同一组的两个小孩总会是和局),而裁判则每次都会随便选择出一种手势,因此没有人会知道裁判到底会出什么。请你在 M 次剪刀石头布游戏结束后,猜猜谁是裁判。如果你能猜出谁是裁判,请说明最早在第几次游戏结束后你就能够确定谁是裁判。

输入格式:

输入文件包含多组测试数据。每组测试数据第一行为两个整数 N 和 M ( 1 ≤ N ≤ 500 , 0 ≤ M ≤ 2000 ),分别为小孩的个数和剪刀石头布游戏进行的次数。接下来 M 行,每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号,为小于 N 的非负整数。符号的可能值为“ = ”、“ > ”和“ < ”,分别表示和局、第一个小孩胜和第二个小孩胜三种情况。

输出格式:

每组测试数据输出一行,若能猜出谁是裁判,则输出身为裁判的小孩的编号,并输出在第几次游戏结束后就能够确定谁是裁判。如果无法确定谁是裁判,或者发现剪刀石头布游戏的胜负情况不合理(即无论谁是裁判都会出现矛盾),则输出相应的信息。具体输出格式请参考输出样例。

输入样例

3 3

0<1

1<2

2<0

3 5

0<1

0>1

1<2

1>2

0<2

4 4

0<1

0>1

2<3

2>3

1 0

输出样例

Can not determine

Player 1 can be determined to be the judge after 4 lines

Impossible

Player 0 can be determined to be the judge after 0 lines

说明:

共有 5 个测试数据集,每个测试数据集为一个输入文件,包含多组测试数据。每个测试数据集从易到难分别为 5 、 10 、 15 、 30 和 40 分,对每个测试数据集分别执行一次程序,每次必须在运行时限 3 秒内结束程序并输出正确的答案才能得分。

所有数据均从标准输入设备( stdin/cin )读入,并写出到标准输出设备 ( stdout/cout )中。

五个测试数据集中输入 N 分别不大于 20 、 50 、 100 、 200 和 500 ,各有 10 组测试数据。

//说明:最低四位表示child分组状态,0:未分组,1/2/3:三组,4:裁判
//次低四位表示child检查状态,0:在以前数据中未出现,
//1:已出现一次,第二次出现即可进行检查判断,2:检查后可能是裁判,3:检查后不可能是裁判
//
using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Threading;
using System.IO;
public class childclqr
    {
        int n;
        int m;
        int[,] data;
        int[] child;
        int[] maybecps;
        int cpps=-1;
        string result; 
        public string Result
        { get { done();return result; } }
        public childclqr(int n,int m,string[]ss)
        {
            this.n = n; this.m = m; 
            data=new int[m,4];
            child=new int[n];
            maybecps=new int[n+1];
            for (int k = 0; k < m; k++)
            {
                data[k, 0] = 0;
                sws(ss[k],k);
            }
        }
        public childclqr(string infile,string outfile)
        {
            FileStream fs = new FileStream(infile,FileMode.Open,FileAccess.Read);
            StreamReader sr = new StreamReader(fs);
            FileStream fo = new FileStream(outfile,FileMode.Create,FileAccess.Write);
            StreamWriter sw = new StreamWriter(fo);
            string s = sr.ReadLine();
            while(s!=null)
            {
                string[] t = s.Split();
                n = int.Parse(t[0]);
                m = int.Parse(t[1]);
                t=new string[m];
                for (int j = 0; j < m; j++)
                    t[j] = sr.ReadLine();
                childclqr c = new childclqr(n,m,t);
                sw.WriteLine(c.Result);
                s = sr.ReadLine();
            }
            sr.Close();
            sw.Close();
        }
        void sws(string s,int n)
        {
            data[n, 1] = 0;
            data[n, 3] = 0;
            int k = 0;
            while (s[k] <= '9' && s[k] >= '0') 
                data[n, 1] = 10 * data[n, 1] + s[k++] - '0';
            data[n, 2] = s[k++];
            while(k<s.Length)
            data[n, 3] = 10 * data[n, 3] + s[k++] - '0';
            if (data[n, 2] == '<')
            {
                 
                data[n, 2] = data[n, 1];
                data[n, 1] = data[n, 3];
                data[n, 3] = data[n, 2];
                data[n, 2] = '>';
            }
        }
        bool maybecp(int c,int k)//在前k组data中假设c为cp,是否没有矛盾
        {
            int j=0;
            for (; j < n; j++)       //清除分组情况
                child[j] &= 0xf0;
            int left = k + 1,begin=0;
            for (j = 0; j <= k; j++)       //有c的data置1,其余置0
            {
                if (data[j, 1] == c || data[j, 3] == c)
                { data[j, 0] = 1; left--; }
                else
                    data[j, 0] = 0;
            }
            child[c] |= 4;       //c置为cp
            while (left > 1)       //left为剩余data,剩余至少两条时进行计算
            {
                while (data[begin, 0] == 1) begin++;       //找到第一个未计算的data
                child[data[begin, 1]] += 1;       //假定第一个child的分组
                for (j = begin; j <=k; j++)
                    if(data[j,0]==0)
                    {
                        int za = child[data[j, 1]]%16, zb = child[data[j, 3]]%16;
                        int sign = data[j, 2];
                        data[j, 0] = 1;
                        left--;
                        if (za > 0 && zb > 0)       //若双方已分组,则判断是否有矛盾,有则返回错误
                        { if ((sign == '=' && za != zb) || (za != (zb + 1) % 3 + 1))return false; }
                        //一方已分组,一方未知,确定未知方的分组,并返回begin重新计算
                        else if (za == 0 && zb > 0)       
                        {
                            if (sign == '=') child[data[j, 1]] += zb;
                            else child[data[j, 1]] += (zb + 1) % 3 + 1;
                            j = begin - 1;
                        }
                        else if (za > 0 && zb == 0)
                        {
                            if (sign == '=') child[data[j, 3]] += za;
                            else child[data[j, 3]] += za % 3 + 1;
                            j = begin - 1;
                        }
                        else       //双方都未分组,原begin已计算,则重定为当前值 
                        { data[j, 0] = 0; left++; if (data[begin, 0] == 1)begin = j; }
                    }
            }
            return true;       //没有矛盾,返回true
        }
        void readytomaybe(int b,int k)
        {
            if (child[b] >> 4 == 1)
            {
                if (maybecp(b, k))
                {
                    child[b] += 0x10;
                    maybecps[++maybecps[0]] = b;
                    if (maybecps[0] == 1)
                        cpps = k;
                    return;
                }
                else
                {
                    child[b] += 0x20;
                    return;
                }
            }
        }
        void toleft(int mlen)
        {
            if (mlen!=maybecps[0]&&maybecps[0] > 0)
                {
                    int r = 1;
                    while (maybecps[r] != -1) r++;
                    int p = r+1;
                    while (r<=maybecps[0])
                    {
                        while(maybecps[p]==-1)p++;
                        maybecps[r++] = maybecps[p];
                        maybecps[p++]=-1;
                    }
                }
        }
        void anay(int k)
        { 
            int a=data[k,1];
            int b = data[k, 3];
            if (child[a] >> 4 == 0 || child[b] >> 4 == 0)    //若ab中有一个以前未出现
            {
                int t = a;
                a = child[a] >> 4 == 0 ? a : b;
                b = t != a ? t : b;
                child[a] |= 0x10;     //将a设为ready
                if (child[b] >> 4 == 0)
                { child[b] |= 0x10; return; }
                else
                    readytomaybe(b,k);     //若b为ready则进行检查
                return;
            }
            else
            {
                int t=-1,mlen = maybecps[0];
                if (mlen == 1) t = maybecps[1];
                for (int j = 1; j <=mlen; j++)    //检查maybecps中的每个成员
                    if (!maybecp(maybecps[j], k))
                    { 
                        child[maybecps[j]] += 0x10;
                        maybecps[j] = -1;
                        maybecps[0]--;
                    }
                toleft(mlen);    //调整maybecps
                readytomaybe(a,k);
                readytomaybe(b,k);
                if (maybecps[0] == 1 && t != maybecps[1])    //若有变化,记下cpps
                    cpps = k;
            }
        }
        void done()
        {
            if (m == 0)
            { result = "Player 0 can be determined to be the judge after 0 lines "; return; }
            for (int k = 0; k < m; k++)
                anay(k);
            if (maybecps[0] == 0)
                result = "Impossible !";
            else if (maybecps[0] == 1)
                result = string.Format("Child {0} is judge,he can be judged after {1} lines",maybecps[1],cpps+1);
            else result = "Can not determine!";
        }
    }

抱歉!评论已关闭.