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 ```