codeforces-scrape

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

470.md (5644B)


      1 Source: https://codeforces.com/blog/entry/13777
      2 
      3 #### [470A - Crystal Ball Sequence](/contest/470/problem/A "Surprise Language Round 7")
      4 
      5 As usual, the first problem tests competitors' ability to do basic math, and in this case it is even easier than the sample — without any loops.
      6 
      7 ```
      8 ^'0-
      9 $ 1+*3*1+.
     10 ```
     11 
     12 #### [470B - Hexakosioihexekontahexaphobia](/contest/470/problem/B "Surprise Language Round 7")
     13 
     14 This problem uses more advanced language concepts — loop, conditional execution and even named variables! Variables are convenient to use as loop counters and result accumulators, so as to avoid stack manipulations for the same purpose. An if-then-else in FALSE looks like this:
     15 
     16 ```
     17 (true/false condition on top of stack) $ 
     18     [(then statements)] ?
     19   ~ [(else statements)] ?
     20 ```
     21 
     22 Solution:
     23 
     24 ```
     25 0n:    {number of 6s found uninterrupted so far}
     26 0r:    {true, if 666 found}
     27 [^$ 1_=~]
     28 [ '6= $ [n; 1+ n:] ?
     29       ~ [0n:] ?
     30   n; 2 > r; | r: 
     31 ]
     32 #
     33 %
     34 r; $ ["YES"] ?
     35    ~ ["NO"] ?
     36 ```
     37 
     38 #### [470C - Eval](/contest/470/problem/C "Surprise Language Round 7")
     39 
     40 This problem can be solved in two ways. You could read numbers, store them to named variables and depending on the operator use one of the operations on them. Or else you could do the other way around, store necessary operation as a function into a named variable (FALSE allows to store functions as variables) and apply it to numbers stored in stack. Here is the code of the second approach:
     41 
     42 ```
     43 [0[^ $$ 47> \58\> &]['0- \ 10*+]#]
     44 r:
     45 
     46 r;!
     47 
     48 $'+=[[+]f:]?
     49 $'-=[[-]f:]?
     50 $'*=[[*]f:]?
     51 $'/=[[/]f:]?
     52 $'%=[[\$@$@\/*-]f:]?
     53 %
     54 
     55 r;!
     56 %
     57 f;!.
     58 ```
     59 
     60 #### [470D - Caesar Cipher](/contest/470/problem/D "Surprise Language Round 7")
     61 
     62 This problem combines elements of previous problems: reading long int, reading a string and doing modulo operation (could be replaced with conditional subtraction).
     63 
     64 ```
     65 0[^ $$ 47> \58\> &]['0- \ 10*+]#% k:   {read the key}
     66 
     67 [^$ 10=~]
     68 [ 'A- k;+ $ 25> [26-] ? 'A+ ,]
     69 #%
     70 ```
     71 
     72 #### [470E - Chessboard](/contest/470/problem/E "Surprise Language Round 7")
     73 
     74 All of a sudden this problem turned out to be easier than C and D; probably a double-for loop is more simple than reading till end of line, especially with all the confusion with ends of line :-)
     75 
     76 ```
     77 0[^ $$ 47> \58\> &]['0- \ 10*+]#%
     78 n:
     79 
     80 [\ $ @ $ @\/*-]
     81 p:
     82 
     83 0i:
     84 [n;i;>]
     85 [0j:
     86  [n;j;>]
     87  [j;i;+ 2p;!
     88   11* 46 \- ,
     89   j;1+j:]
     90  #
     91 "
     92 "
     93 i;1+i:]
     94 #
     95 ```
     96 
     97 #### [470F - Pairwise Sums](/contest/470/problem/F "Surprise Language Round 7")
     98 
     99 Next two problems use a new language construct — operator ø (a.k.a. O, not to be confused with 0), which allows random read access to stack elements. To calculate pairwise sums, one had to first read all array elements into the stak, then calculate indices of necessary elements, read them and add them up.
    100 
    101 ```
    102 [0[^ $$ 47> \58\> &]['0- \ 10*+]#%] r:
    103 
    104 r;! n:   {read the number of elements in array}
    105 
    106 0i:
    107 [n;i;>]
    108 [r;! i;1+i:]
    109 #        {read the elements of the array}
    110 
    111 0i:
    112 [n;i;>]
    113 [$ n;O + . " " n;1-O i;1+i:]
    114 #
    115 
    116 0i:
    117 [n;2*i;>]
    118 [% i;1+i:]
    119 #
    120 ```
    121 
    122 #### [470G - Hamming Distance](/contest/470/problem/G "Surprise Language Round 7")
    123 
    124 Same principle as in the previous problem — read characters of two strings into the stack (store the length of the strings into a named variable), then extract pairs of corresponding characters from it and accumulate the result in another named variable.
    125 
    126 ```
    127 0n:
    128 [^ $ 10=~]
    129 [n;1+n:]
    130 #%
    131 
    132 [^ $ 1_=~]
    133 []
    134 #%
    135 
    136 0i:
    137 0d:
    138 [n;i;>]
    139 [n;i;-1- O
    140  n;n;+i;- O
    141  =~ [d;1+d:] ?
    142  i;1+i:]
    143 #
    144 
    145 0i:
    146 [n;2*i;>]
    147 [% i;1+i:]
    148 #
    149 
    150 d;.
    151 ```
    152 
    153 #### [470H - Array Sorting](/contest/470/problem/H "Surprise Language Round 7")
    154 
    155 Same as the regular sorting task, this problem can be solved in many ways.
    156 
    157 You could write a "simple counting sort", as recommended by [Egor](/profile/Egor "Grandmaster Egor"): do an outer loop from 1 to 100, in the inner loop iterate over all array elements and print each element that equals the counter of the outer loop. Here is the [code](https://codeforces.com/contest/470/submission/7786917).
    158 
    159 Or you could store array elements in named variables (since there are very few of them) and generate a code which would compare pairs of variables and swap them if needed. Thus, instead of a[0] you use variable a, instead of a[1] — b etc. The first such solution I've seen was [nab](/profile/nab "Candidate Master nab")'s: [the code](https://codeforces.com/contest/470/submission/7786384).
    160 
    161 I chose yet another approach: read array elements into a stack and use selection sort, but each time you need a swap, copy the whole array (with elements swapped already) onto the top of the stack. After at most n swaps the top of the stack will hold a sorted array. Unfortunately, stack size is limited, and with n around 20 it overflows. So I reduced array size a lot, which also allowed other approaches :-)
    162 
    163 ```
    164 [0[^ $$ 47> \58\> &]['0- \ 10*+]#%] r:
    165 
    166 r;! n:   {read the number of elements in array}
    167 
    168 0i:
    169 [n;i;>]
    170 [r;! i;1+i:]
    171 #        {read the elements of the array}
    172 
    173 1s:      {# of array copies stored in memory}
    174 
    175 0i:
    176 [n;1-i;>]
    177 [ i;m:          {index of min element between i and n-1, inclusive}
    178   i;1+j:
    179   [n;j;>]
    180   [ n;m;-1- O   {extract a[m]}
    181     n;j;- O     {extract a[j], knowing that a[m] is on top}
    182     >
    183     [j;m:] ?    {if a[j] > a[m], m := j}
    184     j;1+j:
    185   ]#
    186 
    187   i;m;=~
    188   [ 0k:
    189     [n;k;>]
    190     [ k;e:     {index of element we're extracting now}
    191       k;i;=
    192          [m;e:] ?
    193       k;m;=
    194          [i;e:] ?
    195       n;k;+e;-1- O
    196       k;1+k:
    197     ]#
    198     s;1+s:      {+1 copy of array in memory}
    199   ] ?           {if i != m, copy all elements, while swapping a[i] and a[m]}
    200    
    201   i;1+i:]
    202 #
    203 
    204 0i:
    205 [n;i;>]
    206 [n;i;-1- O . " "
    207  i;1+i:]
    208 #
    209 
    210 0i:
    211 [n;s;*i;>]
    212 [% i;1+i:]
    213 #
    214 ```