Codeforces #56 A "Where Are My Flakes?"
問題:http://codeforces.com/contest/60/problem/A
参加形式:本番
箱の数とフレークが隠された場所を示すヒントが与えられる.左から順に箱に番号がついていて,それぞれの箱を箱iとするとき,ヒントが「箱iよりも右にある」「箱iよりも左にある」という形式で与えられる.ヒントに合致する箱の数を求める.
すべてのヒントに合致する判定を一次元の真偽値列を用いて積をとって求めた.
コード
import java.util.*; public class A_WhereAreMyFlakes { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(), m = s.nextInt(); s.nextLine(); BitSet b = new BitSet(); b.set(0, n); for(;m-->0;){ String line = s.nextLine(); int i = new Integer(line.split(" ")[4]); BitSet a = new BitSet(); if(line.contains("left")){ a.set(0,i-1); b.and(a); }else if(i<n){ a.set(i,n); b.and(a); }else{ System.out.println(-1); return; } } System.out.println(b.cardinality()<1?-1:b.cardinality()); } }