Solved by 313 users: ...
UserDateAttemptTimeCMSC
david_it21`19 apr 2008`Ruby2000.0234
david_it21`19 apr 2008`Ruby1900.0235
david_it21`19 apr 2008`Ruby1800.0237
david_it21`19 apr 2008`Ruby2100.0237
david_it21`19 apr 2008`Ruby1500.0241
stasg7`25 nov 2009`C++300.0170
stasg7`25 nov 2009`C++200.0174
sylvandire`13 dec 2013`C++400.0177
gouthampb`10 sep 2008`C++100.0183
nphard`05 oct 2008`C++100.0183
pradeepr_ceg`20 jun 2006`C500.0286
NDAT`08 nov 2006`FPC100.0189
nt_d2`08 nov 2006`FPC300.0189
n2duc`18 dec 2006`FPC100.0289
NghDuc`09 oct 2006`FPC100.0193
nt_d2`17 sep 2006`FPC200.0193
 C++ 198 FPC 57 C 25 Java 20 Kylix 17 Ruby 2 Python 2 Lua 1 Perl 1
` >  >  >  >  >  >  >  >  >  > `

## What is the number (Part II)?

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 < 2000000.

Output. One line with M.

 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

 © acm.mipt DevGroupThe page was generated in 190ms