Олимпиадный тренинг

Задача . Разбиение последовательности


Задача

Темы:
Последовательность натуральных чисел от 1 до `N` нужно разбить на две части от 1 до `K` и от `K+1` до `N` так, чтобы абсолютное значение разности суммы чисел в первой и второй части последовательности было как можно меньше. То есть нужно найти такое `K`, что значение выражения `|\ sum_{i=1}^K\ i\ -\ sum_{i=K+1}^N\ i\ |` минимально. Например, для последовательности чисел от 1 до 4 разбиение будет минимальным для `K=3`, так как `|\ (1+2+3)-(4)\ |\ =\ 2`, что меньше значения разности для `K=1` равного `|\ (1)-(2+3+4)\ |\ =\ 8` и для `K=2` равного `|\ (1+2)-(3+4)\ |\ =\ 4`.
Напишите программу, которая для заданного `N` находит минимальное разбиение.
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).
Вывести одно целое число `K`. Если существует несколько вариантов разбиения, то вывести меньшее из возможных `K`.

Ввод Вывод
4 3




time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Free Pascal2
Комментарий учителя