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

Жадные алгоритмы

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

31/10/2012 | Тренировка (задачи NEERC 2011) (G) |

10/07/2017 | Лето 2017 - 8 (A) |

*Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Paul had a birthday yesterday, and they were playing a guessing game there with Andrew: Andrew was trying to guess Paul's age.
Andrew knew that Paul's age is an integer between 1 and `n`, inclusive. Andrew can guess any number `x` between 1 and `n`,
and Paul will tell him what is the greatest common divisor of `x` and his age.

Here's a possible course of the game for `n=6`. Andrew starts with guessing 3, and Paul replies that the greatest common divisor
of 3 and his age is 1. That means that Paul's age can't be 3 or 6, but can still be 1, 2, 4 or 5. Andrew continues with guessing
2, and Paul replies 2. That means that Paul's age can't be 1 or 5, and the only two remaining choices are 2 and 4. Finally, Andrew
guesses 4, and Paul replies 2. That means that Paul's age is 2, and the game is over.

Andrew needed three guesses in the above example, but it's possible to always determine Paul's age in at most two guesses for `n=6`.
The optimal strategy for Andrew is: at the first step, guess 6. If Paul says 1, then it’s 1 or 5 and he can check which one
by guessing 5. If Paul says 2, then it’s 2 or 4, and he can check by guesing 4 as we've seen above.
If Paul says 3, then we already know the answer is 3. Finally, if Paul says 6, the answer is 6.

What is the number of guesses required in the worst case if Andrew guesses optimally for the given `n`?

The input file contains one integer `n`, `2\ ≤\ n\ ≤\ 10\ 000`.

Output one integer –- the number of guesses Andrew will need to make in the worst case.

Sample Input

6

Sample Output

2