INFOMAN брой 21
/*
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
Решение на задача ISLAND от второто контролно, Ямбол, 3 юни 2001 г.
-------------------------------------------------------------------
Условие: На острова на логиката живеят три вида същества: божествени,
които винаги казват истината; зли, които винаги лъжат и човешки същества,
които казват истината денем, а лъжат нощем. Всеки обитател на острова
може да разпознае всеки друг обитател.
Напишете програма ISLAND.EXE, която извлича информация от разговори
между съществата на острова. Информацията от която се интересуваме е
дали е ден или нощ и какви са съществата, участващи в разговора.
Вход: ISLAND.IN съдържа описание на няколко (<= 5) различни разговора.
Описанието на всеки разговор започва с цяло положително N (<= 50),
указващо брой изявления в разговора. Всяко изявление започва с името
(A, B, C, D или E) на съществото, което говори, ': ' и едно от следните
възможни изявления:
I am [not] ( divine | human | evil | lying ).
X is [not] ( divine | human | evil | lying ).
It is ( day | night ).
Краят на входния файл се означава с разговор с N = 0.
Изход: В изходния файл ISLAND.OUT за всеки разговор се извежда първо
поредния му номер на отделен ред, като се записва 'Conversation #Y',
където
Y е съотв. номер. След това на отделен ред се извежда 'This is
impossible.',
ако такъв разговор не може да се получи или 'No facts are deducible.',
ако
никаква конкретна инф. не може да се извлече от разговора. В противен
случай се извеждат всички факти, по един на ред, в следния формат:
X is ( divine | human | evil ).
It is ( day | night ).
Където X - A, B, C, D или Е. Фактите за обитателите (подредени по азбучен
ред) трябва да бъдат изведени преди това дали е ден или нощ. След всеки
разговор в изходния файл трябва да се извежда по един празен ред.
Решение: 1) Ще дефинираме определена структура тип "изявление".
То може да бъде три типа:
- Същество (не) е божество/зло/човек;
- Същество (не) лъже;
- Ден/нощ е.
Всяко изявление си има автор, като първите два типа имат и
същество-цел и един булев флаг за отрицание.
2) Рекурсивно ще проверим всички възможни комбинации от видове
за съществата
и дали е ден или нощ.
3) За всяка намерена комбинация ще проведим дали има
противоречащо
на нея изявление и ако да => тази комбинация не е възможна.
За всяко едно изявление, което проверяваме, гледаме какъв тип
е авторът му. Ако авторът в текущо разглежданата комбинация е
божество или пък е човек и е ден, то изявлението трябва да бъде
истина, ако е лъжа ще => противоречие.
Ако за даденото изявление е вдигнат флага за отрицание, ще
сменим критеря за противоречие наопаки.
4) За всяка възможна комбинация отбелязваме какви възможни
видове
сме постигнали за всяко едно от съществата и дали има възможна
комбинация при която е ден и съотв. нощ.
5) Ако не сме постигнали нито една възможна комбинация,
извеждаме
'This is impossible'.
Ако за някое от съществата има точно един възможен вид
(божество, зло или човек) извеждаме тази информация и
отбелязваме,
че сме открили конкретен факт.
По същия начин действаме и за ден/нощ. Ако напр. сме получили
възможна комбинация, при която е ден и също така друга, при
която
е нощ => нямаме конктрена инф. затова дали е ден или нощ.
6) Инф. за всяко същество, какви видове може да бъде пазим като
отделни битове. Важно е да се забележи, че е нужно след края на
всеки разговор да се нулира тази информация, за да не внесем
погрешни данни за следващия разговор.
Забележка: Във връзка с формата на списанието, вход/изходът на програмата
е променен (закоментарен) от ISLAND.IN / ISLAND.OUT, на ISLAND.C / екран.
Мартин Вълканов
E-mail: mvalkanov@yahoo.com
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DIVINE 1
#define HUMAN 2
#define EVIL 4
#define DAY 1
#define NIGHT 2
#define MAX_BEINGS 5
#define MAX_N 50
#define ST_KIND 1
#define ST_LYING 2
#define ST_DAYNIGHT 3
typedef struct { int ckind, kind, kindCnt; } being;
typedef struct { char author, target; int stKind;
int day, nt, kind; } statement;
statement smts[MAX_N];
int n;
being b[MAX_BEINGS]; int b_cnt;
int isDay;
int day;
int kinds[3] = { DIVINE, HUMAN, EVIL };
char kindStr[5][7] = { "", "divine", "human", "", "evil" };
int impossible;
void readStatements( FILE * f )
{
int i;
char word[20];
for ( i = 0; i < n; i++ )
{
fscanf( f, "%s", word ); smts[i].author = word[0] - 'A';
if ( smts[i].author >= b_cnt ) b_cnt = smts[i].author + 1;
fscanf( f, "%s", word );
if ( strcmp( word, "It" ) == 0 )
{
smts[i].stKind = ST_DAYNIGHT;
fscanf( f, "%s", word );
fscanf( f, "%s", word );
smts[i].day = ( strcmp( word, "day." ) == 0 ) ? DAY : NIGHT;
smts[i].nt = 0;
}
else
{
if ( word[0] == 'I' )
smts[i].target = smts[i].author;
else
smts[i].target = word[0] - 'A';
if ( smts[i].target >= b_cnt ) b_cnt = smts[i].target + 1;
fscanf( f, "%s", word );
fscanf( f, "%s", word );
if ( smts[i].nt = ( strcmp( word, "not" ) == 0 ) )
fscanf( f, "%s", word );
if ( strcmp( word, "lying." ) == 0 )
smts[i].stKind = ST_LYING;
else
{
smts[i].stKind = ST_KIND;
if ( strcmp( word, "divine." ) == 0 )
smts[i].kind = DIVINE;
else
if ( strcmp( word, "human." ) == 0 )
smts[i].kind = HUMAN;
else
if ( strcmp( word, "evil." ) == 0 )
smts[i].kind = EVIL;
}
}
}
}
int checkStatements( void )
{
int i;
int hasToBeTrue;
int k, kk;
for ( i = 0; i < n; i++ )
{
k = b[ smts[i].author ].ckind;
hasToBeTrue = ( ( k == DIVINE ) || ( ( k == HUMAN ) && ( day == DAY )
) );
if ( smts[i].nt ) hasToBeTrue = !hasToBeTrue;
if ( smts[i].stKind == ST_DAYNIGHT )
{
if ( ( smts[i].day == day ) != hasToBeTrue ) return 0;
}
else
if ( smts[i].stKind == ST_KIND )
{
if ( ( b[ smts[i].target ].ckind == smts[i].kind ) != hasToBeTrue )
return 0;
}
else
if ( smts[i].stKind == ST_LYING )
{
kk = b[ smts[i].target ].ckind;
if ( ( ( ( kk == EVIL ) || ( ( kk == HUMAN ) && ( day == NIGHT ) )
) ) != hasToBeTrue ) return 0;
}
}
return 1;
}
void rec( int l )
{
int i;
if ( l == b_cnt )
{
if ( checkStatements() )
{
impossible = 0;
isDay |= day;
for ( i = 0; i < b_cnt; i++ ) if ( ( b[i].kind & b[i].ckind ) == 0
)
{
b[i].kind |= b[i].ckind;
b[i].kindCnt++;
}
}
return;
}
for ( i = 0; i < 3; i++ )
{
b[l].ckind = kinds[i];
rec( l + 1 );
}
}
int nofacts = 1;
int conv_cnt = 0;
int main( void )
{
FILE * f, * t;
// f = fopen( "island.in", "r" );
// t = fopen( "island.out", "w" );
char sTemp[200];
f = fopen( "island.c", "r" ); fgets( sTemp, 200, f );
t = stdout;
for (;;)
{
fscanf( f, "%d", &n );
if ( n == 0 ) break;
readStatements(f);
impossible = 1;
for ( day = DAY; day <= NIGHT; day++ ) rec(0);
++conv_cnt;
fprintf( t, "Conversation #%d", conv_cnt );
if ( impossible )
fprintf( t, "\nThis is impossible." );
else
{
int i;
for ( i = 0; i < b_cnt; i++ ) if ( b[i].kindCnt == 1 )
{
nofacts = 0;
fprintf( t, "\n%c is %s.", i + 'A', kindStr[ b[i].kind ] );
}
for ( i = 0; i < b_cnt; i++ )
{
b[i].kind = 0;
b[i].kindCnt = 0;
}
b_cnt = 0;
if ( isDay == DAY )
{ nofacts = 0; fprintf( t, "\nIt is day." ); }
else
if ( isDay == NIGHT )
{ nofacts = 0; fprintf( t, "\nIt is night." ); }
isDay = 0;
if ( nofacts ) fprintf( t, "\nNo facts are deducible." );
nofacts = 1;
}
fprintf( t, "\n\n" );
}
fclose(t);
fclose(f);
return 0;
}