<PREV Problem:
NEXT>
Solved by 781 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

What is the number?

Time limit = 5 second(s)

Pete thinks out a rational number (irreducible fraction) x, 0 < x < 1, with denominator less or equal to N.

You may ask him questions like

"Is it true that x < r?"

for any number r.

Please, write program that determines minimal number M(N) of questions that will be sufficient to guess the number. It meens that there exists an algorithm of asking questions such that after M or less questions it leads to unambiguity about x.

Input. One line with N, 1 < N < 5000.

Output. One line with M.

See also the problem 093.

Input#1
2
Output#1
0
Input#2
4
Output#2
3
Input#3
5
Output#3
4

Author:
Voroztsov Artem, MIPT contest, February 2003
14 February 2003

<PREV | Problem set | Search related messages | NEXT>


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

SW soft NIX
ID = 23.20.13.165