162.md (7681B)
1 Source: https://codeforces.com/blog/entry/4139 2 3 So here goes the editorial. Note that Factor allows pretty random codes, feel free to put all words in one line, but all words must be separated by at least one space, don't try to skip a space between a bracket and a word or something like that. 4 5 #### [162A - Pentagonal numbers](/contest/162/problem/A "VK Cup 2012 Wild-card Round 1") 6 7 This problem was almost the same as [130A - Hexagonal numbers](/contest/130/problem/A "Unknown Language Round 4") from Befunge round. Data input and output is done exactly as in the sample code, and besides them the program needs only basic stack operations. 8 9 ``` 10 USING: io kernel math math.parser ; 11 12 readln string>number 13 dup 3 * 1 - * 2 / 14 number>string print 15 ``` 16 17 Factor has a very system of built-in libraries which liberate the programmer from solving a lot of basic routine tasks. So after the first (trivial) probllem I gave several one-liners which needed only to find a proper library for the task. 18 19 #### [162B - Binary notation](/contest/162/problem/B "VK Cup 2012 Wild-card Round 1") 20 21 This problem can be solved in several ways; the shortest one is to use >bin word from math.parser dictionary which does exactly what we need. 22 23 ``` 24 USING: io kernel math math.parser ; 25 26 readln string>number 2 >base print 27 ``` 28 29 #### [162C - Prime factorization](/contest/162/problem/C "VK Cup 2012 Wild-card Round 1") 30 31 Looks like here I misestimated the complexity of the problem; D and E turned out to be easier. Actually, another library function, factors from math.primes.factors, performs all primes decomposition and even returns them as a sequence in a correct order. The second line converts a sequence of numbers into a sequence of strings (map combinator applies operations in square brackets to every element of the sequence). Finally, join concatenates elements of a sequence and inserts * between them. 32 33 ``` 34 USING: io kernel math math.parser math.primes.factors sequences ; 35 36 readln string>number factors 37 [ number>string ] map 38 "*" join print ; 39 ``` 40 41 #### [162D - Remove digits](/contest/162/problem/D "VK Cup 2012 Wild-card Round 1") 42 43 This is yet another problem with multiple approaches possible — for example, one could find non-digits using a regular expression and concatenate them. My solution used replace word: 44 45 ``` 46 USING: math math.parser peg peg.parsers peg.search io kernel ; 47 48 readln 'integer' [ drop "" ] action replace print 49 ``` 50 51 #### [162E - HQ9+](/contest/162/problem/E "VK Cup 2012 Wild-card Round 1") 52 53 Now this is a match for regular expression. Word matches? checks whether the given string matches the given regular expression and pushes a boolean result on the stack. Word if checks this result and prints YES or NO depending on its value. 54 55 ``` 56 USING: io kernel regexp ; 57 58 readln R/ \S*[HQ9]\S*/ matches? 59 [ "YES" ] 60 [ "NO" ] 61 if 62 print 63 ``` 64 65 The problems from the second part of the match required not only googling but also learning some deeper aspects of the language. 66 67 #### [162F - Factorial zeros](/contest/162/problem/F "VK Cup 2012 Wild-card Round 1") 68 69 The quantity of tailing zeros of factorial is defined by the number of 5s this factorial is divisible by (matching 2s are more numerous, there will be enough of them). This number, in turn, can be calculated as *n* / 5 + *n* / 25 + *n* / 125 + ... + *n* / 390625. Note that here we need to use integer division (/i) or round each division result down using truncate, otherwise the leftovers might add up and produce a couple of extra zeros. 70 71 The reference solution contained elements of precalculation (to avoid the loop to calculate the powers of 5) and a named variable n (to avoid remembering the order of things on the top of the stack). 72 73 ``` 74 USING: io formatting kernel locals math math.parser math.functions sequences ; 75 IN: trailing-zeros 76 77 :: trailing-zeros ( -- ) 78 readln string>number :> n 79 { 5 25 125 625 3125 15625 78125 390625 } 80 0 81 [ n swap / truncate + ] reduce 82 "%d" printf ; 83 84 trailing-zeros 85 ``` 86 87 #### [162G - Non-decimal sum](/contest/162/problem/G "VK Cup 2012 Wild-card Round 1") 88 89 This problem turned to be the hardest in the contest, and this surprised me a lot. It could be solved in a way similar to "42" example program, with minor modifications: after reading the quantity of numbers we had to read radix and store it to a named variable (for convenience only), and in the loop body strings had to be converted to numbers using base> word instead of string>number. Finally, the result had to be printed using >base instead of number>string. 90 91 ``` 92 USING: io kernel locals math math.parser sequences unicode.case ; 93 IN: basesum 94 95 :: basesum ( -- ) 96 readln string>number iota 97 readln string>number :> base 98 0 99 [ drop readln base base> + ] reduce 100 base >base >upper print ; 101 102 basesum 103 ``` 104 105 **Update** The docs for the language say that words >base and base> work for radixes only up to 16; actually they work with larger radixes as well, but this lessens my surprise at the complexity of this problem. 106 107 #### [162H - Alternating case](/contest/162/problem/H "VK Cup 2012 Wild-card Round 1") 108 109 In this problem I finally needed a real while loop! The first square brackets contain the continuation condition, the second ones — the loop body. I used it to slice the string in two-character pieces (and a leftover), convert each of them into title case (first letter is uppercase, the rest are lowercase) and print it without newline after it. The same process was applied to the leftover piece 1 or 2 characters long. 110 111 ``` 112 USING: io formatting kernel math sequences unicode.case ; 113 114 readln 115 [ dup length 2 > ] 116 [ 2 cut swap >title "%s" printf ] 117 while 118 >title print 119 ``` 120 121 [Skiminok](/profile/Skiminok "Expert Skiminok") suggested a shorter and cleaner code: 122 123 ``` 124 USING: io kernel math sequences ascii ; 125 readln [ odd? [ ch>lower ] [ ch>upper ] if ] map-index print 126 ``` 127 128 #### [162I - Truncatable primes](/contest/162/problem/I "VK Cup 2012 Wild-card Round 1") 129 130 The second hardest problem, based on OEIS sequence [A024785](http://oeis.org/A024785/). One can use a library word prime? for primality testing, so the main part of the solution is another while-loop which checks whether the string contains a prime and removes its leftmost character. Note that the value of answer is not final at its first assignment, it will be modified later so you have to add ! to its name whenever assigning to it. 131 132 ``` 133 USING: io formatting locals kernel math math.parser math.primes sequences unicode.case ; 134 IN: truncatable-primes 135 136 :: trancatable ( str -- ) 137 "YES" :> answer! 138 str 139 [ dup length 0 > ] 140 [ dup string>number prime? [ "NO" answer! ] unless 141 1 cut swap drop 142 ] 143 while 144 drop 145 answer print ; 146 147 readln 148 trancatable 149 ``` 150 151 #### [162J - Brackets](/contest/162/problem/J "VK Cup 2012 Wild-card Round 1") 152 153 Judging by the number of solutions submitted, I misestimated this problem as the hardest one. My solution was based on counting the brackets which stay open. 154 155 ``` 156 USING: io formatting locals kernel math sequences unicode.case ; 157 IN: balanced-brackets 158 159 :: balanced ( str -- ) 160 0 :> counter! 161 1 :> ok! 162 str 163 [ dup length 0 > ] 164 [ 1 cut swap 165 "(" = [ counter 1 + counter! ] [ counter 1 - counter! ] if 166 counter 0 < [ 0 ok! ] when 167 ] 168 while 169 drop 170 ok 0 = 171 [ "NO" ] 172 [ counter 0 > [ "NO" ] [ "YES" ] if ] 173 if 174 print ; 175 176 readln 177 balanced 178 ``` 179 180 Check out [another editorial](https://codeforces.com/blog/entry/4140) by [wjomlex](/profile/wjomlex "Candidate Master wjomlex") which relies heavily on recursion. Evidently, recursion is a natural response of a high-rated contestant to a functional language — well, I used none :-)