No.111 Ababababa
タグ : / 解いたユーザー数 549
作問者 :
koyumeishi
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もしくは右上の雲マークをクリックしてアカウントを作成してください。