NAddOdd
SRM 714 · 2017-02-20 · by dreamoon
Problem Statement
The Collatz conjecture (also known as the 3n+1 conjecture) is a well-known open problem in mathematics. In this problem we'll study a related problem: the n+odd problem.
You are given an odd
For any starting positive integer x, consider the following sequence: x, f(x), f(f(x)), f(f(f(x))), ...
It can be shown that regardless of x and K the sequence will eventually reach a value that is less than or equal to K. Let g(x) be the smallest number of consecutive applications of the function f needed for this to happen.
For example, g(x) = 3 means that the values x, f(x), and f(f(x)) are all strictly greater than K and the value f(f(f(x))) is at most equal to K.
Another example: Suppose K=1 and x=5. This x defines the following sequence: 5, 5+1 = 6, 6/2 = 3, 3+1 = 4, 4/2 = 2, 2/2 = 1, ... Hence, in this case we have g(5) = 5.
You are given two
Constraints
- K will be between 1 and 100,000, inclusive.
- K will be an odd number.
- L and R will be between 1 and 10^16, inclusive.
- L will be smaller than or equal to R.
5 5 1 Returns: 5
we need to calculate g(5). This example is explained by problem statement. So the answer is 5.
1 99999 99999 Returns: 0
For each x in the given range we have g(x) = 0. In general, whenever x <= K, g(x) = 0.
16 17 3 Returns: 9
The sequence for x=16 looks as follows: 16, 8, 4, 2, 1, ... The sequence for x=17 looks as follows: 17, 20, 10, 5, 8, 4, 2, 1, ... Hence, g(16) = 3 and g(17) = 6.
3 7 5 Returns: 4
1645805087361625 9060129311830846 74935 Returns: 421014795656548226
Submissions are judged against all 115 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class NAddOdd with a public method long long solve(long long L, long long R, int K) · 115 test cases · 2 s / 256 MB per case