POJ 1029 False coin
問題
http://poj.org/problem?id=1029
解法
N枚のコインをそれぞれ偽のコインと仮定したとき矛盾が生じるかどうかで判定する
実装ですこしつまずいた
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 1000; int N, K; vector<vector<int> > L(100), R(100); // L < R vector<char> sign; bool findX(vector<int> v, int x){ for(int i = 0; i < v.size(); i++) if(v[i] == x) return true; return false; } bool c(int x){ for(int i = 0; i < K; i++){ if(sign[i] == '=' && (findX(L[i], x) || findX(R[i], x))) return false; } bool f = true, g = true; for(int i = 0; i < K; i++){ if(sign[i] == '<' && (!findX(L[i], x) || findX(R[i], x))){ f = false; break; } } for(int i = 0; i < K; i++){ if(sign[i] == '<' && (findX(L[i], x) || !findX(R[i], x))){ g = false; break; } } return (f || g); } int main(){ scanf("%d %d", &N, &K); for(int i = 0; i < K; i++){ int p, t; scanf("%d", &p); for(int j = 0; j < p; j++){ scanf("%d", &t); L[i].push_back(t-1); } for(int j = 0; j < p; j++){ scanf("%d", &t); R[i].push_back(t-1); } char c; scanf("%c", &c); scanf("%c", &c); if(c == '>'){ //left > right for(int j = 0; j < p; j++){ int t = L[i][j]; L[i][j] = R[i][j]; R[i][j] = t; } c = '<'; } sign.push_back(c); } int t = 0, ans = 0; for(int i = 0; i < N; i++){ if(c(i)){ ans = i + 1; t++; } } printf("%d\n", (t==1) ? ans : 0); return 0; }