A. Vicious Keyboard

Codeforces

IDCF801A

Time2000ms

Memory256MB

Difficulty—

brute force

English · Original

Chinese · Translation

Formal · Original

Tonio has a keyboard with only two letters, "_V_" and "_K_". One day, he has typed out a string _s_ with only these two letters. He really likes it when the string "_VK_" appears, so he wishes to change at most one letter in the string (or do no changes) to maximize the number of occurrences of that string. Compute the maximum number of times "_VK_" can appear as a substring (i. e. a letter "_K_" right after a letter "_V_") in the resulting string. ## Input The first line will contain a string _s_ consisting only of uppercase English letters "_V_" and "_K_" with length not less than 1 and not greater than 100. ## Output Output a single integer, the maximum number of times "_VK_" can appear as a substring of the given string after changing at most one character. [samples] ## Note For the first case, we do not change any letters. "_VK_" appears once, which is the maximum number of times it could appear. For the second case, we can change the second character from a "_V_" to a "_K_". This will give us the string "_VK_". This has one occurrence of the string "_VK_" as a substring. For the fourth case, we can change the fourth character from a "_K_" to a "_V_". This will give us the string "_VKKVKKKKKKVVVVVVVVVK_". This has three occurrences of the string "_VK_" as a substring. We can check no other moves can give us strictly more occurrences.

Tonio 有一个仅包含两个字母 "_V_" 和 "_K_" 的键盘。一天，他输入了一个仅由这两个字母组成的字符串 #cf_span[s]。他非常喜爱字符串 "_VK_" 的出现，因此他希望至多更改字符串中的一个字母（或不作任何更改），以最大化 "_VK_" 的出现次数。请计算在修改后字符串中，"_VK_" 作为子串（即字母 "_K_" 紧跟在字母 "_V_" 之后）最多能出现多少次。第一行包含一个字符串 #cf_span[s]，仅由大写英文字母 "_V_" 和 "_K_" 组成，长度不小于 #cf_span[1] 且不大于 #cf_span[100]。请输出一个整数，表示在至多更改一个字符后，给定字符串中 "_VK_" 作为子串最多能出现的次数。对于第一个样例，我们不更改任何字母。"_VK_" 出现一次，这是它可能出现的最大次数。对于第二个样例，我们可以将第二个字符从 "_V_" 改为 "_K_"。这样会得到字符串 "_VK_"。该字符串包含一次 "_VK_" 作为子串。对于第四个样例，我们可以将第四个字符从 "_K_" 改为 "_V_"。这样会得到字符串 "_VKKVKKKKKKVVVVVVVVVK_"。该字符串包含三次 "_VK_" 作为子串。我们可以验证，其他任何操作都无法得到更多出现次数。 ## Input 第一行包含一个字符串 #cf_span[s]，仅由大写英文字母 "_V_" 和 "_K_" 组成，长度不小于 #cf_span[1] 且不大于 #cf_span[100]。 ## Output 请输出一个整数，表示在至多更改一个字符后，给定字符串中 "_VK_" 作为子串最多能出现的次数。 [samples] ## Note 对于第一个样例，我们不更改任何字母。"_VK_" 出现一次，这是它可能出现的最大次数。对于第二个样例，我们可以将第二个字符从 "_V_" 改为 "_K_"。这样会得到字符串 "_VK_"。该字符串包含一次 "_VK_" 作为子串。对于第四个样例，我们可以将第四个字符从 "_K_" 改为 "_V_"。这样会得到字符串 "_VKKVKKKKKKVVVVVVVVVK_"。该字符串包含三次 "_VK_" 作为子串。我们可以验证，其他任何操作都无法得到更多出现次数。

**Definitions** Let $ s \in \{V, K\}^n $ be the input string of length $ n $, where $ 1 \leq n \leq 100 $. Let $ f(s) $ denote the number of occurrences of the substring "VK" in $ s $, i.e., $$ f(s) = \sum_{i=1}^{n-1} \mathbf{1}_{s[i] = V \land s[i+1] = K} $$ Let $ S' = \{ s' \mid s' \text{ differs from } s \text{ in at most one position} \} $ be the set of all strings obtainable by changing at most one character in $ s $. **Objective** Compute: $$ \max_{s' \in S'} f(s') $$

Samples

Input #1

VK

Output #1

Input #2

VV

Output #2

Input #3

Output #3

Input #4

VKKKKKKKKKVVVVVVVVVK

Output #4

Input #5

KVKV

Output #5

API Response (JSON)

{
  "problem": {
    "name": "A. Vicious Keyboard",
    "description": {
      "content": "Tonio has a keyboard with only two letters, \"_V_\" and \"_K_\". One day, he has typed out a string _s_ with only these two letters. He really likes it when the string \"_VK_\" appears, so he wishes to cha",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF801A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tonio has a keyboard with only two letters, \"_V_\" and \"_K_\".\n\nOne day, he has typed out a string _s_ with only these two letters. He really likes it when the string \"_VK_\" appears, so he wishes to cha...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Tonio 有一个仅包含两个字母 \"_V_\" 和 \"_K_\" 的键盘。\n\n一天，他输入了一个仅由这两个字母组成的字符串 #cf_span[s]。他非常喜爱字符串 \"_VK_\" 的出现，因此他希望至多更改字符串中的一个字母（或不作任何更改），以最大化 \"_VK_\" 的出现次数。请计算在修改后字符串中，\"_VK_\" 作为子串（即字母 \"_K_\" 紧跟在字母 \"_V_\" 之后）最多能出现多少次。\n\n第一...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{V, K\\}^n $ be the input string of length $ n $, where $ 1 \\leq n \\leq 100 $.  \n\nLet $ f(s) $ denote the number of occurrences of the substring \"VK\" in $ s $, i.e.,  \n$$...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments