<PREV Problem:
NEXT>
Solved by 313 users: ...
UserDateAttemptTimeCMSC
david_it2119 apr 2008Ruby2000.0234 
david_it2119 apr 2008Ruby1900.0235 
david_it2119 apr 2008Ruby1800.0237 
david_it2119 apr 2008Ruby2100.0237 
david_it2119 apr 2008Ruby1500.0241 
stasg725 nov 2009C++300.0170 
stasg725 nov 2009C++200.0174 
sylvandire13 dec 2013C++400.0177 
gouthampb10 sep 2008C++100.0183 
nphard05 oct 2008C++100.0183 
pradeepr_ceg20 jun 2006C500.0286 
NDAT08 nov 2006FPC100.0189 
nt_d208 nov 2006FPC300.0189 
n2duc18 dec 2006FPC100.0289 
NghDuc09 oct 2006FPC100.0193 
nt_d217 sep 2006FPC200.0193 
Languages
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

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


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

SW soft NIX
ID = 3.226.248.180