Модуль: Жадные алгоритмы


Задача

4 /9


Пеши на конкурсе рыболовов

Задача

Пеши сегодня участвует в соревновании по рыбалке с достаточно занимательными правилами.
Рыбалка проходит в несколько раундов. Каждый, кто не успевает выловить достаточно рыб за отведенное время, выбывает. Остальные проходят в следующий раунд. Игра длится до тех пор, пока не останется один участник.
После каждого раунда, который Пеши успешно проходит, если у него оставалось s соперников на начало этого раунда и из них t выбыли в этом же самом раунде, то Пеши получает \({t \over s}\) долларов. Соответственно в следующем раунде у него уже будет s - t соперников.
Пеши задумался, чему равен наибольший приз, который он может получить в лучшем случае. Однако соревнование начинается достаточно скоро, и у него нет времени, чтобы посчитать. Может быть вы сможете?

Входные данные:
Единственная строка содержит целое число n (1 ≤ n ≤ 105), обозначающее число соперников Пеши.

Выходные данные:
Выведите наибольший возможный приз (в долларах), который может получить Пеши.
Ваш ответ будет засчитан, если его абсолютная или относительная погрешность будет не более 10−4. Иначе говоря, если ваш ответ это a, а ответ жюри b, то должно выполняться \({|a - b| \over max(1,b)} \le 10^{-4}\)  .

Примеры:
 
Входные данные Выходные данные
1 1.000000000000
2 1.500000000000