D. Bear and Company

Codeforces

IDCF771D

Time1000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

Bear Limak prepares problems for a programming competition. Of course, it would be unprofessional to mention the sponsor name in the statement. Limak takes it seriously and he is going to change some words. To make it still possible to read, he will try to modify each word as little as possible. Limak has a string _s_ that consists of uppercase English letters. In one move he can swap two **adjacent** letters of the string. For example, he can transform a string "_ABBC_" into "_BABC_" or "_ABCB_" in one move. Limak wants to obtain a string without a substring "_VK_" (i.e. there should be no letter '_V_' immediately followed by letter '_K_'). It can be easily proved that it's possible for any initial string _s_. What is the minimum possible number of moves Limak can do? ## Input The first line of the input contains an integer _n_ (1 ≤ _n_ ≤ 75) — the length of the string. The second line contains a string _s_, consisting of uppercase English letters. The length of the string is equal to _n_. ## Output Print one integer, denoting the minimum possible number of moves Limak can do, in order to obtain a string without a substring "_VK_". [samples] ## Note In the first sample, the initial string is "_VKVK_". The minimum possible number of moves is 3. One optimal sequence of moves is: 1. Swap two last letters. The string becomes "_VKKV_". 2. Swap first two letters. The string becomes "_KVKV_". 3. Swap the second and the third letter. The string becomes "_KKVV_". Indeed, this string doesn't have a substring "_VK_". In the second sample, there are two optimal sequences of moves. One is "_BVVKV_" → "_VBVKV_" → "_VVBKV_". The other is "_BVVKV_" → "_BVKVV_" → "_BKVVV_". In the fifth sample, no swaps are necessary.

Bear Limak 为一场编程竞赛准备题目。当然，在题目描述中提及赞助商名称是不专业的。Limak 认真对待此事，打算修改一些单词。为了保持可读性，他将尽量最小化每个单词的修改。 Limak 有一个由大写英文字母组成的字符串 #cf_span[s]。在一次操作中，他可以交换字符串中两个 *相邻* 的字母。例如，他可以将字符串 "_ABBC_" 在一次操作中变为 "_BABC_" 或 "_ABCB_"。 Limak 希望得到一个不包含子串 "_VK_" 的字符串（即不存在字母 '_V_' 紧接着字母 '_K_' 的情况）。可以证明，对于任意初始字符串 #cf_span[s]，这都是可行的。 Limak 至少需要多少次操作？输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 75]) —— 字符串的长度。第二行包含一个字符串 #cf_span[s]，由大写英文字母组成，字符串长度等于 #cf_span[n]。请输出一个整数，表示 Limak 为了得到一个不含子串 "_VK_" 的字符串所需的最少操作次数。在第一个样例中，初始字符串为 "_VKVK_"。最少操作次数为 #cf_span[3]。一种最优的操作序列是：在第二个样例中，存在两种最优操作序列。一种是 "_BVVKV_"#cf_span[ → ]"_VBVKV_"#cf_span[ → ]"_VVBKV_"。另一种是 "_BVVKV_"#cf_span[ → ]"_BVKVV_"#cf_span[ → ]"_BKVVV_"。在第五个样例中，无需任何交换。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 75]) —— 字符串的长度。第二行包含一个字符串 #cf_span[s]，由大写英文字母组成，字符串长度等于 #cf_span[n]。 ## Output 请输出一个整数，表示 Limak 为了得到一个不含子串 "_VK_" 的字符串所需的最少操作次数。 [samples] ## Note 在第一个样例中，初始字符串为 "_VKVK_"。最少操作次数为 #cf_span[3]。一种最优的操作序列是：交换最后两个字母，字符串变为 "_VKKV_"。交换前两个字母，字符串变为 "_KVKV_"。交换第二和第三个字母，字符串变为 "_KKVV_"。确实，该字符串不含子串 "_VK_"。在第二个样例中，存在两种最优操作序列。一种是 "_BVVKV_"#cf_span[ → ]"_VBVKV_"#cf_span[ → ]"_VVBKV_"。另一种是 "_BVVKV_"#cf_span[ → ]"_BVKVV_"#cf_span[ → ]"_BKVVV_"。在第五个样例中，无需任何交换。

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the string. Let $ s = s_1 s_2 \dots s_n $ be a string over the alphabet $ \{A, B, \dots, Z\} $. **Constraints** 1. $ 1 \leq n \leq 75 $ 2. Each $ s_i \in \{A, B, \dots, Z\} $ **Objective** Find the minimum number of adjacent swaps required to transform $ s $ into a string $ s' $ such that $ s' $ contains no substring "VK", i.e., for all $ i \in \{1, \dots, n-1\} $, it is not the case that $ s'_i = \text{'V'} $ and $ s'_{i+1} = \text{'K'} $.

Samples

Input #1

4
VKVK

Output #1

Input #2

5
BVVKV

Output #2

Input #3

7
VVKEVKK

Output #3

Input #4

20
VKVKVVVKVOVKVQKKKVVK

Output #4

Input #5

5
LIMAK

Output #5

API Response (JSON)

{
  "problem": {
    "name": "D. Bear and Company",
    "description": {
      "content": "Bear Limak prepares problems for a programming competition. Of course, it would be unprofessional to mention the sponsor name in the statement. Limak takes it seriously and he is going to change some ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF771D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bear Limak prepares problems for a programming competition. Of course, it would be unprofessional to mention the sponsor name in the statement. Limak takes it seriously and he is going to change some ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Bear Limak 为一场编程竞赛准备题目。当然，在题目描述中提及赞助商名称是不专业的。Limak 认真对待此事，打算修改一些单词。为了保持可读性，他将尽量最小化每个单词的修改。\n\nLimak 有一个由大写英文字母组成的字符串 #cf_span[s]。在一次操作中，他可以交换字符串中两个 *相邻* 的字母。例如，他可以将字符串 \"_ABBC_\" 在一次操作中变为 \"_BABC_\" 或 \"_ABC...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the string.  \nLet $ s = s_1 s_2 \\dots s_n $ be a string over the alphabet $ \\{A, B, \\dots, Z\\} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 75...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments