codeforces-scrape

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

188.md (8025B)


      1 Source: https://codeforces.com/blog/entry/4633
      2 
      3 Roco is a very simple language. On one hand, it's esoteric, so everything you need to know about it fits in two pages. On the other hand, it's powerful enough to enable writing rather complicated programs in it without racking one's brains over each elementary operation (like in Brainfuck). Being able to refer variables using names (numerical, but names nevertheless) is already a gift to the programmer :-)
      4 
      5 #### [188A - Hexagonal Numbers](/contest/188/problem/A "Surprise Language Round 6")
      6 
      7 As usual, the first problem tests the competitor's understanding of basic arithmetic operations. The solution is very similar to the example.
      8 
      9 ```
     10 iin [0]
     11 mul [1] [0] 2
     12 dec [1]
     13 mul [1] [1] [0]
     14 iout [1]
     15 ac
     16 ```
     17 
     18 Starting with the second one, the problems need learning the main feature of the language — the coroutines. A coroutine is a named piece of code executed in an endless loop. Something in between a procedure (without input parameters and variables, but with a name used for calling it) and a loop (without loop counter or break conditions, but with a chance to break it at any moment), coroutines allow to implement both these concepts.
     19 
     20 #### [188B - A + Reverse B](/contest/188/problem/B "Surprise Language Round 6")
     21 
     22 The key element of this problem is reversing a number (we knew how to add the second number to it ever since the example). There are two ways to do this: either read the number as a sequence of characters and accumulate its reverse simultaneously, or read the number as, well, a number and calculate its reverse using math. I used the second approach, so I needed a single loop-like coroutine which stopped when the number being reversed turned zero.
     23 
     24 ```
     25 /* coroutine to reverse a number [1] into [2] */
     26 co reverse {
     27    eq [3] [1] 0
     28    if [3]
     29       ac
     30  
     31    /* find current number modulo 10 */
     32    mod [3] [1] 10
     33    /* add it to reversed number */
     34    mul [2] [2] 10
     35    add [2] [2] [3] 
     36    /* and divide current number */
     37    div [1] [1] 10
     38 }
     39  
     40 iin [0]
     41 iin [1]
     42 ca reverse
     43 add [2] [2] [0]
     44 iout [2]
     45 ac
     46 ```
     47 
     48 #### [188C - LCM](/contest/188/problem/C "Surprise Language Round 6")
     49 
     50 In other languages the easiest way to get LCM of two numbers is recursive. The specifics of Roco is that one can't write a recursion with a single coroutine calling itself — after the second call of the coroutine its execution continues from the place where it stopped last time. So it was easier to rewrite the standard algorithm as a loop.
     51 
     52 ```
     53 /* [0] - a
     54    [1] - b
     55 */
     56 co gcd {
     57   eq [2] [0] 0
     58   if [2]
     59     ac
     60   set [2] [1]
     61   set [1] [0]
     62   mod [0] [2] [1]
     63 }
     64  
     65 iin [0]
     66 iin [1]
     67 set [3] [0]
     68 set [4] [1]
     69 ca gcd
     70 /* now  [1] is gcd */
     71 div [5] [3] [1]
     72 mul [5] [5] [4]
     73 iout [5]
     74 ac
     75 ```
     76 
     77 #### [188D - Asterisks](/contest/188/problem/D "Surprise Language Round 6")
     78 
     79 Ok, let's move on to a more complicated task: here we need a nested loop, the outer one running through the lines and the inner one — through the asterisks in the line. The inner loop will be called several times (from each iteration of the outer one), so here one could meet the mentioned feature of the coroutines for the first time.
     80 
     81 ```
     82 /* [0] - * quantity
     83    [1] - current line
     84    [2] - current * in line
     85 */
     86  
     87 co one_row {
     88    lt [3] [1] [2]
     89    if [3]
     90       ac
     91    cout 42
     92    inc [2]
     93 }
     94  
     95 co print_all {
     96    lt [3] [0] [1]
     97    if [3]
     98       ac
     99    set [2] 1
    100    ca one_row
    101    cout 10
    102    inc [1]
    103 }
    104  
    105 iin [0]
    106 set [1] 1
    107 ca print_all
    108 ac
    109 ```
    110 
    111 #### [188E - HQ9+](/contest/188/problem/E "Surprise Language Round 6")
    112 
    113 This time one can't solve this problem in one line using regular expressions, since this language has none. So one has to do it in an old-fashioned way, reading characters one-by-one and checking them for equality with each of the required ones. The code is rather long — there are three characters to compare each one to, and the answer has to be printed char-by-char, but overall there is nothing complex here.
    114 
    115 ```
    116 /* [0] - YES or NO
    117    [1] - current char
    118 */
    119  
    120 co one_char {
    121    cin [1]
    122  
    123    eq [2] [1] 10
    124    if [2]
    125       ac
    126  
    127    /* H */
    128    eq [2] [1] 72
    129    or [0] [0] [2]
    130    /* Q */
    131    eq [2] [1] 81
    132    or [0] [0] [2]
    133    /* 9 */
    134    eq [2] [1] 57
    135    or [0] [0] [2]
    136 }
    137  
    138 co say_yes {
    139    cout 89
    140    cout 69
    141    cout 83
    142    cout 10
    143    ac
    144 }
    145  
    146 co say_no {
    147    cout 78
    148    cout 79
    149    cout 10
    150    ac
    151 }
    152  
    153 set [0] 0
    154 ca one_char
    155 /* output the result stored in [0] */
    156 if [0]
    157    ca say_yes
    158 dec [0]
    159 if [0]
    160    ca say_no
    161 ac
    162 ```
    163 
    164 Three last problems are almost real programming :-) They use the fact that in Roco variables are referenced not by names but by their indices in the heap, and the index can in turn be the contents of a variable. One can do more interesting things with arrays, but the programs become longer and more error-prone.
    165 
    166 #### [188F - Binary Notation](/contest/188/problem/F "Surprise Language Round 6")
    167 
    168 The bad thing about the binary notation is that the digits are calculated right-to-left but have to be printed left-to-right. This can be done without arrays (reverse the number in binary using the math trick from [188B - A + Reverse B](/contest/188/problem/B "Surprise Language Round 6") and then print its digits in the same order as they are calculated), but I used an array solution which first calculates the digits and writes them into an array and then goes through the array from the end to the start and prints the digits.
    169 
    170 ```
    171 /* [0] - current number
    172    [1] - index of last digit calculated
    173    [2]..[9] - service cells
    174    [10]..[[1]] - the actual digits of the number
    175 */
    176  
    177 co calculate_digits {
    178    /* stop when the number is 0 */
    179    eq [3] [0] 0
    180    if [3]
    181       ac
    182  
    183    /* get next digit - put it to its location directly */
    184    mod [[1]] [0] 2
    185    /* update the number and its notation length */
    186    div [0] [0] 2
    187    inc [1]
    188 }
    189  
    190 co output_digits {
    191    /* stop when the next digit printed will be outside of the number */
    192    eq [3] [1] 9
    193    if [3]
    194       ac
    195  
    196    /* output the digit at [1] */
    197    iout [[1]]
    198    dec [1]
    199 }
    200  
    201  
    202 iin [0]
    203 set [1] 10
    204 ca calculate_digits
    205 dec [1]
    206 ca output_digits
    207 ac
    208 ```
    209 
    210 #### [188G - Array Sorting](/contest/188/problem/G "Surprise Language Round 6")
    211 
    212 Unlike Befunge, in Roco the memory size limit is technical, not conceptual, so one could coed counting sort as well as comparison-based sort. Here is a code for the former one.
    213 
    214 ```
    215 /* [1]..[100] - the counts of numbers
    216    [101] - quantity of numbers
    217    [102] - current number
    218    [103] - current index
    219 */
    220  
    221 iin [101]
    222  
    223 set [103] 1
    224 co init {
    225    eq [104] [103] 101
    226    if [104]
    227       ac
    228    set [[103]] 0
    229    inc [103]
    230 }
    231 ca init
    232  
    233 set [103] 0
    234 co read {
    235    eq [104] [103] [101]
    236    if [104]
    237       ac
    238    iin [102]
    239    inc [[102]]
    240    inc [103]
    241 }
    242 ca read
    243  
    244 set [102] 1
    245 co print_sorted {
    246    eq [104] [102] 101
    247    if [104]
    248       ac
    249    set [103] 1
    250    co print_one_number {
    251       gt [104] [103] [[102]]
    252       if [104]
    253          ac
    254       iout [102]
    255       cout 32
    256       inc [103]
    257    }
    258    /* due to coroutine property (!), call only for positive quantity of numbers*/
    259    gt [104] [[102]] 0
    260    if [104]
    261       ca print_one_number
    262    inc [102]
    263 }
    264 ca print_sorted
    265 ac
    266 ```
    267 
    268 #### [188H - Stack](/contest/188/problem/H "Surprise Language Round 6")
    269 
    270 This problem required to simulate a stack using an array — nothing too complicated, especially since the data never overflows and never attempts to do invalid calculations.
    271 
    272 ```
    273 /* [0] - current character
    274    [1] - current stack size
    275    [2]..[9] - service
    276    [10]... - stack
    277 */
    278  
    279 co plus {
    280    dec [1]
    281    add [3] [1] 9
    282    add [4] [3] 1
    283    add [[3]] [[3]] [[4]]
    284    ac
    285 }
    286  
    287 co multiply {
    288    dec [1]
    289    add [3] [1] 9
    290    add [4] [3] 1
    291    mul [[3]] [[3]] [[4]]
    292    ac
    293 }
    294  
    295 co number {
    296    sub [2] [0] 48
    297    inc [1]
    298    add [3] [1] 9
    299    set [[3]] [2]
    300    ac
    301 }
    302  
    303 co process {
    304    cin [0]
    305    /* end of line */
    306    eq [2] [0] 10
    307    if [2]
    308       ac
    309    /* digit - push on the stack */
    310    gt [2] [0] 47
    311    if [2]
    312       ca number
    313    eq [2] [0] 43
    314    if [2]
    315       ca plus
    316    eq [2] [0] 42
    317    if [2]
    318       ca multiply
    319 }
    320  
    321 set [2] 0
    322 ca process
    323 /* output the topmost element of the stack */
    324 add [2] [1] 9
    325 iout [[2]]
    326 ac
    327 ```