images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
23/04/2024 21:58:32

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

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1806. Cut

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Let's say that there exists a huge cake made from blueberries, strawberries and chocolate. It's shaped like a square, and has area of 100 square meters. Proffesionals strongly advise that cake is being cut with wet knife and eaten with dry spoon. Also:
  • Every cut begins and ends on the cake's perimeter
  • A cut cannot lie completely on one of the sides
  • No two cuts have the same starting and ending points, i.e. all cuts are different
Parts obtained by these cuts are separated and counted only after last cut has been made. During cutting, the cake keeps its square form.
At least how many cuts need to be made in order to obtain exactly `K` parts?
The first and only line of input contains an integer `K` (`1\ ≤\ K\ ≤\ 1\ 000\ 000`), number of parts that we must have after cutting is done.
The first line of output should contain the requested number of cuts.

Sample Input #1

1

Sample Output #1

0

Sample Input #2

4

Sample Output #2

2

Sample Input #3

7

Sample Output #3

3
Source: COCI 2011/2012
loading