JumpAcrossTheRiver
SRM 793 · 2020-11-03 · by misof
Problem Statement
There is a wide river. Somebody placed a sequence of N+1 stones into the river along a line that goes from one river bank to the other. People can now use these stones to jump across the river.
We will number the stones from 0 to N. Stone 0 is on one bank of the river, stone N is on the other bank, the other stones lie between them in numerical order. For the purpose of this problem, assume that each stone is a point and that all these points lie on one straight line.
For each valid i, the distance between stones i and i+1 is equal to 1 + ((i*i) mod M). For example, if M = 10, the distance between stones 6 and 7 is 1 + (36 mod 10) = 1 + 6 = 7.
You want to get across the river by making at most J jumps, but you are afraid that your maximum jump length might be too short for that. Calculate and return the smallest L such that a person capable of making jumps of length at most L can get across the river in at most J jumps.
(When jumping across the river, the first jump must begin on stone 0; each jump must end on a stone; and in particular, the last jump must end on stone N.)
Notes
- It can be shown that the smallest L we seek is always an integer.
Constraints
- N will be between 1 and 1,000,000, inclusive.
- M will be between 1 and 10^9 + 7, inclusive.
- J will be between 1 and N, inclusive.
10 1 1 Returns: 10
There are 10+1 = 11 rocks in this river, and as M = 1, the distance between any two consecutive rocks is 1. Hence, the distance between the two banks of the river is 10. We want to get across this river in a single jump. Clearly, the jump length we need for that is at least 10.
10 1 3 Returns: 4
L = 4 is sufficient to get across this river in three jumps. E.g., we can jump from stone 0 (the first bank) to stone 3, from there to stone 6, and from there to stone 10 (the other bank). L = 3 is not sufficient (in three jumps we can only get to stone 9), so L = 4 must be optimal.
10 1234567 10 Returns: 82
Here we are allowed to make 10 jumps, which means that we can simply jump from one stone to the next. The longest jump we'll need to make is the jump from stone 9 to stone 10. The length of this jump is 82. Above we have shown that L = 82 is long enough. Now all that remains is to realize that a person with maximum jump length L = 81 cannot get to the other bank of this river at all, so L = 82 must indeed be optimal.
10 1234567 4 Returns: 87
If our maximum jump length is 87, we can get across this river in four jumps: from stone 0 to stone 6 (jump length 1+2+5+10+17+26 = 61), from stone 6 to stone 8 (jump length 37+50 = 87), from stone 8 to stone 9 (jump length 65) and from stone 9 to stone 10 (jump length 82).
123456 1000000007 2 Returns: 27561114912135
Watch out for integer overflow, in particular when computing the distances between consecutive stones.
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class JumpAcrossTheRiver with a public method long long minLength(int N, int M, int J) · 110 test cases · 2 s / 256 MB per case