/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
atcoder の並べ替えである文字列 S が与えられます。
この文字列 S に対して以下の操作を 0 回以上行います。
- S 中の隣接する 2 文字を選び、入れ替える。
S を atcoder にするために必要な最小の操作回数を求めてください。
制約
- S は
atcoderの並べ替えである文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
catredo
出力例 1
8
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
という流れで操作を行うと、 8 回で S を atcoder にすることができ、これが達成可能な最小の操作回数です。
入力例 2
atcoder
出力例 2
0
この場合、文字列 S は元から atcoder です。
入力例 3
redocta
出力例 3
21
Score : 400 points
Problem Statement
You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:
- Choose two adjacent characters of S and swap them.
Find the minimum number of operations required to make S equal atcoder.
Constraints
- S is a string that is a permutation of
atcoder
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer as an integer.
Sample Input 1
catredo
Sample Output 1
8
You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.
Sample Input 2
atcoder
Sample Output 2
0
In this case, the string S is already atcoder.
Sample Input 3
redocta
Sample Output 3
21