問題一覧 > 通常問題

No.2162 Copy and Paste 2

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : miscalc / テスター : akakimidori ygussany
お気に入りにしたユーザー ProblemId : 6838 / 自分の提出
問題文最終更新日: 2022-03-17 19:55:53
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
Advent Calendar Contest 2022 (順位表) の他の問題:

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 a to the end of $T$.
  • Pressing the B key $1$ time appends b to 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 a and b
  • $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もしくは右上の雲マークをクリックしてアカウントを作成してください。