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