1,鸣谢Jimmy Carlson Wang带我翻译题目

2,这个题他有至少50%的功劳.

题目链接:http://codeforces.com/gym/100202/attachments/download/1698/20032004-winter-petrozavodsk-camp-andrew-stankevich-contest-6-en.pdf

题目翻译:(还是特别鸣谢Jimmy Carlson Wang!)

你在一个房间,你可以做出几个操作:

1,捡起地上的东西(输出pick sth)

2,拿若干个东西放到另一个Object上使用(输出在下面)(用完你的东西还在)

3,和Character说话(talk to sb.)

4,拿东西去找Character换,换完你的东西不在了

5,开门(open the door to 某房间)

6,救公主(save princess)

(救不了输出一行"dead princess")

数据保证:

1,东西不超过200个,Object和Character也不超过200个

2,每个东西只能通过一种途径(捡起,Object,Character)获得

3,每个东西最多使用在一个Character上一次,不会有多个Character都要它

4,每个东西都不会既用在Object上,也用在Character上

5,门的钥匙不会用在Object或者Character上

6,两个房间之间最多一个门而且是双向的

样例解释:

样例1:

有4个房间,分别是白色,蓝色,绿色,黑色

有3个门:

1,白-蓝 用的是水晶钥匙

2,白-绿 用的是esmerald钥匙(目测出题人拼错了,应该是emerald翻译为翡翠,下面就用翡翠钥匙代替了)

3,蓝-黑 用的是神奇钥匙

白色房间内:

有0个Character,0个Object

地上有两个东西,一个是水晶钥匙,一个是橘子

黑色房间内没有任何东西(除了公主)

蓝色房间内,有2个Character,1个Object,地上没东西

第一个Character名字叫Wild Joe

你给他老鼠,红辣椒和钱,他就会把神奇钥匙给你

第二个Character名字叫Dead man

他需要橘子汁,能给你红辣椒和翡翠钥匙

那个Object是榨汁机

把橘子放在榨汁机上,能获得橘子汁(而且橘子还能再用..)

绿色门内,有一个Object,地上有个东西

那个Object是猴子

把橘子喂给猴子,它会给你钱

地上有老鼠

攻略:

拿起地上的水晶钥匙和橘子,开门,到蓝色门内

把橘子炸了,得到橘子汁,跟死人说话,喂他橘子汁,获得辣椒和翡翠钥匙

去(经过白色)绿色门,开门,到绿色门内,把橘子喂给猴子得到钱,回蓝色门找Wild Joe,拿神奇钥匙开门救公主

样例2:没有门你怎么救公主?

注意:

1,格式

2,救不了输出"dead princess"

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[1005];
char stop_flag;
void read()
{
    char x;
    for (;;)
    {
        x=getchar();
        if (x!=' ') break;
    }
    int sum=1;
    a[0]=x;
    for (;;)
    {
        a[sum]=getchar();
        if ((a[sum]=='\n')||(a[sum]==',')||(a[sum]==-1))
        {
            stop_flag=a[sum];
            for (;(a[sum-1]==' ')||(a[sum-1]=='\r');)
            {
                sum--;
            }
            a[sum]='\0';
            return;
        }
        sum++;
    }
}
map<string,int> ma;
string room[15];
int x[65],y[65];
struct character
{
    string name;
    int need[305];
    int offer[305];
};
character b[15][305];
struct object
{
    string name;
    int need[305];
    int offer[305];
};
object c[15][305];
int d[15][305];
string items[305];
map<string,int> item;
bool visit[15];
int open[65];
bool can_visit[15];
int own[305];
int n;
int m;
int get_num()
{
    static int sum=0;
    string b=a;
    if (item.find(b)==item.end())
    {
        item[b]=sum;
        items[sum]=b;
        sum++;
    }
    return item[b];
}
void dfss(int now,int goal,int flag=0)
{
    if (!flag) printf("go to %s\n",room[now].c_str());
    if (visit[now]) return;
    visit[now]=true;
    if (now==goal) return;
    int i;
    for (i=0;i<m;i++)
    {
        if (!open[i]) continue;
        if (x[i]==now)
        {
            dfss(y[i],goal);
            if (visit[goal]) return;
            printf("go to %s\n",room[now].c_str());
        }
        if (y[i]==now)
        {
            dfss(x[i],goal);
            if (visit[goal]) return;
            printf("go to %s\n",room[now].c_str());
        }
    }
}
void dfs(int x,int y)
{
    memset(visit,false,sizeof(visit));
    dfss(x,y,1);
}
int main()
{
    freopen("quest.in","r",stdin);
    freopen("quest.out","w",stdout);
    ios::sync_with_stdio(false);
    scanf("%d",&n);
    int i;
    getchar();
    for (i=0;i<n;i++)
    {
        read();
        room[i]=a;
        ma[a]=i;
    }
    scanf("%d",&m);
    for (i=0;i<m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        x[i]--;
        y[i]--;
        read();
        get_num();
    }
    for (i=0;i<n;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        getchar();
        int j;
        for (j=0;j<x;j++)
        {
            int t=0;
            read();
            b[i][j].name=a;
            for (;;)
            {
                read();
                b[i][j].need[t++]=get_num();
                if (stop_flag=='\n') break;
            }
            b[i][j].need[t]=-1;
            t=0;
            for (;;)
            {
                read();
                b[i][j].offer[t++]=get_num();
                if (stop_flag=='\n') break;
            }
            b[i][j].offer[t]=-1;
        }
        for (j=0;j<y;j++)
        {
            int t=0;
            read();
            c[i][j].name=a;
            for (;;)
            {
                read();
                c[i][j].need[t++]=get_num();
                if (stop_flag=='\n') break;
            }
            c[i][j].need[t]=-1;
            t=0;
            for (;;)
            {
                read();
                c[i][j].offer[t++]=get_num();
                if (stop_flag=='\n') break;
            }
            c[i][j].offer[t]=-1;
        }
        for (j=0;j<z;j++)
        {
            read();
            d[i][j]=get_num();
        }
        d[i][z]=-1;
    }
    read();
    int start=ma[a];
    read();
    int end=ma[a];
    can_visit[start]=true;
    //can_do_list:
    //1,go to another room(with key)
    //2,pick up something
    //3,talk to a character or use object
    memset(own,0,sizeof(own));
    int now=start;
    for (;;)
    {
        if (can_visit[end])
        {
            dfs(now,end);
            printf("save princess\n");
            return 0;
        }
        int i;
        for (i=0;i<m;i++)
        {
            if ((own[i])&&((can_visit[x[i]])^(can_visit[y[i]])))
            {
                if (can_visit[x[i]])
                {
                    dfs(now,x[i]);
                    now=x[i];
                    printf("open door to %s\n",room[y[i]].c_str());
                    can_visit[y[i]]=true;
                    open[i]=true;
                    break;
                }
                if (can_visit[y[i]])
                {
                    dfs(now,y[i]);
                    now=y[i];
                    printf("open door to %s\n",room[x[i]].c_str());
                    can_visit[x[i]]=true;
                    open[i]=true;
                    break;
                }
            }
        }
        if (i!=m) continue;
        for (i=0;i<n;i++)
        {
            if (can_visit[i])
            {
                if (d[i][0]==-1) continue;
                dfs(now,i);
                now=i;
                int j;
                for (j=0;d[i][j]!=-1;j++)
                {
                    printf("pick %s\n",items[d[i][j]].c_str());
                    own[d[i][j]]=true;
                }
                d[i][0]=-1;
                break;
            }
        }
        if (i!=n) continue;
        for (i=0;i<n;i++)
        {
            if (can_visit[i])
            {
                int j;
                for (j=0;b[i][j].name.length()!=0;j++)
                {
                    if (b[i][j].need[0]==-1) continue;
                    int k;
                    for (k=0;b[i][j].need[k]!=-1;k++)
                    {
                        if (!own[b[i][j].need[k]])
                        {
                            break;
                        }
                    }
                    if (b[i][j].need[k]==-1)
                    {
                        dfs(now,i);
                        now=i;
                        printf("talk to %s\n",b[i][j].name.c_str());
                        int k;
                        printf("give");
                        for (k=0;b[i][j].need[k]!=-1;k++)
                        {
                            if (k==0)
                            {
                                printf(" ");
                            }
                            else if (b[i][j].need[k+1]==-1)
                            {
                                printf(" and ");
                            }
                            else
                            {
                                printf(", ");
                            }
                            printf("%s",items[b[i][j].need[k]].c_str());
                        }
                        printf(" to %s\n",b[i][j].name.c_str());
                        printf("take");
                        for (k=0;b[i][j].offer[k]!=-1;k++)
                        {
                            own[b[i][j].offer[k]]=true;
                            if (k==0)
                            {
                                printf(" ");
                            }
                            else if (b[i][j].offer[k+1]==-1)
                            {
                                printf(" and ");
                            }
                            else
                            {
                                printf(", ");
                            }
                            printf("%s",items[b[i][j].offer[k]].c_str());
                        }
                        printf(" from %s\n",b[i][j].name.c_str());
                        b[i][j].need[0]=-1;
                        break;
                    }
                }
                if (b[i][j].name.length()!=0) break;
            }
        }
        if (i!=n) continue;
        for (i=0;i<n;i++)
        {
            if (can_visit[i])
            {
                int j;
                for (j=0;c[i][j].name.length()!=0;j++)
                {
                    if (c[i][j].need[0]==-1) continue;
                    int k;
                    for (k=0;c[i][j].need[k]!=-1;k++)
                    {
                        if (!own[c[i][j].need[k]])
                        {
                            break;
                        }
                    }
                    if (c[i][j].need[k]==-1)
                    {
                        dfs(now,i);
                        now=i;
                        int k;
                        printf("use");
                        for (k=0;c[i][j].need[k]!=-1;k++)
                        {
                            if (k==0)
                            {
                                printf(" ");
                            }
                            else if (c[i][j].need[k+1]==-1)
                            {
                                printf(" and ");
                            }
                            else
                            {
                                printf(", ");
                            }
                            printf("%s",items[c[i][j].need[k]].c_str());
                        }
                        printf(" on %s\n",c[i][j].name.c_str());
                        printf("take");
                        for (k=0;c[i][j].offer[k]!=-1;k++)
                        {
                            own[c[i][j].offer[k]]=true;
                            if (k==0)
                            {
                                printf(" ");
                            }
                            else if (c[i][j].offer[k+1]==-1)
                            {
                                printf(" and ");
                            }
                            else
                            {
                                printf(", ");
                            }
                            printf("%s",items[c[i][j].offer[k]].c_str());
                        }
                        printf(" from %s\n",c[i][j].name.c_str());
                        c[i][j].need[0]=-1;
                        break;
                    }
                }
                if (c[i][j].name.length()!=0) break;
            }
        }
        if (i!=n) continue;
        break;
    }
    freopen("quest.out","w",stdout);
    printf("dead princess\n");
    return 0;
}