eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дэвид Коперфилд отдыхает

Дэвид Коперфилд отдыхает

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Посящается лектору второго дня Харьковской Зимней Школы 2011 по программированию Дмитрию Жукову.

Когда Андрей внимательно слушал лекцию Дмитрия Жукова, в зале послышалась фраза “Бабочки Фурье”, от которой Андрей содрогнулся и задумался: "…на улице конец февраля и минус 25, когда же наконец наступит весна и появятся бабочки?" От мыслей о предстоящей весне, тепле и бабочках он перестал внимательно слушать лектора и так и не понял алгоритм Карацубы.

По приезде домой он спросил учителя:

А что это за бабочки Фурье?

­– Послушай, я тебе лучше расскажу о других бабочках, о которых мне рассказывал мой преподаватель, когда я был чуть постарше чем ты и учился в ВУЗе. Может быть они смогут тебе как-то помочь, когда ты будешь самостоятельно разбираться дома с лекцией Дмитрия Жукова…

Алгоритм расчитан на быстрое умножение в уме 2n-значных чисел. Запишем на доске два n-значных числа (понятно, что если одно из чисел короче – мы можем спереди дописать нужное нам количество не значущих нулей). Вспомним фразу: "С младших классов мы знаем табличку умножения". Что означает эта фраза с точки зрения программиста? А означает она то, что мы можем создать двумерный массив, куда занести табличку умножения для цифр от 0 до 9 и при выполнении дальнейших вычислений не умножать заново две цифры, а взять готовое число из памяти – мы ведь уже знаем табличку умножения!!!

Тогда правила для быстрого умножения n-значных чисел можно записать следующим образом:

­Для однозначных чисел правило называется I – мы умножаем две цифры одна над другой.

Для двузначных чисел правило называется IXI. Заметим, что все правила выполняются справа налево. Покажем, как это правило действует в сравнении с обычным умножением в столбик. Поэтому для начала приведём пример обычного умножения для чисел 25 и 37:

Теперь объясним, как мы можем обойтись без промежуточных строк, которые нам потом нужно складывать. Умножим (возьмём с таблички умножения!!!) две правые цифры 5 и 7 – выполним правое I. Последнюю цифру результата 5 запишем сразу в ответ, а остальные цифры (в данном случае только одна цифра 3) перенесём в следующий разряд. Теперь выполним X. Для этого сложим в уме 2∙7 и 3∙5 и прибавим перенос 3. Получим 14 + 15 + 3 = 32. Опять запишем в результат полученную последнюю цифру 2 и запомним перенос 3. Выполним левое I: 2∙3 = 6, прибавим к нему перенос 3 и запишем в результат 9. В итоге наша последовательность выполнения действий на доске будет иметь вид, как показано на рисунке ниже и слева.

Для трёхзначных чисел действует правило IXЖXI и так далее – на каждом этапе максимальная бабочка имеет на одну пару "крылышек" больше, чем предыдущая.

Ну как, Андрей, ты понял как теперь можно быстро умножать длинные числа?

О, конечно – сейчас реализую и испробую на задачке "Произведение".

Алгоритм Андрей реализовал, и задачку сдал, а вот теперь задачка для Вас: какое число было перенесено в алгоритме Андрея на k-том шагу?

Входные данные

В первых двух строках заданы исходные числа A и B (A, B10^10000), каждое в своей строке. В третьей строке задано число k (1k20001).

Выходные данные

Единственное число, запомненное для переноса, при выполнении умножения в одну строчку.

Пример

Входные данные #1
25
37
2
Выходные данные #1
3
Автор Анатолий Присяжнюк