2

Нужно посчитать сколько есть способов представить число, как сумму трех разных чисел. Например число 8 можно представить двумя способами: 1 + 2 + 5 и 1 + 3 + 4. А число 6 одним: 1+2+3. Решение должно быть O(n). Мне пока удалось только посчитать количество способов, где два из трех слагаемых могут быть одинаковым. А вот как провести условие, чтоб все три были разные, не могу понять.

def count(n):
  counter = 0

  if n < 6: 
    return counter
  else:
    counter = (n - 1) * (n - 2) / 2

  return counter


if __name__ == "__main__":
    print(count(6)) #1 
    print(count(8)) # 2
    print(count(30)) # 61
    print(count(1337)) # 148296
2
  • 2
    Вообще-то 1+2+3==6...
    – Harry
    17 сен 2020 в 11:23
  • да, пардон, исправлено
    – braflovsky
    17 сен 2020 в 11:26

2 ответа 2

8

А обязательно за O(n)? За O(1) можно?

n = int(input())

j = n//6
k = n % 6
if k == 0:
    j = j - 1
    k = 6

n = (3*j+k-3)*j
if k == 6: n = n+1

print(n)

Вроде бы так, если поверить вот этому материалу

Можно еще посмотреть на эту последовательность и эту

Нет, конечно, я могу вклеить сюда цикл и получить O(n)... :-)

3
  • Ну что вы, не стоит цикл вклеивать, раз так))
    – braflovsky
    17 сен 2020 в 12:00
  • За n обычно берут объем данных. Для числа это количество цифр (битов). Умножение столбиком выполняется за O(n^2), есть способ получше, но он все равно не мгновенный и даже не линейный. Но это я так, занудствую :)
    – extrn
    17 сен 2020 в 14:48
  • 2
    @extrn В данном случае все же n - это само число, а не количество бит в нем. Да и в рамках задачи, когда числа не произвольной огромной длины - умножение выполняется за одно и то же время...
    – Harry
    17 сен 2020 в 15:41
0

Легче посчитать количество плохих и вычесть из общего. Количество троек, где двое равны - можно посчитать за O(n)(можно и быстрее)(просто перебирать повторяющийся элемент). Количество троек, где равны может быть не больше 1(n либо делится на 3,либо нет). Количество троек всего равно C(n + 2, 2)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.