Devid Koperfild dincəlir

textit2011-ci ilin Xarkov Qış Məktəbinin proqramlaşdırma üzrə ikinci gününün lektoruna,

textbfDmitro Jukov

textit-a həsr olunur.

Andriy Dmitro Jukovun mühazirəsini diqqətlə dinləyərkən, zalda "Furye Kəpənəkləri" ifadəsi eşidildi. Bu, Andriyi titrətdi və düşündürdü: "

textit...artıq fevralın sonudur və mənfi

textbf25

textit dərəcədir, axı bahar nə vaxt gələcək və kəpənəklər nə vaxt görünəcək?" Bahar, istilik və kəpənəklər haqqında xəyallara dalan Andriy mühazirədən uzaqlaşdı və nəticədə Karatsuba alqoritminin izahını qaçırdı.

Evə qayıdanda o, müəllimindən soruşdu:

–

textitBəs bu Furye Kəpənəkləri nədir?

–

textitGəl, sənə fərqli bir kəpənək barədə danışım, bu barədə müəllimim mən universitetdə səndən azca böyük olanda danışmışdı. Ola bilsin, bu, evdə Dmitro Jukovun mühazirəsini oxuyarkən onu anlamana kömək edər...

Bu alqoritm

textbf2

textbfn-rəqəmli ədədlərin sürətli zehni vurulması üçün nəzərdə tutulub. Taxtada iki

textbfn-rəqəmli ədəd yazılır (əgər bir ədəd qısadırsa, başlanğıcda sıfırlar əlavə etməklə onların uzunluğunu bərabərləşdirmək olar). Unutma: "

textitAşağı siniflərdən vurma cədvəlini bilirik". Proqramçı baxımından bu o deməkdir ki,

textbf0-dan

textbf9-a kimi olan rəqəmlərin vurma cədvəli üçün ikiölçülü massiv qurmaq olar və sonrakı hesablamalarda hər dəfə iki rəqəmi vurmaq əvəzinə sadəcə artıq hesablanmış qiyməti götürürük – çünki cədvəli bilirik!

textbfn-rəqəmli ədədlərin sürətli vurulması qaydası belədir:

Birrəqəmli ədədlər üçün qayda

textbfI-dir: eyni mövqedə dayanan iki rəqəmi vur.

includegraphicshttps://static.e-olymp.com/content/59/59478eb6d63e259fa72725ae39549502447ebe12.jpg

İkirəqəmli ədədlər üçün qayda

textbfIXI-dir. Qeyd edək ki, bütün qaydalar sağdan sola yerinə yetirilir. Bu qaydanın adi sütunla vurma ilə necə işlədiyinə baxaq. Əvvəlcə

textbf25 və

textbf37 üçün adi vurmanı göstərək:

İndi izah edək ki, aralıq cəmləri necə keçmək olar. Ən sağdakı rəqəmləri -

textbf5 və

textbf7-ni vur (cədvəldən götür!) – bu sağdakı

textbfI-dir. Son rəqəm olan

textbf5-i cavaba yaz, digər hissəni (burada sadəcə

textbf3) növbəti mövqeyə ötür. Sonra

textbfX-i icra et: zehində

textbf2·7 və

textbf3·5-i topla, bir də ötürülən

textbf3-ü əlavə et, cəmi

textbf14 + 15 + 3 = 32. Yenə də son rəqəm olan

textbf2-ni yaz, və yadda vəziyyəti

textbf3-ü saxla. İndi sol

textbfI-ni et:

textbf2·3 = 6, üstünə vəziyyəti

textbf3 əlavə et və

textbf9-u nəticəyə yaz. Sonda taxtadakı əməliyyat ardıcıllığı aşağıda və soldakı kimidir.

includegraphicshttps://static.e-olymp.com/content/fb/fbd73e0cb02c34f039a73c555adaf0fc21fbd3a9.jpg

Üçrəqəmli ədədlər üçün qayda

textbfIXЖXI-dir və s. – hər mərhələdə ən böyük "kəpənək" əvvəlkindən bir cüt "qanad" artıq olur.

–

textitBəs indi, Andriy, uzun ədədləri necə tez vurmaq lazımdır, başa düşdün?

–

textitAy can, əlbəttə – onu reallaşdıracam və

href/problems/272Məhsul

textit tapşırığında yoxlayacam.

Andriy alqoritmi reallaşdırdı və tapşırığı həll etdi, indi isə sənə sual: Andriyin alqoritmində vurma zamanı

textbfk-cı addımda yadda nə qədər ötürülüb?

InputFile

İlk iki sətrdə başlanğıc ədədlər verilib:

textbfA və

textbfB (A, B \\leq 10^{10000}), hər biri öz sətrində. Üçüncü sətrdə

textbfk ədədi verilib (1 \\leq k \\leq 20001).

OutputFile

Vurma zamanı

textbfk-cı addımda ötürülən yeganə yadda qalan ədədi çap edin.