问题 C: Color

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

Alice, Bob and Yazid are good friends.

Each of them has a color, red, green or blue. Everyone’s color is different from the others’. They can describe their own colors in the format of name is color., such as Yazid is green..

Now they have made their descriptions in some order. After that, Yazid will do the following operations:

1.Connect the 3 sentences to get the initial string.

2.Remove all non-alphabetic characters.

3.Change all uppercase letters to lowercase.

For example, if the initial string is Yazid is green.Alice is red.Bob is blue., then after Yazid’s all operations, it will be turned to yazidisgreenaliceisredbobisblue.

Finally, Alice and Bob will insert any lowercase letters into any positions in this string to get the final string.

You are given the final string. Your task is to find the initial string. In particular:

•If there are multiple solutions, please output the minimum one in lexical order.

•If there is no solution, please output No solution. instead.

输入

Read from the standard input.

The first line contains one integer T (T ≤ 500), representing the number of test cases. For each case:

•One line of a string containing only lowercase letters, representing the final string.

•It is guaranteed that the length of the final string won’t exceed 600.

输出

Write to the standard output.

For each case:

•One line of a string, representing the initial string or No solution..

样例输入

4

aliceisredbobisblueyazidisgreen

aliceisgreenbobisgreenyazidisgreen

aliceisyellowbobisblueyazidisgreen

xxyazidxxisxxgreenxxbobisblueaxlxixcxexixsxrxexdx

样例输出

Alice is red.Bob is blue.Yazid is green.

No solution.

No solution.

Yazid is green.Bob is blue.Alice is red.

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
 
using namespace std;
const int N=1000;
 
string s;
bool vis[30];
string outp,geti;
string name[3];
string color[3];
string out[100];
bool visn[3],visc[3];
int cnt;
 
void build(int len,string temp)
{
    if(len==3)
    {
        //cout<<temp<<endl;
        out[cnt++]=temp;
        return;
    }
    for(int i=0;i<3;i++)
    {
        if(visn[i]) continue;
        for(int j=0;j<3;j++)
        {
            if(visc[j]) continue;
            string t=temp+name[i]+" is "+color[j]+".";
            visn[i]=true;
            visc[j]=true;
            build (len+1,t);
            visn[i]= false;
            visc[j]=false;
        }
    }
}
void init()
{
    ios::sync_with_stdio (false);
    s="aliceisredbobisblueyazidisgreen";
    for(int i=0;i<s.size ();i++)  if(isalpha (s[i])) vis[s[i]-'a']= true;
    name[0]="Alice";
    name[1]="Bob";
    name[2]="Yazid";
    color[2]="red";
    color[1]="green";
    color[0]="blue";
    build(0,"");
    sort(out,out+cnt);
   // cout<<out[0]<<endl;
}
 
int main()
{
    init ();
    int T;
    cin>>T;
    while (T--)
    {
        cin>>geti;
        outp.clear();
        for(int i=0;i<geti.size();i++) if(vis[geti[i]-'a']) outp.push_back (geti[i]);
        bool flag= true;
        for(int i=0;i<cnt;i++)
        {
            int j=0;
            for(int k=0;k<outp.size ();k++)
            {
                if(outp[k]==tolower (out[i][j]))
                {
                    j++;
                    while (out[i][j]==' ' || out[i][j]=='.') j++;
                }
            }
            if(j==out[i].size ())
            {
                cout<<out[i]<<endl;
                flag=false;
                break;
            }
        }
        if(flag) cout<<"No solution."<<endl;
    }
}