MultiplyAddPuzzle
SRM 707 by Blizzard · 2016-12-07 · by cgy4ever
Problem Statement
- Add a to your current number.
- Multiply your current number by b.
You are given the
Constraints
- s will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- t will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- a will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
- b will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
10 40 4 2 Returns: 2
At the beginning you have the number 10. In each step you can either add 4 to your number, or you can multiply it by 2. You want to reach the number 40. The optimal solution is to use multiplication twice, changing 10 to 10*2 = 20 and then changing 20 to 20*2 = 40.
10 28 4 2 Returns: 2
The same setting, but now the goal is the number t = 28. Again, it is possible to reach this number in two steps. In the first step we add 4, going from 10 to 10+4 = 14. In the second step we multiply by 2, going from 14 to 14*2 = 28.
10 99 4 2 Returns: -1
Whatever you do, the number you'll have will always be even, so it's impossible to reach the odd number 99.
345 12345 1 10 Returns: 895
1 1000000000000000000 1 0 Returns: 999999999999999999
Submissions are judged against all 271 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MultiplyAddPuzzle with a public method long long minimalSteps(long long s, long long t, long long a, long long b) · 271 test cases · 2 s / 256 MB per case