801A.md (1731B)
1 Source: https://codeforces.com/problemset/problem/801/A 2 3 A. Vicious Keyboard 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Tonio has a keyboard with only two letters, "V" and "K". 22 23 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. 24 25 Input 26 27 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. 28 29 Output 30 31 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. 32 33 Examples 34 35 Input 36 37 ``` 38 VK 39 ``` 40 41 Output 42 43 ``` 44 1 45 ``` 46 47 Input 48 49 ``` 50 VV 51 ``` 52 53 Output 54 55 ``` 56 1 57 ``` 58 59 Input 60 61 ``` 62 V 63 ``` 64 65 Output 66 67 ``` 68 0 69 ``` 70 71 Input 72 73 ``` 74 VKKKKKKKKKVVVVVVVVVK 75 ``` 76 77 Output 78 79 ``` 80 3 81 ``` 82 83 Input 84 85 ``` 86 KVKV 87 ``` 88 89 Output 90 91 ``` 92 1 93 ``` 94 95 Note 96 97 For the first case, we do not change any letters. "VK" appears once, which is the maximum number of times it could appear. 98 99 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. 100 101 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.