Дэвид Коперфилд отдыхает
Посящается лектору второго дня Харьковской Зимней Школы 2011 по программированию Дмитрию Жукову.
Когда Андрей внимательно слушал лекцию Дмитрия Жукова, в зале послышалась фраза “Бабочки Фурье”, от которой Андрей содрогнулся и задумался: "…на улице конец февраля и минус 25, когда же наконец наступит весна и появятся бабочки?" От мыслей о предстоящей весне, тепле и бабочках он перестал внимательно слушать лектора и так и не понял алгоритм Карацубы.
По приезде домой он спросил учителя:
– А что это за бабочки Фурье?
– Послушай, я тебе лучше расскажу о других бабочках, о которых мне рассказывал мой преподаватель, когда я был чуть постарше чем ты и учился в ВУЗе. Может быть они смогут тебе как-то помочь, когда ты будешь самостоятельно разбираться дома с лекцией Дмитрия Жукова…
Алгоритм расчитан на быстрое умножение в уме 2-х n-значных чисел. Запишем на доске два 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, B ≤ 10^10000), каждое в своей строке. В третьей строке задано число k (1 ≤ k ≤ 20001).
Выходные данные
Единственное число, запомненное для переноса, при выполнении умножения в одну строчку.