原题链接
讨厌模拟啊啊。。
因为不喜欢用(string)，所以用(char)数组打了一十分冗长的初始化。。
枚举今天是星期几及罪犯是谁，然后对每句话进行判断这个人讲的是真是假，如果没有冲突，那么最后计算说假话的总人数是否满足要求即可。
若有多种关于罪犯是谁的假设成立，那么就是不止一个罪犯；若没有假设成立，那么就是不可能有人为罪犯。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 110;
const int M = 25;
const int K = 260;
struct dd {
int id, x, y;
};
dd tmy[N];
int nam_l[N], fake[M], nw_l, sen_l, n;
char sen[K], nam[M][N], nw[N];
char tr[6][M] = { "", "I am guilty.", "I am not guilty.", " is guilty.", " is not guilty.", "Today is " };
char da[8][M] = { "", "Monday.", "Tuesday.", "Wednesday.", "Thursday.", "Friday.", "Saturday.", "Sunday." };
bool e;
inline void re_nam(char *o, int &l)
{
char c = getchar();
for (; c < 'A' || c > 'Z'; c = getchar());
for (l = 0; c != '
' && c != '
' && c != ' ' && c != ':'; c = getchar())
o[l++] = c;
}
inline void re_sen(char o[], int &l)
{
char c = getchar();
for (; (c < 'A' || c > 'Z') && (c < 'a' || c > 'z'); c = getchar());
for (l = 0; c != '
' && c != '
' && c > 0; c = getchar())
o[l++] = c;
}
inline int fin()
{
bool p;
for (int i = 1; i <= n; i++)
if (!(nam_l[i] ^ nw_l))
{
p = 0;
for (int j = 0; j < nw_l && !p; j++)
if (nam[i][j] ^ nw[j])
p = 1;
if (!p)
return i;
}
return 0;
}
inline int fin_day()
{
int i, j, l;
for (i = 1; i <= 7; i++)
if (!((l = strlen(da[i])) ^ nw_l))
{
for (j = 0; j < l; j++)
if (da[i][j] ^ nw[j])
break;
if (j >= l)
return i;
}
return 0;
}
inline bool chos(int i, int x, int y)
{
int j, l = strlen(tr[i]);
if ((y - x) ^ l)
return false;
for (j = 0; j < l; j++)
if (sen[j + x] ^ tr[i][j])
return false;
return true;
}
inline void dm(int x, int y) { fake[x] >= 0 && fake[x] ^ y ? e = 1 : fake[x] = y; }
int main()
{
int i, j, m, p, td, g = 0;
scanf("%d%d%d", &n, &m, &p);
for (i = 1; i <= n; i++)
re_nam(nam[i], nam_l[i]);
for (i = 1; i <= p; i++)
{
re_nam(nw, nw_l);
tmy[i].id = fin();
re_sen(sen, sen_l);
if (chos(1, 0, sen_l))
tmy[i].x = 1;
else
if (chos(2, 0, sen_l))
tmy[i].x = 2;
else
{
for (nw_l = j = 0; j < sen_l; j++)
if (sen[j] < 'A' || sen[j] > 'Z')
break;
else
nw[nw_l++] = sen[j];
int k = fin();
if (k && chos(3, j, sen_l))
tmy[i].x = 3, tmy[i].y = k;
else
if (k && chos(4, j, sen_l))
tmy[i].x = 4, tmy[i].y = k;
else
if (chos(5, 0, 9))
{
for (nw_l = 0, j = 9; j < sen_l; j++)
nw[nw_l++] = sen[j];
k = fin_day();
if (k)
tmy[i].x = 5, tmy[i].y = k;
}
}
}
for (i = 1; i <= n; i++)
for (td = 1; td < 8; td++)
{
memset(fake, -1, sizeof(fake));
e = 0;
for (j = 1; j <= p && !e; j++)
{
int x = tmy[j].id, k = tmy[j].x;
if (!k)
continue;
if (!(k ^ 1))
dm(x, i ^ x ? 1 : 0);
else
if (!(k ^ 2))
dm(x, i ^ x ? 0 : 1);
else
if (!(k ^ 3))
dm(x, i ^ tmy[j].y ? 1 : 0);
else
if (!(k ^ 4))
dm(x, i ^ tmy[j].y ? 0 : 1);
else
dm(x, td ^ tmy[j].y ? 1 : 0);
}
if (e)
continue;
int s_1 = 0, s_2 = 0;
for (j = 1; j <= n; j++)
if (fake[j] > 0)
s_1++;
else
if (fake[j] < 0)
s_2++;
if (s_1 <= m && m <= s_1 + s_2)
{
if (g && g ^ i)
{
printf("Cannot Determine");
return 0;
}
g = i;
}
}
if (!g)
printf("Impossible");
else
for (i = 0; i < nam_l[g]; i++)
printf("%c", nam[g][i]);
return 0;
}