1003

問題原文

問題

最大 10 億桁の 0,1 のビット列がある(ことになっている).入力として,ある範囲における 1 の個数の偶奇(パリティ)が与えられる(ただし正しいとは限らない).具体的にはこんな感じ.

  1. ビット 1 からビット 2 まで 1 が偶数個.
  2. ビット 3 からビット 4 まで 1 が奇数個.
  3. ビット 5 からビット 6 まで 1 が偶数個.
  4. ビット 1 からビット 6 まで 1 が偶数個.
  5. ビット 7 からビット 10 まで 1 が奇数個.

ここで,上から何番目 Consistent な情報であるかを答える.たとえば上の例では 1. から 3. までは正しい可能性があるが,4. は明らかに嘘なので 3 と出力する.全部の情報が正しい可能性がある場合は与えられた情報の数(上の例では 5)を出力する.

解法

自然言語で記述するとややこしいのでエッセンスだけ.

たとえば上の例であれば

  • 範囲 [1,2] が偶数個
  • 範囲 [3,4] が奇数個
  • 範囲 [5,6] が偶数個

というようなデータ構造を作る.ここでたとえば

  • 範囲 [1,4] が偶数個
  • 範囲 [3,4] が奇数個

というデータが与えられたら

  • 範囲 [1,2] が奇数個
  • 範囲 [3,4] が奇数個

というデータに改変する必要がある.

泉のプログラム

file1003.cpp


添付ファイル: file1003.cpp 550件 [詳細]

Last-modified: 2009-11-06 (金) 13:25:51 (3426d)