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; }