@jinxonik / UniLecs #85

MinRowLen.py

from math import sqrt
from math import ceil

# Найти минимальное число n, при котором ± 1 ± 2 ± ... ± n = k
def min_row_len(k):
  if k == 0: return 3  # частный случай: 1+2-3 = -1-2+3 = 0
  if k < 1: k = -k  # для отрицательных чисел результат будет тем же (знаки чисел ряда будут инвертированы)
  n = ceil((sqrt(1+8*k)-1)/2)  # мин. длина ряда 1..n, сумма которого >= k (решаем уравнение n^2 + n = 2*k)
  dif = n*(n+1)//2 - k  # разница между суммой ряда и k
  # если разница чётная, её можно аннулировать инверсией знака одного из чисел ряда (т.к. при изменении
  # знака числа x результат изменится на 2*x); при dif = 0 знаки не меняются
  if dif % 2 == 0: return n
  # если последнее число ряда чётное, разницу можно аннулировать добавлением ещё одного числа (нечётного),
  # превратив эту разницу в чётное и инвертировав знак одного из чисел ряда
  # иначе (если последнее число ряда НЕчётное), придётся добавлять 2 числа, чтобы сделать разницу чётной
  return n + (1 if n % 2 == 0 else 2)

for k in (-700,-12,-10,-2,-1,0,1,2,3,5,10,12,15,20,50,700,54321,101024,101025,101026,101027):
  print('Min row length for %d is %d' % (k, min_row_len(k)))