Codeforces #180 Div2 C "Parity Game"
問題
http://codeforces.com/contest/298/problem/C
訳
あなたはホッキョクグマのアリス、ボブと一緒に魚釣りをしている。
アタリがくるのを待つことにクマたちは退屈していた。
彼らはゲームをすることにした。
アリスとボブはそれぞれが01-文字列(0か1の文字しか含まれていない文字列)a, bを書いた。
それからあなたは以下の2つの操作を使ってaをbへ変換することに挑戦する。
- aの末尾にparity(a)を書き足す。例)1010 -> 10100
- aの最初の文字を削除する。 例)1001 -> 001
あなたは好きなだけ上記の操作を行う事ができる。
aからbへと変換することが可能であるかを出力せよ。
parity(a)はaに1が奇数個含まれていた場合 1 にそうでなければ 0 を返すものである。
考えた事
え・・・分からん・・・
どういう法則があるんだ?
(めっちゃ書き出してみる)
1は増やす事ができたとしても、3 -> 4、7 -> 8など
奇数を偶数にすることのみだな。
で、2つの操作を上手く使えば1と0を好きなように
並べることができるみたいだ。
だから、aの1の数がbを作る分だけあればおk
ソースコード
int main() { string a, b; cin >> a >> b; int aOne = 0; for( int i = 0; i < a.length(); i++ ){ if( a[i] == '1' ) aOne++; } int bOne = 0; for( int i = 0; i < b.length(); i++ ){ if( b[i] == '1' ) bOne++; } if( aOne % 2 == 1 ) aOne++; bool ok = (aOne >= bOne); cout << (ok ? "YES" : "NO") << endl; }