MultiplyXPlusOne
2016 TCO India Regional · 2016-03-24 · by cgy4ever
2016 TCO India Regional · 2016-03-24 · by cgy4ever · Brute Force
Problem Statement
Problem Statement
There is a card and at the beginning there is a number s on it, in each step you can do one of this operation:
- Suppose the number on this card is x, change it into 2x+1.
- Suppose the number on this card is x, change it into 3x+1.
Constraints
- s will be between 0 and 1,000,000, inclusive.
- t will be between 0 and 1,000,000, inclusive.
Examples
0)
1 22 Returns: 3
First we use operation 1, the number will become 2*1+1 = 3. Then we use operation 1 again, we get 3*2+1 = 7. Last we use operation 2, it will be 7*3+1 = 22.
1)
1 31 Returns: 3
Although we can get it by 1, 3, 7, 15, 31, we could use less steps by 1, 3, 10, 31.
2)
100 99 Returns: -1
We can't decrease the number, so it is impossible to get 99 from 100.
3)
55555 1000000 Returns: 3
4)
1 1 Returns: 0
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MultiplyXPlusOne with a public method int minimalSteps(int s, int t) · 78 test cases · 2 s / 256 MB per case