Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:其实就是枚举,麻烦点

Posted by zyz913614263 at 2011-12-04 10:03:03 on Problem 1478
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator