Delightful (Easy)
Time limit1sMemory limit512 MB
Write a program of at most 100 commands for a ternary computer with 26 40-trit registers that computes the length of the longest non-decreasing prefix of the input in register X and leaves the answer in Y.
- Level
Hard10 of 10
- Topics
- Implementation, Simulation, Bit manipulation, Greedy
- Solved
- No attempts yet
Problem
You found a strange box in your grandma's basement. A careful inspection revealed that it is an old-school computer. You tried to run a few simple programs, but they all behaved very strangely. It took you a while to find the cause: the computer uses ternary logic and arithmetic!
A trit is the ternary counterpart of a bit. The trits of this computer can hold the values 0, 1, 2. When performing logical operations on trits, we treat 0 as false, 1 as unknown, and 2 as true.
The computer has 26 registers labeled A through Z. Each register is a 40-trit unsigned integer variable.
Write a program that computes ndp: the length of the longest non-decreasing prefix of a number. For example, for a number x of the form 000122012…3, ndp(x)=6, because the first six trits of x are in sorted order but the first seven are not.
Formally, let the ternary representation of x be x39x38…x0. We define ndp(x) as the largest i such that x39 ≤ x38 ≤ ⋯ ≤ x39 − i + 1.
At the start of your program's execution, register X holds the input number and all other registers hold zeros. At the end of your program's execution, register Y must hold the value ndp(X), and the other registers may hold any values.
Your program must contain at most 100 commands.
Input
There is no input.
Output
Your output file must contain a program that satisfies the conditions above and solves the given subproblem.
Empty lines and extra whitespace on each line are ignored, so you may use them freely to format your program for readability. Only non-empty lines count toward the limit on the number of commands. In your program, there must be at least one space between any two tokens, and at least one newline between any two commands.