首页 > ACM题库 > HDU-杭电 > Hdu 1470 Island of Logic[解题报告] C++
2013
12-11

Hdu 1470 Island of Logic[解题报告] C++

Island of Logic

问题描述 :

The Island of Logic has three kinds of inhabitants: divine beings that always tell the truth, evil beings that always lie, and human beings that are truthful during the day and lie at night. Every inhabitant recognizes the type of every other inhabitant.
A social scientist wants to visit the island. Because he is not able to distinguish the three kinds of beings only from their looks, he asks you to provide a communication analyzer that deduces facts from conversations among inhabitants. The interesting facts are whether it is day or night and what kind of beings the speakers are.

输入:

The input contains several descriptions of conversations. Each description starts with an integer n, the number of statements in the conversation. The following n lines each contain one statement by an inhabitant. Every statement line begins with the speaker’s name, one of the capital letters A, B, C, D, E, followed by a colon `:’. Next is one of the following kinds of statements:

I am [not] ( divine | human | evil | lying ).

X is [not] ( divine | human | evil | lying ).

It is ( day | night ).

Square brackets [] mean that the word in the brackets may or may not appear, round brackets () mean that exactly one of the alternatives separated by | must appear. X stands for some name from A, B, C, D, E. There will be no two consecutive spaces in any statement line, and at most 50 statements in a conversation.

The input is terminated by a test case starting with n = 0.

输出:

For each conversation, first output the number of the conversation in the format shown in the sample output. Then print “This is impossible.”, if the conversation cannot happen according to the rules or “No facts are deducible.”, if no facts can be deduced. Otherwise print all the facts that can be deduced. Deduced facts should be printed using the following formats:

X is ( divine | human | evil ).

It is ( day | night ).

X is to be replaced by a capital letter speaker name. Facts about inhabitants must be given first (in alphabetical order), then it may be stated whether it is day or night.

The output for each conversation must be followed by a single blank line.

样例输入:

1
A: I am divine.
1
A: I am lying.
1
A: I am evil.
3
A: B is human.
B: A is evil.
A: B is evil.
0

样例输出:

Conversation #1
No facts are deducible.

Conversation #2
This is impossible.

Conversation #3
A is human.
It is night.

Conversation #4
A is evil.
B is divine.

Reasoning made easy 

To make things clearer, we will show the reasoning behind the third input example, where A says ``I am evil.''.
 What can be deduced from this? 
Obviously A cannot be divine, since she would be lying, similarly A cannot be evil, since she would tell the truth. 
Therefore, A must be human, moreover, since she is lying, it must be night. So the correct output is as shown. 

In the fourth input example, it is obvious that A is lying since her two statements are contradictory. 
So, B can be neither human nor evil, and consequently must be divine. B always tells the truth, thus A must be evil. Voil‘a!


这道题虽然不是很难,但是由于我代码功底实在太渣了,一开始写烂了,有一个数组定义的太小,结果出现无厘头的错误,调了好久才过。另外提交的时候一开始是CE,调一下发现原来“not”是不能当为变量名的,虽然我到现在也不知道为什么,接着切题,同时也不能荒废了学习,加油!

#include "stdio.h"
#include "string.h"
int main()
{
    char str[1000][20];
    int n,i,answer[10][500],count[10],number=0,j,zeronum,bigonenum,role[10],time,ok,identity,
    others,nott,divine,evil,human,lying,day,night;
    while(scanf("%d",&n)==1)
    {
        if(n==0) break;
        getchar();
        memset(str,0,sizeof(str));
        for(i=1;i<=n;i++)
            gets(str[i]);
        printf("Conversation #%d\n",++number);
        memset(count,0,sizeof(count));
        for(role[1]=1;role[1]<=3;role[1]++)
        for(role[2]=1;role[2]<=3;role[2]++)
        for(role[3]=1;role[3]<=3;role[3]++)
        for(role[4]=1;role[4]<=3;role[4]++)
        for(role[5]=1;role[5]<=3;role[5]++)
        for(time=1;time<=2;time++)
        {
            ok=1;
            for(i=1;i<=n;i++)
            {
                identity=str[i][0]-64;
                nott=0;
                for(j=0;str[i][j+3]!='\0';j++)
                    if(str[i][j]=='n'&&str[i][j+1]=='o'&&str[i][j+2]=='t')
                    {nott=1;break;}
                divine=0;
                for(j=0;str[i][j+2]!='\0';j++)
                    if(str[i][j]=='d'&&str[i][j+1]=='i')
                    {divine=1;break;}
                evil=0;
                for(j=0;str[i][j+2]!='\0';j++)
                    if(str[i][j]=='e'&&str[i][j+1]=='v')
                    {evil=1;break;}
                human=0;
                for(j=0;str[i][j+2]!='\0';j++)
                    if(str[i][j]=='h'&&str[i][j+1]=='u')
                    {human=1;break;}
                lying=0;
                for(j=0;str[i][j+2]!='\0';j++)
                    if(str[i][j]=='l'&&str[i][j+1]=='y')
                    {lying=1;break;}
                day=0;
                for(j=0;str[i][j+2]!='\0';j++)
                    if(str[i][j]=='d'&&str[i][j+1]=='a')
                    {day=1;break;}
                night=0;
                for(j=0;str[i][j+2]!='\0';j++)
                    if(str[i][j]=='n'&&str[i][j+1]=='i')
                    {night=1;break;}
                if(str[i][3]=='I')
                    others=identity;
                else others=str[i][3]-64;
                if(role[identity]==1)
                {
                    if(day==1)
                    {
                        if(nott==1)
                        {
                            if(time==1)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==2)
                            {ok=0;break;}
                        }
                    }
                    if(night==1)
                    {
                        if(nott==1)
                        {
                            if(time==2)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==1)
                            {ok=0;break;}
                        }
                    }
                    if(divine==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]==1)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]!=1)
                            {ok=0;break;}
                        }
                    }
                    if(evil==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]==2)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]!=2)
                            {ok=0;break;}
                        }
                    }
                    if(human==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]==3)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]!=3)
                            {ok=0;break;}
                        }
                    }
                    if(lying==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]==2)
                            {ok=0;break;}
                            else if(time==2&&role[others]==3)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]==1)
                            {ok=0;break;}
                            else if(role[others]==3&&time==1)
                            {ok=0;break;}
                        }
                    }
                }
                else if(role[identity]==2)
                {
                    if(day==1)
                    {
                        if(nott==1)
                        {
                            if(time!=1)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==1)
                            {ok=0;break;}
                        }
                    }
                    if(night==1)
                    {
                        if(nott==1)
                        {
                            if(time!=2)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==2)
                            {ok=0;break;}
                        }
                    }
                    if(divine==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]!=1)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]==1)
                            {ok=0;break;}
                        }
                    }
                    if(evil==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]!=2)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]==2)
                            {ok=0;break;}
                        }
                    }
                    if(human==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]!=3)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]==3)
                            {ok=0;break;}
                        }
                    }
                    if(lying==1)
                    {
                        if(nott==1)
                        {
                            if(role[others]==1)
                            {ok=0;break;}
                            else if(time==1&&role[others]==3)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(role[others]==2)
                            {ok=0;break;}
                            else if(role[others]==3&&time==2)
                            {ok=0;break;}
                        }
                    }
                }
                else if(role[identity]==3)
                {
                    if(day==1)
                    {
                        if(nott==1)
                        {
                            ok=0;break;
                        }
                    }
                    if(night==1)
                    {
                        if(nott==0)
                        {
                            ok=0;break;
                        }
                    }
                    if(divine==1)
                    {
                        if(nott==1)
                        {
                            if(time==1&&role[others]==1)
                            {ok=0;break;}
                            else if(time==2&&role[others]!=1)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==1&&role[others]!=1)
                            {ok=0;break;}
                            else if(time==2&&role[others]==1)
                            {ok=0;break;}
                        }
                    }
                    if(evil==1)
                    {
                        if(nott==1)
                        {
                            if(time==1&&role[others]==2)
                            {ok=0;break;}
                            else if(time==2&&role[others]!=2)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==1&&role[others]!=2)
                            {ok=0;break;}
                            else if(time==2&&role[others]==2)
                            {ok=0;break;}
                        }
                    }
                    if(human==1)
                    {
                        if(nott==1)
                        {
                            if(time==1&&role[others]==3)
                            {ok=0;break;}
                            else if(time==2&&role[others]!=3)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==1&&role[others]!=3)
                            {ok=0;break;}
                            else if(time==2&&role[others]==3)
                            {ok=0;break;}
                        }
                    }
                    if(lying==1)
                    {
                        if(nott==1)
                        {
                            if(time==1&&role[others]==2)
                            {ok=0;break;}
                            else if(time==2&&role[others]==1)
                            {ok=0;break;}
                        }
                        else
                        {
                            if(time==1&&role[others]==1)
                            {ok=0;break;}
                            else if(time==1&&role[others]==3)
                            {ok=0;break;}
                            else if(role[others]==3&&time==2)
                            {ok=0;break;}
                            else if(role[others]==2&&time==2)
                            {ok=0;break;}
                        }
                    }
                }
                }
                if(ok==1)
                {
                    for(j=1;j<=5;j++)
                    {
                        if(role[j]==answer[j][count[j]])
                            continue;
                        ++count[j];
                        answer[j][count[j]]=role[j];
                    }
                    if(answer[6][count[6]]!=time)
                    {
                        ++count[6];
                        answer[6][count[6]]=time;
                    }
                }
                }
                zeronum=0;
                bigonenum=0;
                for(i=1;i<=6;i++)
                {
                    if(count[i]==0)
                        ++zeronum;
                    else if(count[i]>1)
                        ++bigonenum;
                }
                if(zeronum>0)
                    printf("This is impossible.\n\n");
                else if(bigonenum==6)
                    printf("No facts are deducible.\n\n");
                else
                {
                    for(i=1;i<=5;i++)
                    if(count[i]==1)
                    {
                        printf("%c is ",i+64);
                        if(answer[i][1]==1)
                            printf("divine.\n");
                        else if(answer[i][1]==2)
                            printf("evil.\n");
                        else printf("human.\n");
                    }
                    if(count[6]==1)
                        if(answer[6][1]==1)
                            printf("It is day.\n");
                        else printf("It is night.\n");
                    printf("\n");
                }
    } 
                return 0;
}

 


  1. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测