DoubleOrOneEasy
SRM 677 · 2015-11-03 · by cgy4ever
SRM 677 · 2015-11-03 · by cgy4ever · Math
Problem Statement
Problem Statement
You have two positive integers: the first one is a, the second one is b.
You also have a red button and a blue button.
Whenever you push the red button, both your numbers are incremented by 1.
Whenever you push the blue button, both your numbers are multiplied by 2.
Your goal is to change the pair (a, b) into the pair (newA, newB).
You are given theint s a, b, newA, and newB.
If there is a sequence of zero or more button pushes that accomplishes your goal, return the length of the shortest such sequence. Otherwise, return -1.
You also have a red button and a blue button.
Whenever you push the red button, both your numbers are incremented by 1.
Whenever you push the blue button, both your numbers are multiplied by 2.
Your goal is to change the pair (a, b) into the pair (newA, newB).
You are given the
If there is a sequence of zero or more button pushes that accomplishes your goal, return the length of the shortest such sequence. Otherwise, return -1.
Notes
- The operations can produce arbitrarily large integers. For example, if you just push the blue button 1000 times in a row, you will get the numbers a*2^1000 and b*2^1000.
Constraints
- a will be between 1 and 1,000,000,000, inclusive.
- b will be between 1 and 1,000,000,000, inclusive.
- newA will be between 1 and 1,000,000,000, inclusive.
- newB will be between 1 and 1,000,000,000, inclusive.
Examples
0)
100 1000 101 1001 Returns: 1
Just push the red button once.
1)
100 1000 202 2002 Returns: 2
The best solution is to push the red button followed by the blue button. This performs the operation +1 followed by the operation *2. Another valid solution is to push the blue button once and then the red button twice to perform the operations *2, +1, and +1. This solution is not optimal because the previous solution contains fewer operations.
2)
2 2 1 1 Returns: -1
We are unable to decrease a and b.
3)
1 111111111 8 888888888 Returns: 3
4)
1 111111111 9 999999999 Returns: -1
Submissions are judged against all 197 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DoubleOrOneEasy with a public method int minimalSteps(int a, int b, int newA, int newB) · 197 test cases · 2 s / 256 MB per case