Beta Round #56-A: Where Are My Flakes?

問題概要

N(<1000)個の箱がある。どれか一つにエサが入っている。ヒントとなる情報がM(<1000)個与えられる。ヒントとは、エサがi番目の箱より右(or 左)に入っているという情報である。エサの入っている可能性のある箱の個数を求める問題。

解法

hintが与えられる度に入ってないことが確定したマスを更新する。計算量O(N*M)。区間で処理したらもっと速くなるかもしれないけど、これで十分。

bool isIn[1001];
char str[10];

int main(){
    int i, j, N, M, e;
    scanf("%d%d ",&N,&M);
    REP(i,N)isIn[i] = true;
    REP(i,M){
        scanf("To the %s of %d\n", str, &e);
        e--;
        if(!strcmp(str,"left")){
            for(j=e;j<N;j++) isIn[j] = false;
        }
        else{
            for(j=0;j<=e;j++) isIn[j] = false;
        }
    }
    int ans = count(isIn,isIn+N,true);
    printf("%d\n", ans?ans:-1);
    return 0;
}