/*
  Name:6.剪刀石头布
  Copyright:
  Author:
  Date: 28-05-06 08:51
  Description:
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

 

输出要求:
1.每组测试数据输出一行,若能猜出谁是裁判,则输出裁判的编号,并输出在第几次游戏结束后就能够确定谁是裁判,小孩的编号和游戏次数以一个空格隔开;
2.如果无法确定谁是裁判,输出-2;如果发现剪刀石头布游戏的胜负情况不合理(即无论谁是裁判都会出现矛盾),则输出-1。例:
-2
1 4
-1
0 0

 

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

/*
算法介绍:
1。如果只有1个人,参加比赛,那么他就是裁判,即输出:0 0 。
2。建立数组 players[MAX][MAX] 记录比赛结果(数组赋初值0),若选手a输给b,则players[a][b]=1,players[b][a]=3;若打平,则players[a][b]=players[b][a]=2;
注意:在记录成绩之前,先判断选手a,b 是否已经比赛过,如果已经比赛过,则判断先前的比赛结果是否与当前结果相同,若不相同,在数组judger[]中做标记(数组赋初值0),若judger[a]=0,使judger[a]=1,表示a有可能为裁判;若judger[a]=1,则使judger[a]=2,表示a肯定为裁判,因为他和两个人出现不同结果。
同理处理b。
3。遍历数组judger[],用temp1记录judger[i]=1出现的次数,用temp2记录judger[i]=2出现的次数,如果2个或以下的人可能为裁判,且没有人肯定为裁判,即if (temp1 <= 2 && temp2 == 0),则无法确定谁是裁判;
如果2个或以下的人可能为裁判,且有1人肯定为裁判,即if (temp1 <= 2 && temp2 == 1),则确定裁判i;
如果2个以上的人可能为裁判,即if (temp1 > 2),则胜负情况不合理。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 500;
void Readata(const char *filename);


int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

 Readata("in.txt");


 time(&endTime);
 cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void Readata(const char *filename)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            int N, M;
            in >> N;
            in >> M;
           
            if (N == 1) //如果只有1个人,参加比赛,那么他就是裁判
                  cout << 0 << ' ' << 0 << endl;
                 
            int players[MAX][MAX] = {0};//记录比赛结果
            int *judger = new int[N];//记录是否可能为裁判,0表示不可能,1表示可能,2表示确定
            for (int i=0; i<N; i++)
                  judger[i] = 0;
                 
            int n = 0;//累计比赛场数
            int min = n;//存储能够确定谁是裁判的最少场数
            while (!in.eof() && n < M)//读入比赛结果信息
            {
                  char data[3]; //存储比赛选手编号和结果

                  in >> data[0];
                  in >> data[1];
                  in >> data[2];
                 // cout << data[0] << ' ' << data[1] << ' ' << data[2] << endl;
                  n++;
                  int flag = (data[1]=='<')? 1 :((data[1]=='=')? 2 : 3);//分别用1,2,3表示负,平,胜
                 
                  if (players[data[0]-'0'][data[2]-'0'] == 0)//若a,b未对局过,存储比赛结果
                  {
                        players[data[0]-'0'][data[2]-'0'] = flag;
                        players[data[2]-'0'][data[0]-'0'] = 4 - flag;
                  }
                  else if (players[data[0]-'0'][data[2]-'0'] != flag)//若a,b已对局过,且比赛结果不同
                  {
                        if (judger[data[0]-'0'] == 0) //a有可能为裁判
                              judger[data[0]-'0'] = 1;
                        else if (judger[data[0]-'0'] == 1)//a就是裁判
                        {
                              judger[data[0]-'0'] = 2;
                              min = n;
                        }
                       
                        if (judger[data[2]-'0'] == 0) //b有可能为裁判
                              judger[data[2]-'0'] = 1;
                        else if (judger[data[2]-'0'] == 1) //a就b是裁判
                        {
                              judger[data[2]-'0'] = 2;
                              min = n;
                        }
                  }
                 // cout << "players["<<data[0]-'0'<<"]["<<data[2]-'0'<<"]="<<players[data[0]-'0'][data[2]-'0']<<endl;
            }
            int temp1 = 0; //记录judger[i]=1出现的次数
            int temp2 = 0; //记录judger[i]=2出现的次数
            int answer;
            for (int i=0; i<N; i++)
            {
                  //cout << judger[i] << ' ';
                  if (judger[i] == 1)
                       temp1++;

                  if (judger[i] == 2)
                  {
                       temp2++;
                       answer = i;
                  }
            }
            cout << endl;
            if (temp1 <= 2 && temp2 == 0)
                  cout << -2 << endl;
            else  if (temp1 <= 2 && temp2 == 1)
                  cout << answer << ' ' << min << endl;
            else  if (temp1 > 2)
                  cout << -1 << endl;
                 
            delete []judger;
      }

    in.close(); //关闭文件
}

 

Posted on 2006-05-30 13:59 梦想飞扬 阅读(573) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理