УЧЕБНО - ТРЕНИРОВОЧНЫЕ СБОРЫ К IOI 2003 ДЕНЬ №5 Бактерии
Время на тест: - Тесты к задаче:Скачать Автор задачи: Метельский И.С.
Один раз в школе, в которой учится Петя Булочкин, вспыхнула эпидемия гриппа. «Как бы не заболеть!» - подумал тогда Петя. Он был очень хорошим мальчиком и любил ходить в школу. К сожалению, так как Петя часто ходил в школу, у него были серьезные проблемы со здоровьем, и, конечно, он заболел. Сидеть дома и болеть было скучно, и Петя все время думал над проблемой, которая появилась у него недавно – надо было как-то исправлять девятку по биологии.
Во время таких вот размышлений у Пети появилась гениальная идея – нужно исследовать рост популяции бактерий гриппа! Сказано – сделано. Для Пети не составило большого труда обнаружить закон роста бактерий: если в данный момент времени есть X бактерий, то через одну наносекунду их будет X+S(X), где S(X) – сумма цифр числа X. Например, если сейчас есть 1 бактерия, то через одну наносекунду будет 2 бактерии, а через девять наносекунд – 62 бактерии.
Для большей убедительности Петя решил построить график зависимости количества бактерий от прошедшего времени. Он исходит из предположения, что в момент времени 1 имеется 1 бактерия, и хочет узнать, сколько бактерий будет в момент времени N (время измеряется в наносекундах). Петя выбрал несколько значений N (которые будут соответствовать опорным точкам графика) и занес их в файлы с именами 1.in, 2.in, …, 15.in. Он хочет получить файлы с именами 1.out, 2.out, …, 15.out, причем файл I.in должен содержать число, равное количеству бактерий в момент времени N, где N – число, записанное в файле I.in. Помогите ему получить эти файлы!!!
Задание. Сформулируем задание более точно. Пусть F(i) – количество бактерий в момент времени i. Тогда F(1) = 1 и F(X) = F(X-1)+S(F(X-1)), X>1 (S(A) – сумма цифр числа A). По введенному числу M необходимо найти F(M).
Входные данные. Входной файл с именем I.in (1<=I<=15) будет содержать одно целое число M (1<=M<=1014).
Выходные данные. Выходной файл с именем I.out (1<=I<=15) должен содержать одно целое число F(M).
Замечание. В этой программе вы должны сдавать не программу, а только выходные файлы для тех входных файлов, которые вам будут даны.
Пример.
0.in
6
0.out
23
Замечание.
Баллы, которые начисляются за правильный ответ на каждый из тестов, указаны в следующей таблице: