130.md (7606B)
1 Source: https://codeforces.com/blog/entry/3226 2 3 So here goes an editorial for the round. For me Befunge is one of the languages in which it's much easier to write code than to read it (and debugging code written by someone else is a complete torture; that's why we don't have hacking in ULRs). That's why I'll post just the general idea of the solution and my own codes — the latter just to show that I can code in Befunge too. 4 5 ### A. Hexagonal numbers 6 7 ``` 8 &:2*1-*.@ 9 ``` 10 11 A "consolation" problem, which requires only to understand the principles of working with stack. Read *n*, duplicate it, multiply the topmost copy by 2 and decrement the result. Now the stack contains two numbers *n* and 2*n* - 1; multiply them and print the result. 12 13 ### B. Gnikool Ssalg 14 15 ``` 16 > ~ : 25*- #v_ $ >:#,_ @ 17 ^ < 18 ``` 19 20 Here the easiest solution is to use the main stack property — elements are popped in reverse order compared to the order in which they were pushed. You can break the solution in two loops — in the first one you read input data till the end of line (#10) and keep the characters on the stack, and in the second one you print stack elements as long as it's not empty. To run a loop (as well as to do any conditional branching) one has to use commands `_` and `|`, but remember that they delete from the stack the element they use to make a choice, so if you're going to need it later, duplicate it. 21 22 ### C. Decimal sum 23 24 ``` 25 0 &>: #v_ $. @ 26 >1- \ & + \v 27 ^ < 28 ``` 29 30 A one-loop problem which requires tracking the current contents of the stack carefully. At the start of each loop iteration the stack contains two elements: the current sum (initialized with zero) and the quantity of numbers you still have to add (initialized by reading input). If the latter is non-zero, the instruction pointer goes into the loop body (second line of the program). There we decrement the counter and swap it with the current sum. After this we read the current number and add it to the sum. Finally we swap the top two elements of the stack again — and we're ready for the next iteration. 31 32 It was also possible to use a memory cell to store the loop counter, but I think it's an unnecessary over-complication. 33 34 ### D. Exponentiation 35 36 ``` 37 &30p & &32p 1 \ >:#v_ $. 25*, @ 38 >1- \ 30g * 32g % \v 39 ^ < 40 ``` 41 42 The task becomes more complicated: this time on each iteration you have to juggle more than two numbers, so the stack alone is not enough — unlike some other stack-based languages, Befunge has no commands which allow access to stack elements buried deeper than top two positions. We'll have to use "memory" — program cells not occupied by useful commands. Commands `p` and `g` are meant for writing self-modifying code, but Befunge has no regular random-access memory, so one has to use whatever it has. 43 44 Usage of memory simplifies things: write *a* and *c* into memory, keep *b* on the stack as loop counter, and keep the current value of the power on the stack as well. In the loop body the required values are extracted from memory as needed, so that the stack doesn't get littered. 45 46 ### E. Tribonacci numbers 47 48 ``` 49 031p032p133p & > 31g 32g + 33g + 39*1-% 32g 31p 33g 32p 33p v 50 | :-1 < 51 > 31g . 25*,@ 52 ``` 53 54 The same principle as in the previous problem, but a bit more memory manipulation; handle with care. 55 56 ### F. Prime factorization 57 58 ``` 59 & 211p > : 1 - #v_ 25*, @ > 11g:. / v 60 > : 11g %!| 61 > 11g 1+ 11p v 62 ^ < 63 ``` 64 65 Forget whatever code you write lightning-fast on any regular contest :-) and recall how you solved this a long time ago. The number itself is small enough, so you can check divisors up to *n* instead of *sqrt*(*n*). If you divide the number by the divisor you find, you're fine with not skipping composite divisors — they won't divide the number anyways. Finally, if a divisor is found, you don't have to find its degree immediately — it's enough not to increment it during this iteration, and you'll find it again on the next one. Keep *n* on the stack, store the current divisor in memory and perform actions in each branch carefully, and the problem will be solved. 66 67 ### G. CAPS LOCK ON 68 69 ``` 70 > ~ : 25*- #v_ 25* , @ >48*-v 71 > :: "`"` \"{"\` * | > , v 72 > ^ 73 ^ < 74 ``` 75 76 This problem is very similar to CamelCase example from the given article about Befunge. It was even easier — you needn't care about the type of the previous character. The most complicated thing about it might be learning "greater than" operation and applying it to correct values. 77 78 ### H. Balanced brackets 79 80 ``` 81 v > "ON" ,, v 82 > ~ : 25*- #v_ $ | > 25*, @ 83 > "SEY" ,,, ^ 84 > : 58*- #v_ v 85 > \ : 58*- #v_v 86 \ $ 87 ^ < <$< 88 ``` 89 90 Originally I intended to give strings which had three types of brackets in them, but by the time I've implemented the check for only one type, I realized that it was a pretty bad idea. Even with one type of brackets you have enough trouble implementing the check. There are two possible ways to solve the problem: store the opening brackets themselves on the stack (with several types of brackets it would be the only option) or store only the quantity of opening brackets which are not closed yet. The answer is "NO" in two cases: if the current bracket is closing and you have no opening brackets on the stack, or if the input data is over and you still have opening brackets left. 91 92 ### I. Array sorting 93 94 ``` 95 v 96 > 543** > :#v_ $&> :#v_ 1 > :0g > :#v_ $ 1+: 543** `! #v_ 25*,@ 97 ^-1p0\0:< ^-1 p0\+1 g0:&< ^-1\.:\< 98 ^ < 99 ``` 100 101 Once again, forget about nice things like Arrays.sort() and recall counting sort. Befunge program is sized 25 x 80, the given numbers can vary between 1 and 60, so we can store the quantity of number i in a cell (0, i), if this part of the program (the first line) has no commands we'll need. The program will have three main loops — initializing memory with zeros, reading input and incrementing values in corresponding memory cells, and convering the resulting values into a sorted array. 102 103 ### J. Date calculation 104 105 ``` 106 56*1+ :10p :30p :50p :70p :80p :52*0p :62*0p 1- :2-20p :40p :60p :90p 92+0p v 107 v % *:*45 : & < 108 > > 20g 1+ 20p v 109 > ! | > v 110 > : 52*:* % ! | 111 > : 4 % !| 112 v << < 113 > . 00g . 25*, @ 114 > $100p & > : 00g 0g ` ! | 115 > 00g 0g - 00g 1+ 00p v 116 ^ < 117 ``` 118 119 This is another problem which is very easy in any high-level language and very ugly in Befunge. First of all we initialize some memory cells with quantities of days in months of a regular non-leap year. Next we read the year index, check whether it's leap and if needed change the number of days in February. Finally, we read the day index and in a loop decrement it by the number of days in the current month while incrementing the index of the current month as many times as possible. Just think how easy this problem would have been if our calendar was organized in a more regular way!