20/04/2024 19:08:42

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

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

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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`.

Пример ввода

Пример вывода

Система оценки и описание подзадач

Подзадача 1 (50 баллов)

`2\ ≤\ N\ ≤\ 100`

В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 2 (30 баллов)

`100\ <\ N\ ≤\ 10^6`

В этой подзадаче 10 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (20 баллов)

`10^6\ <\ N\ ≤\ 10^9`

В этой подзадаче 5 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).

14/11/2015	Муниципальный этап 7-8 классы (3)
18/11/2015	Занятие по темам "Бинарный поиск, сканирование" (A)