算法训练 黑白无常
时间限制：1.0s 内存限制：256.0MB
问题描述
某寝室的同学们在学术完之后准备玩一个游戏：游戏是这样的，每个人头上都被贴了一张白色或者黑色的纸，现在每个人都会说一句话“我看到x张白色纸条和y张黑色的纸条”，又已知每个头上贴着白色纸的人说的是真话、每个头上贴着黑色纸的人说的是谎话，现在要求你判断哪些人头上贴着的是白色的纸条，如果无解输出“NoSolution.”；如果有多组解，则把每个答案中贴白条的人的编号按照大小排列后组成一个数（比如第一个人和第三个人头上贴着的是白纸条，那么这个数就是13；如果第6、7、8个人都贴的是白纸条，那么这个数就是678）输出最小的那个数（如果全部都是黑纸条也满足情况的话，那么输出0）
输入格式
第一行为一个整数n，接下来n行中的第i行有两个整数x和y，分别表示第i个人说“我看到x张白色纸条和y张黑色的纸条”。
输出格式
一行。如果无解输出“NoSolution.”。否则输出答案中数值（具体见问题描述）最小的那个，如果全部都是黑纸条也满足情况的话，那么输出0
样例输入
2
1 0
1 0
样例输出
0
样例输入
5
3 1
0 4
1 3
4 0
1 3
样例输出
35
数据规模和约定
n<=8
#include <stdio.h>#define BLACK 0
#define WHITE 1int n;
int x[10], y[10];
int slip[10];int solve(int person_id)
{if (person_id > 0){slip[person_id] = BLACK;if (solve(person_id - 1))return 1;slip[person_id] = WHITE;return solve(person_id - 1);}else{int n_black = 0, n_white = 0;for (int i = 1; i <= n; ++i){if (slip[i] == BLACK)n_black++;elsen_white++;}for (int i = 1; i <= n; ++i){if (slip[i] == WHITE){if (!(x[i] == n_white - 1 && y[i] == n_black))return 0;}else{if (x[i] == n_white && y[i] == n_black - 1)return 0;}}return 1;}
}int main()
{scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d %d", &x[i], &y[i]);if (solve(n)){int n_black = 0, n_white = 0;for (int i = 1; i <= n; ++i){if (slip[i] == BLACK)n_black++;elsen_white++;}if (n_black == n)printf("0");else{for (int i = 1; i <= n; ++i){if (slip[i] == WHITE)printf("%d", i);}}}elseprintf("NoSolution.");return 0;
}