TwoRegisters
TCO10 Round 1 · 2010-04-11 · by soul-net
Problem Statement
You have a very simple computer whose memory consists only of two registers X and Y. Each of them can store a positive integer. The computer is so simple that it only has two different instructions (between brackets is the name of each instruction):
[X] X := X + Y [Y] Y := X + Y
As you may have imagined, both instructions compute the sum of both registers and store the result in one of them, overwriting its previous content. A program for this computer is simply a sequential list of zero or more instructions. When a program starts in this computer, both registers are initialized to 1. For instance, if the program is "XXYYX" then the following happens:
X | Y | ins | execute ----+---+-----+------------ 1 | 1 | [X] | X := X + Y ----+---+-----+------------ 2 | 1 | [X] | X := X + Y ----+---+-----+------------ 3 | 1 | [Y] | Y := X + Y ----+---+-----+------------ 3 | 4 | [Y] | Y := X + Y ----+---+-----+------------ 3 | 7 | [X] | X := X + Y ----+---+-----+------------ 10 | 7 |
You will be given an
Notes
- A String comes lexicographically earlier than another one of the same length if and only if it contains a letter closer the beginning of the alphabet in the first position at which they differ.
Constraints
- r will be between 1 and 1000000 (106), inclusive.
10 Returns: "XXYYX"
The example in the problem statement.
3 Returns: "XX"
20 Returns: "XYYYYXX"
34 Returns: "XYXYXYX"
1000000 Returns: "XXYXYXYXXYXYXYXXYYXXYXYYXYYXYX"
Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TwoRegisters with a public method string minProg(int r) · 150 test cases · 2 s / 256 MB per case