11295. 2-variable function

 

Given an integer n, find the smallest integer x that satisfies two conditions:

·        x is greater than or equal to n;

·        There is a pair of non-negative integers (a, b) such that

x = a3 + a2 * b + a * b2 + b3

 

Input. One nonnegative integer n (n ≤ 1018).

 

Output. Print the smallest value of x.

 

Sample input 1

Sample output 1

9

15

 

 

Sample input 2

Sample output 2

0

0

 

 

SOLUTION

full search

 

Algorithm analysis

Let f(a, b) = a3 + a2 * b + a * b2 + b3. The function f is increasing with respect to а at a fixed value of b and is increasing with respect to b at a fixed value of а.

Since n ≤ 1018, function f is cubic with respect to both а and b, then a ≤  = 106 and b ≤  = 106.

We shall search the desired pair (a, b) using the two-pointers method, starting with the interval [0; 106]. Set a = 0, b = 106. While f(a, b) ≥ n and b is non-negative, decrease b by 1. Then increase a by 1 and continue decreasing b by 1 as long as f(a, b) ≥ n and b ≥ 0. Continue this process until a ≤ b.

 

Example

For n = 9, the smallest desired x is 15. For example, f(2, 1) = 15.

For n = 0, the desired x = 0, since f(0, 0) = 0.

 

Algorithm realization

Let’s define a function f(a, b) = a3 + a2 * b + a * b2 + b3.

 

long long f(long long a, long long b)

{

  return (a * a * a + a * a * b + a * b * b + b * b * b);

}

 

Read the input value of n.

 

scanf("%lld", &n);

 

Initialize the value of x.

 

x = 8e18;

 

Start the full search on the interval [0; 106], setting a = 0 and b = 106.

 

b = 1000000;

for (a = 0; a <= b; a++)

 

While f(a, b) ≥ n, decrease the value of b by 1 (as long as b is non-negative). Recalculate the value of x.

 

  while (f(a, b) >= n && b >= 0)

  {

    x = min(x, f(a, b));

    b--;

  }

 

Print the answer.

 

printf("%lld\n", x);