DoubleOrOne
2015 TCO Semifinal · 2015-04-08 · by lg5293
Problem Statement
You are given two
More precisely, in each step you will perform one of the following two moves:
- Move '0': add 1 to a, multiply b by 2
- Move '1': multiply a by 2, add 1 to b
Any sequence of steps can now be written as a string of zeros and ones.
It is guaranteed that for each pair a, b that satifies the constraints (given below) it is possible to reach the goal in at most 2500 steps.
Find any such sequence of steps and return a
Note that your solution does not have to minimize the number of steps. Any valid solution that consists of at most 2500 steps will be accepted.
Notes
- The fact that a and b are given as ints does not imply any upper bound on their values. For example, if you start with a=1 and perform move '1' exactly 1000 times, you will have a=2^1000.
Constraints
- a,b will be between 0 and 100, inclusive.
1 1 Returns: ""
Nothing needs to be done here.
1 2 Returns: "11"
One way to make a,b equal is to apply move '1' twice. In this case, we get the following sequence: (1,2) -> (2,3) -> (4,4).
2 1 Returns: "1110100"
This example is the same as Example 1, only with a and b swapped. Here we intentionally show a different correct sequence of steps. Note that the answer "00" would also be accepted.
10 24 Returns: "001101011"
(10, 24) -> (11, 48) -> (12, 96) -> (24, 97) -> (48, 98) -> (49, 196) -> (98, 197) -> (99, 394) -> (198, 395) -> (396, 396)
0 64 Returns: "10111101111"
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DoubleOrOne with a public method string findSequence(int a, int b) · 70 test cases · 2 s / 256 MB per case