{"raw_statement":[{"iden":"statement","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 words. To make it still possible to read, he will try to modify each word as little as possible.\n\nLimak 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.\n\nLimak 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_.\n\nWhat is the minimum possible number of moves Limak can do?"},{"iden":"input","content":"The first line of the input contains an integer _n_ (1 ≤ _n_ ≤ 75) — the length of the string.\n\nThe second line contains a string _s_, consisting of uppercase English letters. The length of the string is equal to _n_."},{"iden":"output","content":"Print one integer, denoting the minimum possible number of moves Limak can do, in order to obtain a string without a substring \"_VK_\"."},{"iden":"examples","content":"Input\n\n4\nVKVK\n\nOutput\n\n3\n\nInput\n\n5\nBVVKV\n\nOutput\n\n2\n\nInput\n\n7\nVVKEVKK\n\nOutput\n\n3\n\nInput\n\n20\nVKVKVVVKVOVKVQKKKVVK\n\nOutput\n\n8\n\nInput\n\n5\nLIMAK\n\nOutput\n\n0"},{"iden":"note","content":"In the first sample, the initial string is \"_VKVK_\". The minimum possible number of moves is 3. One optimal sequence of moves is:\n\n1.  Swap two last letters. The string becomes \"_VKKV_\".\n2.  Swap first two letters. The string becomes \"_KVKV_\".\n3.  Swap the second and the third letter. The string becomes \"_KKVV_\". Indeed, this string doesn't have a substring \"_VK_\".\n\nIn the second sample, there are two optimal sequences of moves. One is \"_BVVKV_\"  →  \"_VBVKV_\"  →  \"_VVBKV_\". The other is \"_BVVKV_\"  →  \"_BVKVV_\"  →  \"_BKVVV_\".\n\nIn the fifth sample, no swaps are necessary."}],"translated_statement":[{"iden":"statement","content":"Bear Limak 为编程竞赛准备题目。当然，在题目描述中提及赞助商名称是不专业的。Limak 认真对待此事，打算修改某些单词。为了使修改后的文本仍可阅读，他将尽可能少地修改每个单词。\n\nLimak 有一个由大写英文字母组成的字符串 #cf_span[s]。在一次操作中，他可以交换字符串中两个 *相邻* 的字母。例如，他可以将字符串 \"_ABBC_\" 变为 \"_BABC_\" 或 \"_ABCB_\"。\n\nLimak 希望得到一个不含子串 \"_VK_\" 的字符串（即不存在字母 '_V_' 紧接着字母 '_K_' 的情况）。可以证明，对于任意初始字符串 #cf_span[s]，这都是可行的。\n\n请问 Limak 至少需要多少次操作？\n\n输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 75]）——字符串的长度。\n\n第二行包含一个字符串 #cf_span[s]，由大写英文字母组成，长度等于 #cf_span[n]。\n\n请输出一个整数，表示 Limak 为获得不含子串 \"_VK_\" 的字符串所需的最少操作次数。\n\n在第一个样例中，初始字符串为 \"_VKVK_\"，最少操作次数为 #cf_span[3]。一种最优操作序列如下：\n\n在第二个样例中，存在两种最优操作序列。一种是 \"_BVVKV_\"#cf_span[  →  ]\"_VBVKV_\"#cf_span[  →  ]\"_VVBKV_\"。另一种是 \"_BVVKV_\"#cf_span[  →  ]\"_BVKVV_\"#cf_span[  →  ]\"_BKVVV_\"。\n\n在第五个样例中，无需任何交换。"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 75]）——字符串的长度。第二行包含一个字符串 #cf_span[s]，由大写英文字母组成，长度等于 #cf_span[n]。"},{"iden":"output","content":"请输出一个整数，表示 Limak 为获得不含子串 \"_VK_\" 的字符串所需的最少操作次数。"},{"iden":"examples","content":"输入\n4\nVKVK\n输出\n3\n\n输入\n5\nBVVKV\n输出\n2\n\n输入\n7\nVVKEVKK\n输出\n3\n\n输入\n20\nVKVKVVVKVOVKVQKKKVVK\n输出\n8\n\n输入\n5\nLIMAK\n输出\n0"},{"iden":"note","content":"在第一个样例中，初始字符串为 \"_VKVK_\"，最少操作次数为 #cf_span[3]。一种最优操作序列如下：交换最后两个字母，字符串变为 \"_VKKV_\"；交换前两个字母，字符串变为 \"_KVKV_\"；交换第二和第三个字母，字符串变为 \"_KKVV_\"。该字符串确实不含子串 \"_VK_\"。\n\n在第二个样例中，存在两种最优操作序列。一种是 \"_BVVKV_\"#cf_span[  →  ]\"_VBVKV_\"#cf_span[  →  ]\"_VVBKV_\"。另一种是 \"_BVVKV_\"#cf_span[  →  ]\"_BVKVV_\"#cf_span[  →  ]\"_BKVVV_\"。\n\n在第五个样例中，无需任何交换。"}],"sample_group":[],"show_order":[],"formal_statement":"**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**  \n$ 1 \\leq n \\leq 75 $\n\n**Objective**  \nFind 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'} $.","simple_statement":null,"has_page_source":false}