Вы занимаетесь организацией соревнований для детей, и у вас есть конфет, которые собираетесь раздать в качестве призов. Вы хотите отдать эти конфеты тем, кто займёт первые мест в соревнованиях, и распределить конфеты так, чтобы за более высокое место всегда выходило больше конфет. Чтобы порадовать как можно больше детей, вам понадобится найти самое большое значение , при котором это возможно.
- Входные данные: Целое число .
- Выходные данные: Первая строка содержит максимальное число , при котором можно представить как сумму пар неповторяющихся положительных целых чисел. Вторая строка — пар неповторяющихся положительных целых чисел, сумма которых будет (если есть несколько таких вариантов, то можно использовать любой из них).
- Ограничения: .
Пример 1
|
Ввод |
Вывод |
|
6 |
3 |
Пример 2
|
Ввод |
Вывод |
|
8 |
3 |
Пример 3
|
Ввод |
Вывод |
|
2 |
1 |
✒️ Упражнение:
Можно ли представить 8 как сумму четырёх неповторяющихся положительных целых чисел?
Нетрудно понять, что ответ на этот вопрос: «Нет». Предположим, что и . Тогда , , и . Однако тогда .
По этой же причине, если равно сумме неповторяющихся положительных целых чисел , то . Верно и обратное: если , то можно представить как сумму неповторяющихся целых чисел.
Действительно, пусть . Тогда будет равно сумме следующих целых чисел: . Несложно заметить, что все они отличаются друг от друга.
Алгоритм состоит в нахождении самого большого значения , при котором .
Время выполнения — или .