2013编程之美资格赛【传话游戏】

时间限制: 1000ms 内存限制: 256MB

描述

Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位。然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位……以此类推,直到倒数第二位告诉Bob。两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释。最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家。 

由于传话过程中可能出现一些偏差,游戏者越多,Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西,所以大家玩得乐此不疲。经过几轮游戏后,Alice注意到在两人传话中,有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表,她想知道她的话传到Bob时会变成什么样子,请你写个程序来帮助她。

输入

输入包括多组数据。第一行是整数 T,表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M,分别表示游戏者的数量和单词转化列表长度。随后有 M 行,每行包含两个用空格隔开的单词 a 和 b,表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词,表示Alice所想的句子,句子总长不超过100个字符。所有单词都只包含小写字母,并且长度不超过20,同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。

输出

对于每组测试数据,单独输出一行“Case #c: s”。其中,c 为测试数据编号,s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。

数据范围

1 ≤ T ≤ 100

小数据:2 ≤ N ≤ 10, 0 ≤ M ≤ 10 

大数据:2 ≤ N ≤ 100, 0 ≤ M ≤ 100 

样例输入
2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear

#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
using namespace std;

int main()
{
    int T;
    cin>>T;
    if(T<1||T>100)
        return 0;
    string result[100];
    int N,M;
    map<string,string> mapstring;
    for(int k=0;k<T;++k){
        cin>>N>>M;
        if(N<2||N>10||M<0||M>10)
            return 0;
        string s1,s2,str[1000];
        mapstring.clear();
        for(int i=0;i<M;++i){
            cin>>s1>>s2;
            if(s1.size()>20||s2.size()>20)
                return 0;
            mapstring.insert(pair <string,string>( s1, s2 ));
        }
        int itr=0;
         string ss;
        getchar();
        getline(cin,ss);
        string::iterator p=ss.begin();
        while(p!=ss.end()){
            if(*p==' ')
                ++itr;
            else
                str[itr].push_back(*p);
            ++p;
        }
        itr=0;
        map<string, string>::iterator iter;
        while(str[itr]!=""){
            for(int i=0;i<N-1;++i){
                iter=mapstring.find(str[itr]);
                if(iter!=mapstring.end())
                    str[itr]=iter->second;
                else
                    break;
            }
            itr++;
        }
        if(str[itr]=="")
            if(itr>100)
                return 0;
        else
            if(itr>99)
                return 0;
        itr=0;
        while(str[itr]!=""){
            string tmp=str[itr]+" ";
            result[k]+=tmp;
            itr++;
        }
        result[k]=result[k].substr(0,result[k].length()-1);
    }
    for(int i=0;i<T;++i)
        cout<<"Case #"<<i+1<<": "<<result[i]<<endl;
    return 0;
}

以前没做过ACM,一个空格PE了一个小时。。。。。。。。。。。。。。。。。蛋碎了


本文 由 cococo点点 创作,采用 知识共享 署名-非商业性使用-相同方式共享 3.0 中国大陆 许可协议进行许可。欢迎转载,请注明出处:
转载自:cococo点点 http://www.cnblogs.com/coder2012

时间: 2024-10-30 06:36:43

2013编程之美资格赛【传话游戏】的相关文章

2013编程之美资格赛之长方形(Java实现)

长方形 时间限制: 1000ms 内存限制: 256MB 描述 在 N 条水平线与 M 条竖直线构成的网格中,放 K 枚石子,每个石子都只能放在网格的交叉点上.问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子. 输入 输入文件包含多组测试数据. 第一行,给出一个整数T,为数据组数.接下来依次给出每组测试数据. 每组数据为三个用空格隔开的整数 N,M,K. 输出 对于每组测试数据,输出一行"Case #X: Y",其中X表示测试数据编号,Y表示

2013编程之美资格赛之树上的三角形(Java实现)

树上的三角形 时间限制: 2000ms 内存限制: 256MB 描述 有一棵树,树上有只毛毛虫.它在这棵树上生活了很久,对它的构造了如指掌.所以它在树上从来都是走最短路,不会绕路.它还还特别喜欢三角形,所以当它在树上爬来爬去的时候总会在想,如果把刚才爬过的那几根树枝/树干锯下来,能不能从中选三根出来拼成一个三角形呢? 输入 输入数据的第一行包含一个整数 T,表示数据组数. 接下来有 T 组数据,每组数据中: 第一行包含一个整数 N,表示树上节点的个数(从 1 到 N 标号). 接下来的 N-1

2013编程之美资格赛之传话游戏(Java实现)

传话游戏 时间限制: 1000ms 内存限制: 256MB 描述 Alice和Bob还有其他几位好朋友在一起玩传话游戏.这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位.然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位--以此类推,直到倒数第二位告诉Bob.两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释.最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家.  由于传话过

2013编程之美资格赛总结

终于可以完成一个程序比赛的题目了,虽然这次的时间有些长.这是第一次完成,感到真心不错.参加程序比赛是受舍友的影响,但很快就喜欢上了.但,从前不见第一次参加程序比赛--腾讯的编程马拉松,一个题不会,连提交代码的心思都没有.到第二次,参加百度的百度之星,百度之星参加了两次区域赛,第一次做的唯一一道题连题意都没有明白,结果不言而喻,失败:第二次区域赛,明白了题意,写出来代码,但提交结果还是失败,因为没有对于大数据进行思考.这就是参加的两次比赛的情况.这是第三次参加,是微软的编程之美,依据现在的结果,感

2013编程之美资格赛之大数据测试(JAVA)

传话游戏大数据通过 长方形WA.原因是求长方形数量时,用到了四数连乘,哦,其结果就是超出Int型表示的范围,WA是必然的. 树上的三角形TLE.这个也是在情理之内,由于我连树的构造都不太会实现,自己想的一种方法构造了一种类树(就是类似的树).时间会比较长,超时也在情理之中. 哦.说一下结果,   题目1 题目2 题目3 名次 大赛ID 得分 罚时 10分 20分 15分 20分 15分 20分 622 fxleyu 60 165:32:12 AC AC AC WA AC TLE  好吧,这就是这

2013编程之美全国挑战赛资格赛之传话游戏

时间限制: 1000ms 内存限制: 256MB 描述 Alice和Bob还有其他几位好朋友在一起玩传话游戏.这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位.然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位--以此类推,直到倒数第二位告诉Bob.两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释.最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家.  由于传话过程中可能出

2013编程之美全国挑战赛第一场-传话游戏

传话游戏 时间限制: 1000ms 内存限制: 256MB 描述 Alice和Bob还有其他几位好朋友在一起玩传话游戏.这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位.然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位--以此类推,直到倒数第二位告诉Bob.两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释.最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家. 由于传话过程

2013编程之美全国挑战赛第二场-集会

昨天做编程之美的题感觉只有这一道是水题.思路没问题但是写程序写错了一个地方没AC.今天翻出来想了一下终于解决了. 解题思路: 要寻找的这个目标点的纵坐标为0,设横坐标为x.以示例数据为例,可以得到目标点到这些点的距离,更直观一点,绘制成图形点击查看.观察可知符合要求的点可能出现的位置是某两个抛物线的交点或者某个抛物线的顶点.求出这些点来比较计算出的距离,取最小的即可.没机会提交的代码如下: import java.util.Scanner; public class Main { public

2013编程之美-测试赛

题目列表 > A + B 时间限制: 1000ms 内存限制: 1024MB 描述 输入两个正整数A和B, 求A+B的值 输入 两个正整数A, B 输出 A+B的和 对于小数据, 0 < A, B <= 10; 对于大数据, 0 < A, B <= 10100 样例输入 2 3 样例输出 5 #include<iostream> #include<cstring> using namespace std; int* strtoint(char *str