expression.py

# task_85
# Рассмотрим сумму чисел от 1 до n. По она равна n(n+1)/2 и это очивидно максимальное
# возможное значение выражения. Заметим, что если в сумме у какого-то члена z поменять знак, то
# сумма уменьшится на 2*z. Из этого следует что, n должно быть таким чтобы n(n+1)/2 - k было четным
# Дальше все просто, начальная оценка для n получается из решения уравнения n(n+1)=2k. Далее она уточняется
# чтобы удовлетворить условию четности(максимум может понадобиться добавить 2 числа в последовательность).
# случай когда k < 0 симметричен, поэтому мы просто берем модуль в самом начале
import math

# sum of number from 1 to n
def range_sum(n):
    return n*(n+1)//2

# solve quadratic equation
def estimate_n(k):
    return int(-1+math.sqrt(1+8*k))//2

def solve(k):
    k = abs(k)
    n = estimate_n(k)
    #adjust n because of dropping floating point part
    if range_sum(n) < k:
        n += 1
    # adjust to satisfy difference constraint. Max 2 iterations
    while (range_sum(n)-k) % 2 == 1:
        n += 1
    return n

print("k = 2; n = {}".format(solve(2)))
print("k = 3; n = {}".format(solve(3)))
print("k = 4; n = {}".format(solve(4)))
print("k = 5; n = {}".format(solve(5)))
print("k = 12; n = {}".format(solve(12)))
print("k = 15; n = {}".format(solve(5)))
print("k = 1; n = {}".format(solve(1)))
print("k = -2; n = {}".format(solve(-2)))
print("k = -5; n = {}".format(solve(-5)))