Попарно отдельные слагаемые

Попарно отдельные слагаемые

Эта проблема была взята из Coursera Специализация по структурам данных и алгоритмам, в частности из Курса Algorithmic Toolbox, неделя 3: Жадные алгоритмы, которые я недавно завершил. Если вы проходите этот курс или планируете пройти этот курс, пожалуйста, не ждите решения, поскольку оно противоречит Кодексу чести и не принесет вам никакой пользы.

Введение в проблему

Это пример проблемы, в которой подзадача соответствующего жадного алгоритма немного отличается от исходной задачи.

описание проблемы

Задача. Цель этой задачи - представить заданное положительное целое число n как сумму как можно большего числа попарно различных положительных целых чисел. То есть, чтобы найти максимальное k такое, что n можно записать как a (1) + a (2) + ··· + a (k), где a ( 1),…, a (k) - положительные целые числа и a (i)! = A (j) для всех 1 ≤ i ‹j ≤ k.
Формат ввода. Входные данные состоят из единственного целого числа n.
Ограничения. 1 ≤ n ≤ 10 ^ 9
Формат вывода. В первой строке выведите максимальное число k, чтобы n можно было представить как сумму k попарно различных положительных целых чисел. . Во второй строке выведите k попарно различных положительных целых чисел, которые в сумме дают n (если таких представлений много, выведите любое из них).
Ограничения по времени. C: 1 сек, C ++: 1 сек, Java: 1,5 сек, Python: 5 сек. C #: 1,5 секунды, Haskell: 2 секунды, JavaScript: 3 секунды, Ruby: 3 секунды, Scala: 3 секунды
Ограничение памяти. 512 Мб

Образец 1

Вход:
6
Выход:
3
1 2 3

Образец 2

Вход:
8
Выход:
3
1 2 5

Образец 3

Вход:
2
Выход:
1
2

Что делать

Чтобы найти алгоритм решения этой проблемы, вы можете немного поиграть с маленькими числами. Предположим, например, что мы хотим представить 8 как сумму как можно большего числа попарно различных слагаемых. Что ж, естественно попробовать использовать 1 в качестве первого слагаемого, не так ли? Затем остающаяся проблема состоит в том, чтобы представить 7 как сумму максимального числа попарно различных натуральных чисел, ни одно из которых не равно 1. Затем мы берем 2 и остаемся со следующей проблемой: представить 5 как сумму различных положительных целых чисел. каждое из которых не меньше 3. Ясно, что в этом случае мы не можем использовать два слагаемых (понимаете почему?). В целом, это дает нам следующее оптимальное представление:
8 = 1 + 2 + 5.
В общем, наша подзадача такова: заданные целые числа k и l, где l ≤ k, представляют k как a сумма как можно большего количества попарно различных целых чисел, каждое из которых не меньше l. Если k ≤ 2l, то ответ очевиден: 1. В противном случае можно безопасно использовать l в качестве одного из слагаемых. Сформулируем и докажем это формально.
Лемма 5.1. Пусть k ›2l и p будет максимальное число такое, что k можно представить как сумму p попарно различных слагаемых, каждое из которых не меньше l. Тогда существует оптимальное представление k = a (1) + ··· + a (p) (то есть все a (i) не меньше l и попарно различны) такое, что a (1) = l .
Доказательство. Рассмотрим некоторое оптимальное представление k = b (1) + ··· + b (p). Без ограничения общности предположим, что b (1) ‹b (2)‹… ‹b (p). Мы знаем, что p ≥ 2 (при k ›2l). Если b (1) = l, то все готово. В противном случае пусть ∆ = b (1) - l ≥ 1. Рассмотрим следующее представление n:
n = (b (1) - ∆) + b (2) + ··· + (b (p) + ∆).
Нетрудно понять, что это верное и оптимальное представление (оно содержит p слагаемых, и все они различны, так как (b (1) - ∆) ‹b (2)‹… ‹(b (p) + ∆))
Несложно заметить, что наша исходная задача имеет тот же тип: нам нужно представить целое число n как сумму максимального количества попарно различных целых чисел, каждое из которых не менее 1 (следовательно, k = n и l = 1).
Подводя итог, изначально мы имеем k = n и l = 1. Чтобы решить (k, l) -подзадачу, мы делаем следующее. Если k ≤ 2l, мы выводим только одно слагаемое k. В противном случае мы выводим l, а затем решаем подзадачу (k − l, l + 1).

Мое решение:

Если вы можете придумать какой-либо другой способ улучшить этот алгоритм или указать на что-то, что, по вашему мнению, я сделал неправильно, вы более чем рады связаться со мной, ответив к этому и указав на ошибки. Если вам нравится это решение, нажмите кнопку «Рекомендовать» ниже, это будет много значить для меня. Спасибо.