No.111 あばばばば

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 228
作問者 : koyumeishikoyumeishi

4 ProblemId : 246 / 出題時の順位表

問題文

「あばばばばばば、ばあ!」
保吉は女を後ろにしながら、我知らずにやにや笑ひ出した。

芥川龍之介 あばばばば http://www.aozora.gr.jp/cards/000879/card14.htmlより


何故保吉は「にやにや笑ひ出した」のでしょうか?
そう、お察しのように「あばばばばばば」をローマ字に置き換えた「$ababababababa$」という文字列が回文になっていたからです。

文字列$S$は"$a$"の後ろに"$ba$"が複数回続く長さ$L$の文字列です。 長さ$L$が与えられると$S$は一意に決まります。 例えば$L=3$のとき$S$は"$aba$"、$L=5$のときは"$ababa$"となります。 $L$が与えられるので、対応する$S$の中に長さ2以上の回文がいくつ含まれるかを答えてください。

回文とは、前から読んでも後ろから読んでも同じ文字列のことです。 より厳密には$S$の$i$番目の文字を$S_i$とすると、 $0 \leq k \leq j-i \ (i \leq j)$であるようなすべての$k$について、 $S_{i+k} = S_{j-k}$であるとき、文字列$S_i + S_{i+1} + \dots + S_j$は長さ$j-i+1$の回文となります。
例えば"$ababa$"という文字列は前から読んでも後ろから読んでも"$ababa$"という文字列になるため、長さ5の回文です。
一方"$abab$"という文字列は後ろから読むと"$baba$"という文字列になり、前から読んだ時と一致しないため回文ではありません。

入力

$L$

"$a$"の後に"$ba$"が複数回続くような文字列の長さ$L$が与えられます。

$L$は以下の制約を満たします
$3 \leq L < 10^9$
$L$は奇数

出力

文字列に長さ2以上の回文がいくつ含まれるかを一行で出力してください。

サンプル

サンプル1
入力
5
出力
4

文字列の長さは5のため、対応する文字列は"$ababa$"です。 この中には"$aba$"という回文が2つ、"$bab$"という回文が1つ、"$ababa$"という回文が1つ含まれています。

サンプル2
入力
9
出力
16

対応する文字列は"$ababababa$"です。

サンプル3
入力
200001
出力
10000000000

提出ページヘ