Question

Phyton срочно пожалуйста

Дано ціле число N (>1). Вивести найбільше з цілих чисел K, для яких сума S = 1 + 2 + … + K буде меншою або дорівнює N, і саму цю суму.​

Answer 1

Асимптотика: что-то типа O(NlogN)

def f(n):

return n * (n + 1) // 2

def bs(n):

left = 0

right = n

while left < right:

 mid = (left + right) // 2

 now = f(mid)

 if now <= n and f(mid + 1) > n:

  return mid

 if now > n:

  right = mid - 1

 else:

  left = mid + 1

return left

k = bs(int(input()))

print(k, f(k), sep='\n')