Девід Коперфілд відпочиває
Присвячується лектору другого дня Харківської Зимової Школи 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).
Вихідні дані
Єдине число, запомнене для переносу, при виконанні множення в один рядок.