問題一覧 > 通常問題

No.111 Ababababa

レベル : / AI推定難易度 : 450 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 549
作問者 : koyumeishi
お気に入りにしたユーザー ProblemId : 246 / 自分の提出
問題文最終更新日: 2026-06-25 07:09:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 70 (順位表) の他の問題:

Problem Statement

"Ababababababa, baa!"
With the woman behind him, Yasukichi found himself starting to grin in spite of himself.

From Ryunosuke Akutagawa, Ababababa http://www.aozora.gr.jp/cards/000879/card14.html


Why did Yasukichi "start to grin"?
Yes, as you may have guessed, it is because the string "$ababababababa$", obtained by writing "Ababababababa" in Roman letters, was a palindrome.

The string $S$ is a string of length $L$ consisting of "$a$" followed by multiple repetitions of "$ba$". Given the length $L$, $S$ is uniquely determined. For example, when $L=3$, $S$ is "$aba$", and when $L=5$, it is "$ababa$". Given $L$, find how many palindromes of length at least 2 are contained in the corresponding $S$.

A palindrome is a string that reads the same forward and backward. More strictly, let the $i$-th character of $S$ be denoted by $S_i$. If $S_{i+k} = S_{j-k}$ holds for all $k$ such that $0 \leq k \leq j-i \ (i \leq j)$, then the string $S_i + S_{i+1} + \dots + S_j$ is a palindrome of length $j-i+1$.
For example, the string "$ababa$" reads as the string "$ababa$" both forward and backward, so it is a palindrome of length 5.
On the other hand, the string "$abab$" reads as the string "$baba$" backward, which does not match how it reads forward, so it is not a palindrome.

Input

$L$

The length $L$ of a string consisting of "$a$" followed by multiple repetitions of "$ba$" is given.

$L$ satisfies the following constraints:
$3 \leq L < 10^9$
$L$ is odd

Output

Output on one line the number of palindromes of length at least 2 contained in the string.

Sample

Sample 1
Input
5
Output
4

The length of the string is 5, so the corresponding string is "$ababa$". It contains 2 occurrences of the palindrome "$aba$", 1 occurrence of the palindrome "$bab$", and 1 occurrence of the palindrome "$ababa$".

Sample 2
Input
9
Output
16

The corresponding string is "$ababababa$".

Sample 3
Input
200001
Output
10000000000

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。