MahdiJumping
SRM 767 · 2019-09-17 · by minimario
Problem Statement
Mahdi is playing a game in Quera.
In the beginning he is standing on position 0. His goal is to reach position n-1.
From any position x other than n-1, he can simply go to position x+1. Each such move costs a.
From any position x he can jump to position (A*x+B) mod n. Each such jump costs b.
Compute and return the minimal total cost of reaching the goal.
Constraints
- n, A, a, and b will each be between 1 and 5,000,000, inclusive.
- B will be between 0 and 5,000,000, inclusive.
7 1 1 1 5 Returns: 6
Mahdi will simply go to 1, 2, 3, 4, 5, 6.
5 2 2 1 2 Returns: 3
Mahdi will go to x = 1 and then to x = 4.
5 5 5 5 5 Returns: 20
5000000 314 5 1 2 Returns: 31
5000000 5 5 5 5 Returns: 175
Submissions are judged against all 153 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MahdiJumping with a public method long long minDis(int n, int A, int B, int a, int b) · 153 test cases · 2 s / 256 MB per case