|
|
思路：
由于数据量比较小，可以枚举ABCDE的所有身份和时间（白天或者晚上），不会超时。
判断deducible、impossible的部分很难写，基本上是照着数据改的。。
1. 如果没有任何状态是符合要求的，输出 impossible。
2. 在符合要求的状态中，如果对于某个人的身份或者时间，存在分歧，那该条就不能输出。
3. 在（2）的情况下，如果没有任何输出，就输出 deducible。
快被这玩意整疯了。要是没有数据肯定搞不出来。
 #include <stdio.h>
#define MAX_N 6
  enum kind_t  {
 NONE,
ROLE_START,
DIVINE = ROLE_START, HUMAN, EVIL,
ROLE_END = EVIL,
ANY_ROLE,
LYING,
TIME_START,
DAY = TIME_START,
NIGHT,
TIME_END = NIGHT,
ANY_TIME
 };
char *str_tbl[] = {
"none",
"divine", "human", "evil", "any_role",
"lying",
"day", "night", "any_time"
};
struct node {
int x, y, not, type;
};
struct node in[64];
struct stat {
int role[MAX_N], time;
};
struct stat ans, cur;
int N;
__inline void input(struct node *t)
{
char a[32], b[32];
scanf("%s%s", a, b);
t->x = a[0] - 'A';
if (b[0] == 'I')
t->y = t->x;
else
t->y = b[0] - 'A';
scanf("%s%s", a, b);
  if (b[0] == 'n' && b[1] == 'o') {
t->not = 1;
scanf("%s", b);
 } else
t->not = 0;
if (b[0] == 'd')
t->type = (b[1] == 'a') ? DAY : DIVINE;
else if (b[0] == 'h')
t->type = HUMAN;
else if (b[0] == 'e')
t->type = EVIL;
else if (b[0] == 'l')
t->type = LYING;
else
t->type = NIGHT;
}
__inline int lies(int x)
{
return (cur.role[x] == EVIL) || (cur.role[x] == HUMAN && cur.time == NIGHT);
}
__inline int check_one(struct node *t)
{
int right;
if (t->type >= ROLE_START && t->type <= ROLE_END)
right = t->not ^ (cur.role[t->y] == t->type);
else if (t->type == LYING)
right = t->not ^ lies(t->y);
else {
if (t->type == DAY)
right = (cur.time == DAY);
else
right = (cur.time == NIGHT);
}
return lies(t->x) ? !right : right;
}
__inline void check()
{
int i;
for (i = 0; i < N; i++)
if (!check_one(&in[i]))
return ;
for (i = 0; i < MAX_N; i++) {
if (ans.role[i] == NONE)
ans.role[i] = cur.role[i];
else if (ans.role[i] != cur.role[i])
ans.role[i] = ANY_ROLE;
}
if (ans.time == NONE)
ans.time = cur.time;
else if (ans.time != cur.time)
ans.time = ANY_TIME;
}
__inline void solve()
{
int i, mask, cnt, *arr[MAX_N];
mask = 0;
for (i = 0; i < N; i++) {
mask |= 1 << in[i].x;
mask |= 1 << in[i].y;
}
for (cnt = i = 0; i < MAX_N; i++) {
if (mask & (1 << i)) {
arr[cnt++] = &cur.role[i];
cur.role[i] = ROLE_START;
} else
cur.role[i] = NONE;
ans.role[i] = NONE;
}
ans.time = NONE;
while (1) {
cur.time = DAY;
check();
cur.time = NIGHT;
check();
for (i = 0; i < cnt && *arr[i] == ROLE_END; i++)
*arr[i] = ROLE_START;
if (i == cnt)
break;
(*arr[i])++;
}
}
__inline void dump()
{
int i, cnt;
for (i = 0; i < MAX_N && ans.role[i] == NONE; i++);
if (i == MAX_N && ans.time == NONE) {
printf("This is impossible.\n\n");
return ;
}
for (cnt = i = 0; i < MAX_N; i++) {
if (ans.role[i] >= ROLE_START && ans.role[i] <= ROLE_END) {
cnt++;
printf("%c is %s.\n", i + 'A', str_tbl[ans.role[i]]);
}
}
if (ans.time >= TIME_START && ans.time <= TIME_END) {
printf("It is %s.\n", str_tbl[ans.time]);
cnt++;
}
if (!cnt) {
printf("No facts are deducible.\n\n");
return ;
}
putchar('\n');
}
int main()
{
int i, t;
freopen("e:\\test\\in.txt", "r", stdin);
for (t = 1; scanf("%d", &N), N; t++) {
for (i = 0; i < N; i++)
input(&in[i]);
printf("Conversation #%d\n", t);
solve();
dump();
}
return 0;
}
|