TopCoder Statistics - Problem Statement

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 int r. Return the shortest program for the described computer that makes register X end with value r. Register Y may contain any value. If there are several such programs, return the one that comes earliest lexicographically.

Definition

Class:: TwoRegisters
Method:: minProg
Parameters:: int
Returns:: String
Method signature:: String minProg(int r)
(be sure your method is public)

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.

Examples

10

Returns: "XXYYX"

The example in the problem statement.
3

Returns: "XX"
20

Returns: "XYYYYXX"
34

Returns: "XYXYXYX"
1000000

Returns: "XXYXYXYXXYXYXYXXYYXXYXYYXYYXYX"
999999

Returns: "XXYXYXXYXYXYXYYXXYXYXYXYYYXYXX"
999998

Returns: "XXYXXYXYXXYYXXYXYYXYXYYXYXYXYX"
999997

Returns: "XXYXXYYXYXXYXYYXYXYXXYXYXYXXYX"
999996

Returns: "XYXXYXYXXYXYXYXYYXXXYYXYXXYXYX"
999994

Returns: "XXXXYXXYXXYXXYYXYXYYXYXYXYXYXYX"
999983

Returns: "XXYXXYXYXYXYXYXXYXYXXYXXYYXXYX"
999973

Returns: "XXYXYXXYXYXXYXXYXYXYXXYYXXYXYX"
999971

Returns: "XXYXYXXXYXYXYYXXYXYYXYXYXYXYXX"
999961

Returns: "XXYXYXYXYYXYXYXYXXYYXYXYYYXYXX"
999960

Returns: "XYXXYXYXYYXXXYYXYXXYXYXYYXYXYX"
994009

Returns: "XXYXYXXYXXYYXXYXYXXYXYXYXYYXYX"
994009

Returns: "XXYXYXXYXXYYXXYXYXXYXYXYXYYXYX"
964573

Returns: "XYXYXYXYYXYXYXXYXYXYXYYXYXYXX"
964559

Returns: "XXYXYYXXYXYXXYYXXYYXYYXYXYXYXX"
964545

Returns: "XXYYXYXYXYXYXYYXYXXYXYYYXXYXYX"
926617

Returns: "XXYXXXYYXXYXYXYXYXYYXYXYXYXXYX"
925315

Returns: "XXXYXXYXYXYXYXYYXYXYXXYXYYXYXX"
707281

Returns: "XYXYXYXYXXYYYXXYXYYXYXYXYXXYX"
676188

Returns: "XXYYXXYYXXYXYYXYXYXYXYYXYXYXX"
671696

Returns: "XXXXYXYXXYYXYYXXYXYXYXYXYYXYXX"
655980

Returns: "XXXXYXXYXYXXYXYXYXYXYYXXYYXYXX"
533575

Returns: "XXXYXYXYYXYXXYXXYXYXXYYXYXYXX"
318255

Returns: "XXXYXYXYYYXYYXYXYXYXXYXYXYXX"
309763

Returns: "XXYXYXYXXYXXYXYXYXYYXYXYXYX"
309763

Returns: "XXYXYXYXXYXXYXYXYXYYXYXYXYX"
306079

Returns: "XXXYXYXYXYXYXYXXYYYXYXYXXYYX"
306079

Returns: "XXXYXYXYXYXYXYXXYYYXYXYXXYYX"
273851

Returns: "XXYXYXYXYXYYXYXXYYXXYXYXXYX"
262144

Returns: "XYXXYXYYYXYXYYXYYXYXYXYXYXX"
234719

Returns: "XXYXXXYYXYXYXYXXYXYXYXXYXYX"
182629

Returns: "XXYXXYXYXYYXYXYYYXYXYYXXYYX"
182629

Returns: "XXYXXYXYXYYXYXYYYXYXYYXXYYX"
181402

Returns: "XXXYXYYYXYXYXYXYYXYXYXYYXXX"
180457

Returns: "XXXYXYXYXYXYXXXYXYYXXYYXXYX"
180457

Returns: "XXXYXYXYXYXYXXXYXYYXXYYXXYX"
174557

Returns: "XXXYXXYYXYYXYXYXYYXXYYXXYXX"
174557

Returns: "XXXYXXYYXYYXYXYXYYXXYYXXYXX"
172481

Returns: "XXXXYXYXYXYYXXYXYXYXYXYYXXX"
172481

Returns: "XXXXYXYXYXYYXXYXYXYXYXYYXXX"
130085

Returns: "XXYYXXXYYXXYYXXYYXYXYXYXYX"
130079

Returns: "XYXYXXYXYXXYYXYXYXXYXYXYX"
130074

Returns: "XXYYYXYXXYXYXYXYYXXYYXYYXX"
94249

Returns: "XYXXYXXYXXYXYXXYXXYXXYXYX"
94249

Returns: "XYXXYXXYXXYXYXXYXXYXXYXYX"
55567

Returns: "XXYXYXYXXYYXYYYXYXYXYYXX"
55567

Returns: "XXYXYXYXXYYXYYYXYXYXYYXX"
53111

Returns: "XYXYXYXYXXYXXYXYXYYXYXX"
53111

Returns: "XYXYXYXYXXYXXYXYXYYXYXX"
47502

Returns: "XXXYXYXXYXYXXYXYYYXYXYXX"
47501

Returns: "XXXYXXYXYXYYXYXYXYXYYYXX"
47500

Returns: "XXXYXXYXYYXXYXYXXYXYYXYX"
32768

Returns: "XYXXYXYXYXYXXYXYXYYXYX"
32761

Returns: "XXYXXXYXYYXYXXYXYXXYXYX"
32761

Returns: "XXYXXXYXYYXYXXYXYXXYXYX"
31313

Returns: "XXYXXXYXYXXYYXXYXYXYYXX"
31313

Returns: "XXYXXXYXYXXYYXXYXYXYYXX"
29929

Returns: "XXXYXYXYXYYXYXXXYXYXXYX"
29929

Returns: "XXXYXYXYXYYXYXXXYXYXXYX"
24389

Returns: "XXYXYXYXXYYYXYXXYXYXYX"
6561

Returns: "XXYXXYXYXYXYXYXXYYX"
6222

Returns: "XYXYYXXYXXYYXYYXXYX"
6221

Returns: "XXYXXYXYYXYXYXXYYXX"
6216

Returns: "XXYXYXXYXYXXYYXYYXX"
4096

Returns: "XYXXYXYXXXYYXYXYXX"
1024

Returns: "XXYXXYXYXYXYXXX"
1012

Returns: "XXXYXXYYXXYYXYYX"
1009

Returns: "XXYXXYXYXYYXXYX"
1007

Returns: "XYXXYYXXYYXYYXX"
1000

Returns: "XXYYXYYXYXYYXYX"
997

Returns: "XXYXYYYXYXYXYXX"
996

Returns: "XXXYXXYXYYXYYYXX"
841

Returns: "XXXYXXYXYXXYXYX"
512

Returns: "XXXYXYXYYXYXXX"
308

Returns: "XYXYXXYXYYXX"
307

Returns: "XYXYYXYXYYXX"
303

Returns: "XYXYXYYXYYXX"
256

Returns: "XXYYXXYYXYXX"
183

Returns: "XYXXYXXYXYX"
181

Returns: "XXYXYXYXXYX"
178

Returns: "XXYXYXXYXYX"
177

Returns: "XXYXYXYYXYX"
173

Returns: "XYXXYYXYYXX"
169

Returns: "XXYYXYXYYXX"
128

Returns: "XYXXYXYXYX"
81

Returns: "XYXYXYYXX"
64

Returns: "XXYYXYYXX"
32

Returns: "XXXYXYYX"
29

Returns: "XXYXYXX"
16

Returns: "XYYYXX"
9

Returns: "XXXYX"
8

Returns: "XYXX"
7

Returns: "XXYX"
6

Returns: "XXXXX"
5

Returns: "XYX"
4

Returns: "XXX"
2

Returns: "X"
1

Returns: ""
3847

Returns: "XXXXYXXYXYXXYXYYXYX"
15061

Returns: "XXXXYXYXXXYXYXXYXYXYXX"
37491

Returns: "XXXXYXXYXYYXXYXYXYXXYYXX"
38069

Returns: "XXXXYYXYXXYXYXXYXXYXYYXX"
39791

Returns: "XXXXYXXYYXYXXYXYXYXYYXYX"
59881

Returns: "XXXXYXYXXYXXYYXXYXYXXYXYX"
61073

Returns: "XXXYXYXYXYXXYXYXYYYXXXYYX"
95831

Returns: "XXXXYXYYXYXXYYXYYXYXYYXYXX"
999859

Returns: "XXXXYYXXYXYXYXYXYYXXYXYXYYXYXXX"
999517

Returns: "XXXXYXYXYXYXYXXYYXXYXXYYXYXXYXX"
998537

Returns: "XXXXYYXYXXYXYXYXYYXYYXXYXYXXYXX"
972653

Returns: "XXXXYYXXYXXYXXYXYXXYXYXYXXYXYXX"
947369

Returns: "XXXXYXYYXYYXYXYXYYXYXYXXYXXYYXX"
944747

Returns: "XXXXYXYXXYYXYXYXXYXYXYYXXYYXXYX"
987654

Returns: "XXXYXXYXYXXYXYXYXXXYYYXXYXYXYXX"
999977

Returns: "XXYXYXYXYXYXYYXXYYYXXYXYXYXXYX"
953124

Returns: "XXXYXYXYXXXYXYXYXXYXYYXYYXXYXXX"
999990

Returns: "XXXXYYXXYXYXYYXYXYXYXYYXYXYYXXX"
321232

Returns: "XXYXYXXYXXYXYXYYYXXYXYXXYYXX"
999763

Returns: "XXYXYXYXXYYXYXXYYXYYXYYXYXYXYX"
814239

Returns: "XXYXXYYYXYYXXYXYXYYXYXYXYXXYXX"
832038

Returns: "XXYXYXYXYXYXYXXXYXYXYXYXYXYXX"
987549

Returns: "XXXYXYYXYYXYXXYXYXYXXYXXXYXYYXX"
999898

Returns: "XXXXYXYXXYXXYXYXYXXYXYYXYXYYXYX"
99999

Returns: "XXYXYYXYYXYXYYXYXYXYYXXYX"
832040

Returns: "XYXYXYXYXYXYXYXYXYXYXYXYXYXX"
999979

Returns: "XXYXYXYXYXXYXYYXXYXYXXXYXYXYXX"
832039

Returns: "XXYXYXYXYXYXYYXYXXYXXXYXXYXXYX"
957867

Returns: "XXYYXXYXXYYXYXYXYXYXYYXYYXXYXX"
99988

Returns: "XYXXYYXXYXYXYYXYYXXYXYYXX"
997243

Returns: "XXXXYYXYYXYXXXYXYYXYXYXYXYXYXYX"
148459

Returns: "XXYXYXYXYYXXYYXYXYYXYXXYYX"
948317

Returns: "XYXXYXXYYXYYXYYXXYYXYXYXYYXYXX"
978956

Returns: "XXXYXYXXXYYXYXYXXYXYXYXXYYXXYYX"
567423

Returns: "XXYYXXYXYXXYYYXXYXYXYXYYXYXYX"
999753

Returns: "XYXYXYXYXXYXYXYXYXYYXXXYXYYYXX"
100000

Returns: "XXYYXXXYYXYXYXYXYXYXXYXYX"
983421

Returns: "XXYXYYXYXXYXXYXYXYXYYXXYXYYXYX"
999987

Returns: "XXYXYXYYXXYXYXYXYXYYXYXYYYXYXX"
1252

Returns: "XXXYXXYXYXXYYXYX"
994758

Returns: "XXXYXXYYXYXXYXYYXXXYYXYXYXYYXYX"
979543

Returns: "XXYXYYXXYXYXYXXYXYXYXYXXYXXYYX"
948741

Returns: "XXYXYYXYXYXYXYXXYXYYXXYXXYXYYX"
12388

Returns: "XXXYXXYXXYYXYXYXXYXYX"
836833

Returns: "XXYXYXXYYXXYYXYXYXYXYYXXXYYXYX"
869357

Returns: "XXYXYXXYXXYXYXYYXYYXYYXYXYXYYX"
1113

Returns: "XXXYXYXYXYXXYYYX"
747793

Returns: "XYXYXXYXYXYXYXXYYYXYXYXYXYYXX"

Statistics

Problem Statement for "TwoRegisters"

Problem Statement

Definition

Notes

Constraints

Examples