6.5. Задача «Количество призов»

Вы занимаетесь организацией соревнований для детей, и у вас есть конфет, которые собираетесь раздать в качестве призов. Вы хотите отдать эти конфеты тем, кто займёт первые мест в соревнованиях, и распределить конфеты так, чтобы за более высокое место всегда выходило больше конфет. Чтобы порадовать как можно больше детей, вам понадобится найти самое большое значение , при котором это возможно.

• Входные данные: Целое число .
• Выходные данные: Первая строка содержит максимальное число , при котором можно представить как сумму пар неповторяющихся положительных целых чисел. Вторая строка — пар неповторяющихся положительных целых чисел, сумма которых будет (если есть несколько таких вариантов, то можно использовать любой из них).
• Ограничения: .

Пример 1Пример 1

Ввод	Вывод
6	3 1 2 3

Пример 2Пример 2

Ввод	Вывод
8	3 1 2 5

Пример 3Пример 3

Ввод	Вывод
2	1 2

✒️ Упражнение:
Можно ли представить 8 как сумму четырёх неповторяющихся положительных целых чисел?

Нетрудно понять, что ответ на этот вопрос: «Нет». Предположим, что и . Тогда , , и . Однако тогда .

По этой же причине, если равно сумме неповторяющихся положительных целых чисел , то . Верно и обратное: если , то можно представить как сумму неповторяющихся целых чисел.

Действительно, пусть . Тогда будет равно сумме следующих целых чисел: . Несложно заметить, что все они отличаются друг от друга.

Алгоритм состоит в нахождении самого большого значения , при котором .

Время выполнения — или .