No.2162 Copy and Paste 2
タグ : / 解いたユーザー数 30
作問者 :
miscalc
/ テスター :
akakimidori
Problem Statement
The time limit for this problem is 7 seconds.
Miscalc has strings $T, U$. Initially, they are empty.
Miscalc has $4$ keys at hand: the A key, the B key, the C key, and the V key. Pressing each key changes $T$ and $U$ as follows.
- Pressing the A key $1$ time appends
ato the end of $T$. - Pressing the B key $1$ time appends
bto the end of $T$. - Pressing the C key $1$ time replaces $U$ with $T$.
- Pressing the V key $1$ time appends $U$ to the end of $T$.
You are given a string $S$ consisting of a and b. What is the minimum number of key presses required to make $T$ equal to $S$?
Input
$S$
- $S$ is a string consisting of
aandb - $1 \leq |S| \leq 2 \times 10^5$
Output
Output the minimum number of key presses required to make $T$ equal to $S$. Print a newline at the end.
Sample
Sample 1
Input
babbababa
Output
7
Pressing the keys in the following order minimizes the number of presses.
- Press the B key. Now $T = $
b, $U = $. - Press the A key. Now $T = $
ba, $U = $. - Press the C key. Now $T = $
ba, $U = $ba. - Press the B key. Now $T = $
bab, $U = $ba. - Press the V key. Now $T = $
babba, $U = $ba. - Press the V key. Now $T = $
babbaba, $U = $ba. - Press the V key. Now $T = $
babbababa, $U = $ba.
Sample 2
Input
aabbaabaabbaab
Output
8
Pressing the keys in the following order minimizes the number of presses.
- Press the A key. Now $T = $
a, $U = $. - Press the A key. Now $T = $
aa, $U = $. - Press the B key. Now $T = $
aab, $U = $. - Press the C key. Now $T = $
aab, $U = $aab. - Press the B key. Now $T = $
aabb, $U = $aab. - Press the V key. Now $T = $
aabbaab, $U = $aab. - Press the C key. Now $T = $
aabbaab, $U = $aabbaab. - Press the V key. Now $T = $
aabbaabaabbaab, $U = $aabbaab.
Sample 3
Input
aaaaaaaaaaaaaaaa
Output
8
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。