problem.txt (2767B)
1 B. WOW Factor 2 time limit per test1 second 3 memory limit per test256 megabytes 4 Recall that string a 5 is a subsequence of a string b 6 if a 7 can be obtained from b 8 by deletion of several (possibly zero or all) characters. For example, for the string a 9 ="wowwo", the following strings are subsequences: "wowwo", "wowo", "oo", "wow", "", and others, but the following are not subsequences: "owoo", "owwwo", "ooo". 10 11 The wow factor of a string is the number of its subsequences equal to the word "wow". Bob wants to write a string that has a large wow factor. However, the "w" key on his keyboard is broken, so he types two "v"s instead. 12 13 Little did he realise that he may have introduced more "w"s than he thought. Consider for instance the string "ww". Bob would type it as "vvvv", but this string actually contains three occurrences of "w": 14 15 "vvvv" 16 "vvvv" 17 "vvvv" 18 For example, the wow factor of the word "vvvovvv" equals to four because there are four wows: 19 20 "vvvovvv" 21 "vvvovvv" 22 "vvvovvv" 23 "vvvovvv" 24 Note that the subsequence "vvvovvv" does not count towards the wow factor, as the "v"s have to be consecutive. 25 26 For a given string s 27 , compute and output its wow factor. Note that it is not guaranteed that it is possible to get s 28 from another string replacing "w" with "vv". For example, s 29 can be equal to "vov". 30 31 Input 32 The input contains a single non-empty string s 33 , consisting only of characters "v" and "o". The length of s 34 is at most 106 35 . 36 37 Output 38 Output a single integer, the wow factor of s 39 . 40 41 Examples 42 InputCopy 43 vvvovvv 44 OutputCopy 45 4 46 InputCopy 47 vvovooovovvovoovoovvvvovovvvov 48 OutputCopy 49 100 50 Note 51 The first example is explained in the legend. 52 53 --- 54 55 - a is a subsequence of b iff a can be created by removing elements from b 56 - wow factor := number of subsequences == "wow" 57 - we use vv as a stand in for w 58 - vvvv gives us three ways to make w's (always # of v's - 1) 59 - each string is made of only v's and o's 60 61 --- 62 63 examples: 64 65 vvvovvv 66 67 vv_ovv_ 68 vv_ov_v 69 vv_ovv_ 70 vv_ov_v 71 72 in each example, we may take a v (or skip it), take another v (or skip it), and if we already have 2 v's then we may take the next o, ..., and after we've taken a o, we may take up to two more v's. 73 74 string size is at most 10**6 = 100_000 75 76 a naive approach would be evaluating, basically, 2**n selections if all elements are v's 77 78 the state is as follows: 79 80 - s(fvc,oc,svc) 81 - fvc == first v count (0->2) 82 - oc == o count (0->1) 83 - svc == second v count (0->2) 84 - s(ct) 85 - ct ranges from 0->5 86 - vv o vv 87 - when ct == 5, we have found one 88 - when ct == 4 or 3, we can take a 4 89 - ... 90 91 this gives us an upper bound of 5 * size which is at worst 500_000, a reasonable number of stated assuming limited computation per state 92 93 --- 94 95 vvovooovovvovoovoovvvvovovvvov