1029falsecoin.cpp

算法编程题,北京大学OnlineJudge 1029Falsecoin

#include<stdio.h>  
#include<math.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
#include<set>
#include<map>
using namespace std;


//一堆硬币,有一个假币(或重或轻),问是哪个.
//枚举硬币,如果没有满足或有多个满足,则0

int n,m;
int a[1001];
bool lt[100][1001];
bool rt[100][1001];
char s[100][2];

bool Input(){
	if(scanf("%d%d",&n,&m)==EOF){
		return 0;
	}
	int i,j,k,t,tn;
	for(i=0;i<m;i++){
		for(j=1;j<=n;j++){
			lt[i][j]=0,rt[i][j]=0;
		}
		scanf("%d",&tn);
		for(j=0;j<tn;j++){
			scanf("%d",&t);
			lt[i][t]=1;
		}
		for(j=0;j<tn;j++){
			scanf("%d",&t);
			rt[i][t]=1;
		}
		scanf("%s",&s[i]);
	}
	return 1;
}

void Solve(){
	int i,j,k;
	int flag=0,ans;
	for(i=n;i>=1;i--){
		int inc[2]={-1,1};
		for(k=0;k<2;k++){
			for(j=0;j<m;j++){
				int s1=0,s2=0;
				if(lt[j][i]) s1+=inc[k];
				if(rt[j][i]) s2+=inc[k];
				if(!(s[j][0]=='='&&s1==s2||s[j][0]=='<'&&s1<s2||s[j][0]=='>'&&s1>s2)){
					break;
				}
			}
			if(j>=m){
				break;
			}
		}
		if(k<2){
			flag++;
			ans=i;
		}
	}
	if(flag!=1){
		ans=0;
	}
	printf("%d\n",ans);
	return;
}

int main()
{
	//freopen("in.txt","r",stdin);
	while(Input()){
		Solve();
	}
	return 0;
}