Shadow Companion
Time limit2sMemory limit512 MB
Construct a fixed program over a bit tape with a shadow that transforms every input n < 2^10 into n squared.
- Level
Hard10 of 10
- Topics
- Simulation, Bit manipulation, Implementation, Math
- Solved
- No attempts yet
Problem
You are given a number in its binary representation with infinitely many leading zeroes. You can walk over its bits and do some operations with them.
More precisely, you can make the following moves:
- "s": summon a shadow. Your shadow appears one bit to the left of your current position.
- "l": walk one bit to the left. Your shadow, if it exists, does the same.
- "r": walk one bit to the right. Your shadow, if it exists, does the same.
- "L": if the bit you are standing at is 1, walk one bit to the left; otherwise do nothing. Your shadow, if it exists and is standing at 1, also walks one bit to the left. Note that you and your shadow behave independently. You move if you are standing at 1, and it moves if it is standing at 1.
- "R": the same as the previous option, but you and your shadow move right instead of left.
- "x": exchange positions with your shadow. If it does not exist, nothing happens.
- "f": flip some bits (flipping means replacing 0 by 1 and vice versa). You flip two bits: the bit you are standing at and the bit to your left. Your shadow, if it exists, is not as strong as you and flips only the bit it is standing at. Note that during this move some bit may be flipped twice and therefore remain unchanged.
Initially you are at the rightmost (least significant) bit, and . Write a program (that is, a sequence of moves) that satisfies the following:
- Neither you nor your shadow ever tries to move to the right from the least significant bit (in other words, do not try to leave the number).
- Your program consists of no more than 500 000 commands.
- The number at the end is .
Some technical details:
- If after some move you and your shadow have the same position, your shadow disappears.
- If you summon a shadow when you already have one, your previous shadow disappears.
- Your position at the end may be arbitrary.
- Your shadow is allowed to exist at the end, and its position may be arbitrary.
- During execution, the number represented by the bits may be arbitrarily large. The only constraint on it is that it must equal at the end.
- Again, if you and your shadow flip the same bit simultaneously, it does not change.
Input
There is no input.
Output
Print a single string consisting of no more than 500 000 letters from the set "slrLRxf" representing your program.
Hint
The sample output is incorrect. In fact, it is a program which, starting from the state where the two rightmost bits are and and the other bits are zeroes, reaches the state where all the bits are zeroes and the third bit (1-indexed) is the Sheffer stroke of and (that is, ).
Below is an example of how it works for :
