Девід Коперфілд відпочиває

Присвячується лектору другого дня Харківської зимової школи 2011 з програмування, Дмитру Жукову.

Поки Андрій уважно слухав лекцію Дмитра Жукова, залунала фраза «Фур'є-метелики». Андрія пробігли мурашки, і він подумав: «...кінець лютого, мінус $25$ градусів, коли вже нарешті прийде весна й з'являться метелики?» Замріяний про весну, тепло і метеликів, він перестав уважно слухати лектора й пропустив пояснення алгоритму Карацуби.

Вдома він спитав у свого вчителя:

– Що це за Фур'є-метелики?

– Давай я розповім тобі про інший тип метеликів, про який мені розповів мій учитель, коли я був трохи старшим за тебе й навчався в університеті. Можливо, вони допоможуть тобі зрозуміти лекцію Дмитра Жукова, коли ти подивишся її вдома...

Цей алгоритм призначений для швидкого усного множення $2$ $n$-значних чисел. Запиши на дошці два $n$-значних числа (якщо одне з чисел коротше, попереду можна дописати нулі, щоб обидва стали однакової довжини). Згадай фразу: "З молодших класів знаємо таблицю множення". З точки зору програміста це означає, що можна створити двовимірний масив для таблиці множення цифр від $0$ до $9$, і надалі просто брати наперед обчислене значення, замість кожного разу множити дві цифри – адже таблицю ми вже знаємо!

Правила для швидкого множення $n$-значних чисел такі:

Для однозначних чисел правило I: перемножити дві цифри, які стоять одна над одною.

Для двозначних чисел правило IXI. Зверни увагу, що всі правила виконуються справа наліво. Продемонструємо, як працює це правило в порівнянні зі звичайним множенням «у стовпчик». Для початку ось звичне множення для чисел $25$ та $37$:

Тепер пояснимо, як можна не писати проміжні рядки, які зазвичай треба додавати. Перемнож (вибери з таблиці!) праві цифри $5$ та $7$ — це праве I. Запиши останню цифру $5$ прямо у відповідь, а решту цифр (тут – просто $3$) перенеси в пам'яті (це перенос) для наступного розряду. Тепер виконай X: подумки склади 2 \cdot 7 і 3 \cdot 5 та додай перенос $3$, і отримаєш 14 + 15 + 3 = 32. Знову запиши останню цифру $2$ в результат, перенос $3$ залиш у пам'яті. Тепер виконай ліве I: 2 \cdot 3 = 6, додай перенос $3$, отримаєш $9$ у відповідь. У результаті послідовність дій на дошці показана нижче й ліворуч.

Для трицифрових чисел правило IXЖXI, і так далі — на кожному кроці у найбільшого метелика з'являється ще одна пара «крилець» порівняно з попереднім.

– Ну що, Андрію, тепер ти зрозумів, як швидко множити довгі числа?

– О, звісно — я реалізую це й випробую на задачі "Добуток".

Андрій реалізував алгоритм і розв'язав задачу, але тепер питання для тебе: яке число було перенесено при $k$-му кроці в алгоритмі Андрія?