<ПРЕД Задача:
СЛЕД>
Задачу решил 781 пользователь: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Угадай число

Time limit = 5 секунд(ы)

Петя загадал рациональное число (несократимую дробь) больше нуля и меньше единицы, со знаменателем меньше либо равно N. Вы можете задавать ему вопросы типа

"верно ли, что число меньше r?"

где вместо r можно подставлять любое рациональное число.

По числу N определите минимальное число вопросов M(N), которых наверняка хватит, чтобы узнать загаданное Петей число. То есть такое число M, что существует алгоритм задавания вопросов, который при данном N для всех возможных вариантов загаданного числа узнает, чему равно загаданое число, меньше либо равно, чем за M вопросов, и алгоритма с меньшим M не существует.

Вход. Вход состоит из одной строчки, в которой находится натуральное число N, 1 < N < 5000.

Выход. Одна строчка, в которой находится натуральное число — минимальное число вопросов, которого аверняка хватит, чтобы угадать загаданное число.

См. также задачу 093.

Вход#1
2
Выход#1
0
Вход#2
4
Выход#2
3
Вход#3
5
Выход#3
4

Автор:
Ворожцов Артем, Физтех олимпиада, февраль 2003.

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.224.197.86