codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 :-)