<PREV Problem:
NEXT>
Solved by 781 users: ...
UserDateAttemptTimeCMSC
david_it2119 apr 2008Ruby1500.0234 
david_it2119 apr 2008Ruby1400.0235 
barlukov19 dec 2009Kylix100.0141 
david_it2119 apr 2008Ruby1200.0241 
david_it2119 apr 2008Ruby1100.0244 
david_it2119 apr 2008Ruby1000.0247 
stasg723 nov 2009C++900.0175 
JohnJones_00111 sep 2006Python300.0775 
sylvandire15 jan 2014C++100.0177 
pradeepr_ceg20 jun 2006C600.0182 
gouthampb10 sep 2008C++600.0183 
nphard05 oct 2008C++100.0283 
evg28106 jul 2009Python1400.5483 
Kopyrin_37.511 nov 2013Ruby445.2583 
stasg723 nov 2009C++800.0188 
Languages
C++
406
FPC
178
C
109
Java
45
Kylix
43
Ruby
8
Python
7
Lua
2
Haskell
1
Scheme
1
Perl
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 210ms

SW soft NIX
ID = 54.224.197.86