| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:其实就是枚举,麻烦点In Reply To:其实就是枚举,麻烦点 Posted by:J_M at 2010-02-02 22:00:19 #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[][50] = {
"none",
"divine", "human", "evil", "any_role",
"lying",
"day", "night", "any_time"
};
struct node {
int x, y, no, 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->no = 1;
scanf("%s", b);
} else
t->no = 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->no ^ (cur.role[t->y] == t->type);
else if (t->type == LYING)
right = t->no ^ 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;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator