ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1831. Урок Цыфиркина

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Феофан, новый ученик Цыфиркина, оказался намного умнее и сообразительнее Митрофанушки. За первые три урока арифметики он уже научился складывать целые положительные числа в столбик — не очень быстро, зато без ошибок. Для этого Феофан использует следующий алгоритм.
  1. Феофан складывает числа поразрядно справа налево: сначала единицы, потом десятки и т.д.
  2. Феофан берёт пару цифр в очередном разряде и складывает их.
  3. Если происходит перенос единицы из предыдущего разряда, Феофан прибавляет её к полученной сумме.
  4. Он приписывает последнюю цифру суммы к ответу и, если необходимо, делает пометку о переносе единицы в следующий разряд.
  5. Если разряды закончились, а из последнего разряда есть перенос единицы, Феофан просто приписывает её слева к ответу.
Чтобы написать одну цифру или поставить пометку о переносе единицы, Феофану нужна одна секунда. Если хотя бы одно из складываемых чисел равно нулю или единице, то Феофан тратит на сложение одну секунду, а если оба числа больше единицы — две секунды. Однако, сложив два числа, Феофан запоминает результат сложения и впоследствии в случае надобности вспоминает его за одну секунду. Если Феофану потребуется вычислить a + b и до этого он уже вычислял b + a, то он также сможет использовать полученный ранее результат. К сожалению, к следующему уроку Феофан забывает все эти результаты и ему приходится запоминать их заново.
Например, на сложение чисел 526 и 625 Феофан тратит 12 секунд: четыре секунды — на запись цифр ответа, две секунды — на пометки о переносе, две секунды — на вычисление каждой из сумм 6 + 5 и 2 + 2 и по одной секунде на вычисление сумм 4 + 1 и 5 + 6 (поскольку в процессе сложения Феофан уже запомнил, что 6 + 5 = 11).
В начале очередного занятия Цыфиркин написал на доске два k-значных числа и дал Феофану задание сложить их. Каждое из этих чисел Цыфиркин выбрал равновероятно из множества положительных k-значных чисел без ведущих нулей. Найдите математическое ожидание времени, которое понадобится Феофану для сложения этих чисел.

Исходные данные

В единственной строке записано целое число k (1 ≤ k ≤ 5000).

Результат

Выведите ожидаемое время сложения двух положительных k-значных чисел с абсолютной или относительной погрешностью не более 10−6.

Пример

исходные данныерезультат
2
7.51530864
Автор задачи: Евгений Курпилянский (идея — Александр Ипатов)
Источник задачи: XV Открытый чемпионат Урала по спортивному программированию (апрель, 2011)