Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2256. Разбиение последовательности
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 14/11/2015 | Муниципальный этап 7-8 классы (3) |
| 18/11/2015 | Занятие по темам "Бинарный поиск, сканирование" (A) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Последовательность натуральных чисел от 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
Система оценки и описание подзадач
Подзадача 1 (50 баллов)
`2\ ≤\ N\ ≤\ 100`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов)
`100\ <\ N\ ≤\ 10^6`
В этой подзадаче 10 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.
Подзадача 3 (20 баллов)
`10^6\ <\ N\ ≤\ 10^9`
В этой подзадаче 5 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).
