Skip to content

11255: 【原1255】你的魔戒?不,是你的魔戒。

题目

题目描述

author: Kalethars 张晔 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1255 

Description

在前往末日火山的途中,佛罗多与他的霍比特人同胞不幸被半兽人抓住了。 半兽人要对每个霍比特人进行询问,以找出哪个霍比特人携带了至尊魔戒。

每个霍比特人可能会说以下几种话:

I have the ring. 我有魔戒。

I have not the ring. 我没有魔戒。

XXX has the ring. XXX有魔戒。(XXX表示某个霍比特人的名字)

XXX has not the ring. XXX没有魔戒。

Today is XXX. 今天天气真好,是XXX吧!(XXX表示Monday/Tuesday/Wednesday/Thursday/Friday/Saturday/Sunday其中之一,只有首字母大写)

询问中所回答的其他话,都不列入考虑的范围之内。

半兽人所知道的是,霍比特人中有N个人始终说假话,而其他人始终说真话。

每个霍比特人可能会回答多句话也可能不会回答。

但是现在有人听不懂这些话,你需要帮忙他处理。

每句话对应三元组(f,t,c),对应关系如下(其中speakerid是说话者的id):

I have the ring. -> (speakerid, speakerid, 1)

I have not the ring. -> (speakerid, speakerid, 2)

XXX has the ring. -> (speakerid, XXX's id, 1)

XXX has not the ring. -> (speakerid, XXX's id, 2)

Today is XXX. -> (speakerid, xxx, 3),其中(XXX=Monday->xxx=1, XXX=Tuesday->xxx=2, ..., XXX=Sunday->xxx=7)

询问中所回答的其他话,即废话,不输出。

Input Format

输入由若干行组成,第一行有二个整数,M(1<=M<=10)、N(1<=N<=M)和P(1<=P<=20)。

M是半兽人抓到的霍比特人数,N是其中始终说谎的人数,P是得到的回答的总数。

接下来M行,每行是一个霍比特人的名字(英文字母组成,全部大写),他们的id按顺序为0到M-1。

往后有P行,每行开始是某个霍比特人的名宇,紧跟着一个冒号和一个空格,后面是一句回答,符合前表中所列格式。 回答每行不会超过250个字符。

输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。

Output Format

输出若干行,对每句非废话,输出三个空格隔开的整数。 如果全是废话,输出"Orz"(不包含引号).

Sample Input

3 1 5
FRODO
SAM
GOLLUM
FRODO: I have the ring.
FRODO: Today is Sunday.
GOLLUM: FRODO has the ring.
SAM: I have the ring.
SAM: How are you??

Sample Output

0 0 1
0 7 3
2 0 1
1 1 1

Hint

对于60%的数据,将不涉及到星期几(但是可能有废话)。

要#include , 使用string。

使用getline(cin,变量名)来读入整行的字符串,如string name; getline(cin, name)。

使用getchar()来读入可能有的多余的字符(如回车等等),如char ch = getchar()。

使用.find(str)来找到这个字符串第一次出现的位置,如strig word; ...; int loc = word.find(":")。

使用.substr(起始位置,长度)来截取字符串,如string name1 = word.substr(0, loc)。

使用==判断字符串相等,如string name1, name2; ...; name1==name2;

使用.length()获取字符串的长度,如int len = name.length();

WashSwang's solution

#include <iostream>
#include <string>
using namespace std;
string s,name[30],who,towho,days[7]={"Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};
int m,n,p,mh,f,t,c,succ,pos;
char ch;
int findname(string name1)
{
    for (int j=0;j<m;++j)
        if (name1==name[j])
            return j;
    return -1;
}
int main() {
    cin>>m>>n>>p;
    ch=getchar();
    for (int i=0;i<m;++i){
        getline(cin,name[i]);
    }
    for (int i=0;i<p;++i){
        getline(cin,s);
        mh=s.find(':');
        who=s.substr(0,mh);
        c=-1;
        f=findname(who);
        if (f==-1) continue;
        pos=s.find('.');
        if (pos!=s.length()-1) continue;
        pos=s.find(" have the ring.");
        if (pos!=-1) {
            if (pos - mh == 3 && s[pos - 1] == 'I' && s[mh + 2] == 'I') {
                t = f;
                c = 1;
            }
        }
        else{
            pos=s.find(" have not the ring.");
            if (pos!=-1) {
                if (pos - mh == 3 && s[pos - 1] == 'I' && s[mh + 2] == 'I') {
                    t = f;
                    c = 2;
                }
            }
            else{
                pos=s.find(" has the ring.");
                if (pos!=-1){
                    t=findname(s.substr(mh+2,pos-2-mh));
                    if (t!=-1) c=1;
                }
                else{
                    pos=s.find(" has not the ring.");
                    if (pos!=-1){
                        t=findname(s.substr(mh+2,pos-2-mh));
                        if (t!=-1) c=2;
                    }
                    else{
                        pos=s.find(" Today is ");
                        if (pos!=-1){
                            t=-1;
                            for (int j=0;j<7;++j)
                                if (s.find(days[j])==pos+10)
                                {
                                    t=j+1;
                                    break;
                                }
                            if (t!=-1) c=3;
                        }
                    }
                }
            }
        }
        if (c!=-1)
        {
            succ++;
            cout<<f<<" "<<t<<" "<<c<<endl;
        }
    }
    if (!succ) cout<<"Orz"<<endl;
    return 0;
}