Řešení úloh ústředního kola 43. ročníku
P-III-1
Daná posloupnost N čísel je tvořena čísly a
1,a
2,...,a
N. Pro
každé číslo a
i můžeme určit hodnotu e
i udávající, o kolik více
bylo kladných čísel než záporných v počátečním úseku posloupnosti
a
1a
2...a
i. Pokud bylo v úseku a
1a
2...a
i
více záporných čísel,
bude mít e
i zápornou hodnotu. Pro každé pořadové číslo prvku i od
1 do N bude jistě platit nerovnost -i<=e
i<=i.
Každý vybalancovaný úsek posloupnosti
apap+1...aq-1aq je
charakterizován tím, že jeho krajní prvky ap-1, aq mají stejnou
tuto e-hodnotu, tj. ep-1=eq. Pokud tedy určíme všechny hodnoty
ei pro i od 1 do N, stačí mezi nimi nalézt dvojici stejných hodnot
co nejvíce od sebe vzdálených. Jejich vzdálenost od sebe
v posloupnosti pak přímo udává délku maximálního vybalancovaného
úseku. Jestliže neexistuje žádná dvojice stejných hodnot
ep-1=eq, jsou všechna čísla v posloupnosti kladná nebo všechna
záporná a daná posloupnost tedy neobsahuje žádný vybalancovaný
úsek.
Výpočet hodnot ei pro všechna i od 1 do N je velmi snadný.
Stačí jednou projít celou posloupností a za každé kladné, resp.
záporné číslo přičíst k průběžně počítané hodnotě +1, resp. -1.
Formálně zapsáno, položíme
e0=0
a potom:
- ei= ei-1+ 1 když ai>0
- ei= ei-1 když ai=0
- ei= ei-1- 1 když ai<0
Bylo by možné uložit si všechny hodnoty e
i do pole a v něm
pak vyhledávat dvojice stejných hodnot. Takový postup je ale
zbytečně pomalý. Lepší je ukládat si do pomocného pole F pro
každou dosaženou e-hodnotu M nejmenší takové p, že e
p=M. Vzhledem
k podmínce -i<=e
i<=i musí být toto pole indexováno od -N do N.
Využívat se z něj bude přitom pouze jistý souvislý úsek s indexy
od X do Y. Během čtení a zpracovávání prvků posloupnosti se
velikost tohoto úseku může zvětšovat.
Na začátku výpočtu položíme X=0, Y=0 a F[0]=0. Postupně
budeme číst čísla tvořící danou posloupnost a zpracovávat je. Po
přečtení čísla ai nejprve spočítáme hodnotu ei podle výše
uvedeného předpisu (na základě zaznamenané předchozí hodnoty
ei-1). Jestliže ei<X, musí být nutně ei=X-1. Zmenšíme tedy
X o 1 a zaznamenáme výskyt nové e-hodnoty F[X]=i. Podobně pro
ei>Y zvětšíme Y o 1 a uložíme hodnotu F[Y]=i. Je-li
ei z intervalu , stejná e-hodnota byla již nalezena někdy
dříve, a sice poprvé při zpracování prvku s pořadím F[ei]. To
znamená, že nejdelší vybalancovaný úsek končící prvkem ai má
délku i-F[ei]. Nyní zbývá jen porovnat tuto délku s průběžně
ukládaným maximem z délek nalezených vybalancovaných úseků.
Popsaný algoritmus je jistě konečný, jediný jeho cyklus se
provádí pouze jednou pro každé číslo dané posloupnosti. Má tedy
lineární časovou složitost. Správnost algoritmu vyplývá ze
skutečnosti, že systematicky prozkoumáme maximální vybalancované
úseky končící každým z prvků posloupnosti a z jejich délek
vybereme maximum.
program Vybalancovany_Usek;
const MaxN=1000;
var N:integer; {počet čísel v posloupnosti}
A:integer; {právě zpracovávané číslo}
E:integer; {e-hodnota zpracovávaného čísla}
I:integer; {pořadí zpracovávaného čísla}
X,Y:integer; {meze rozsahu nalezených e-hodnot}
F:array[-MaxN..MaxN] of integer;
{indexy prvních výskytů jednotlivých e-hodnot}
Max:integer; {délka max. vybalancovaného úseku}
begin
X:=0; Y:=0;
F[0]:=0;
E:=0;
Max:=0;
for I:=1 to N do
begin
read(A); {další zpracovávané číslo}
if A>0 then E:=E+1 {spočítání jeho e-hodnoty}
else if A<0 then E:=E-1;
if E<X then {nová nejmenší e-hodnota}
begin X:=X-1; F[X]:=I end
else if E>Y then {nová největší e-hodnota}
begin Y:=Y+1; F[Y]:=I end
else {další výskyt stejné e-hodnoty}
if I-F[E]>Max then Max:=I-F[E]
end;
if Max=0 then
writeln('Vybalancovany usek neexistuje!')
else
writeln('Delka maximalniho vybalancovaneho useku: ',Max)
end.
P-III-2
Úloha P-III-2 je jednou z klasických úloh teorie grafů.
Silniční síť představuje souvislý neorientovaný graf, v němž
vrcholy grafu odpovídají městům a hrany grafu silnicím.
Nepostradatelné silnice, tak jak jsou definovány v zadání úlohy,
odpovídají v teorii grafů zvláštním hranám zvaným mosty. Úkolem
tedy je nalézt v daném grafu všechny mosty.
Algoritmus řešení je založen na procházení zadaným grafem do
hloubky. Při procházení bude každý vrchol grafu navštíven právě
jednou. Způsob procházení lze znázornit stromem. Kořenem stromu
procházení je vrchol, z něhož bylo procházení zahájeno. Za kořen
můžeme zvolit libovolný vrchol grafu. Bezprostředními následníky
některého vrcholu V jsou všechny ty vrcholy, do nichž
prohledávání z vrcholu V bezprostředně pokračovalo. Protože
zadaný graf je souvislý, budou ve stromu procházení obsaženy
všechny vrcholy původního grafu (města). Ze všech hran (silnic)
budou ve stromě procházení obsaženy jen ty, které nás v průběhu
procházení dovedly do nového, doposud nenavštíveného vrcholu.
Představme si, že do stromu procházení dokreslíme zelenou
barvou všechny zbývající hrany grafu. To jsou tedy takové,
kterými průchod do hloubky nepokračoval. Jinak řečeno, v průběhu
procházení tyto silnice vedly z právě procházeného města do
jiného, již dříve navštíveného města. Doplněný strom tedy bude
izomorfní s původním grafem.
Nyní vyslovíme jedno pomocné tvrzení: Oba koncové vrcholy
každé zelené hrany leží na téže větvi stromu procházení. Tvrzení
snadno dokážeme sporem. Předpokládejme, že by některá zelená
silnice spojovala dvě města A a B, která neleží na jedné větvi
stromu procházení. Označme je tak, že během průchodu bylo
A poprvé navštíveno dříve než B. Město B jistě neleží v podstromu
procházení s kořenem A (jinak by A a B ležela na téže větvi). Pro
postup procházení to znamená, že nejprve bylo (případně
několikrát) navštíveno město A a teprve potom (případně
několikrát) navštíveno město B. Všimněme si okamžiku během
procházení, kdy jsme město A navštívili naposledy. To bylo
v situaci, kdy jsme se z něho vraceli zpět (kdybychom šli vpřed,
museli bychom do A přijít ještě na zpáteční cestě). V tomto
okamžiku jsme se ale nezachovali správně podle algoritmu
procházení grafem do hloubky: vraceli jsme se zpět, a přitom jsme
ještě měli projít silnicí AB, protože ta vedla do tehdy ještě
nenavštíveného města B.
K tomu, aby hrana byla mostem, je nutné a stačí, aby se
jejím odstraněním oddělil podstrom ve stromu procházení, který
nebude dostupný ani po některé zelené hraně. Podle předchozího
tvrzení by takové spojení zelenou hranou muselo vést do vyšší
vrstvy ve stromě procházení.
Na základě provedených úvah již lze zformulovat algoritmus.
Zadaný graf budeme procházet do hloubky, začít můžeme libovolným
vrcholem (např. vrcholem číslo 1). Během procházení si budeme
u každého vrcholu M pamatovat jeho hloubku ve stromě procházení
HM. Kořen stromu procházení bude mít hloubku 0. Postupně během
průchodu budeme pro každý procházený vrchol M určovat číslo
ZM definované takto: ZM je minimum z HM a
z hloubek koncových měst
všech zelených silnic, které vycházejí z vrcholů v podstromu
s kořenem M. ZM je tedy číslo nejvyšší hladiny ve stromě
procházení, do které vede přímé spojení zelenou silnicí
z nějakého města v podstromu s kořenem M. Přitom si všímáme jen
hladin nad vrcholem M. Nastane-li pro některý vrchol M nerovnost
ZM < HM, existuje zelená silnice, která
spojuje podstrom
s kořenem ve vrcholu M se zbytkem grafu.
Je-li ZM = HM, je
silnice, po níž jsme do M během procházení přišli, mostem.
Zbývá ukázat, jak budeme počítat hodnoty HM a
ZM pro vrchol M. Hodnotu HM určíme
snadno při prvním vstupu do vrcholu M během
procházení grafem - je o 1 větší než odpovídající hodnota HX
vrcholu X, z něhož do M přicházíme. Stanovení hodnoty ZM je
o něco obtížnější.
Hodnota ZM je rovna minimu z hodnoty HM
a z hodnot Zi všech vrcholů ležících v podstromu s kořenem ve
vrcholu M. Při prvním vstupu do vrcholu M můžeme tudíž
inicializovat hodnotu ZM již známou
hodnotou HM a pak ji během
procházení podstromu vrcholu M budeme případně zmenšovat,
bude-li to možné. Při každém dalším příchodu do vrcholu M (tj.
při návratu z nějakého následníka vrcholu M) lze hodnotu ZM
snížit na Z-hodnotu tohoto následníka. K dalšímu snížení ZM mohou
přispět hrany, které vedou z vrcholu M do již navštívených uzlů
a po nichž se tudíž při průchodu nepostupuje. Hodnotu ZM můžeme
snížit na H-hodnotu koncových vrcholů těchto zelených hran.
Definitivní hodnotu ZM získáme až při posledním opuštění vrcholu
M.
Složitost celého algoritmu je dána složitostí průchodu
grafem do hloubky. Ostatní výpočty spojené s určováním hodnot HM
a ZM mají konstantní časové nároky. Časová složitost programu pro
průchod grafem do hloubky závisí na vhodné volbě vnitřní
reprezentace grafu. Při vhodně zvolené reprezentaci (viz uvedená
programová ukázka) je přímo úměrná počtu hran v grafu, tj. je
řádu n2, kde n je počet vrcholů grafu.
program Mosty (input,output);
{ Format ocekavanych vstupnich dat - zadani grafu:
- sousedi kazdeho vrcholu vzdy na jednom radku ve tvaru
<cislo-vrcholu> <cislo-souseda1> <cislo-souseda2> ...
- vrcholy musi byt ocislovany od jedne po jedne a v tomto
poradi musi byt take radky na vstupu zadany
- kazda hrana se tedy uvadi dvakrat (na radcich pro jeden
a pro druhy jeji koncovy vrchol)
- program pro jednoduchost netestuje spravnost zadanych
vstupnich dat (nebylo by tezke testy doplnit) }
const
MaxPocetMest = 40;
MaxPocetSilnic = 200;
type
Mesto = 1..MaxPocetMest+1; { fiktivni mesto na konci }
Silnice = 1..MaxPocetSilnic;
var
GMesto : array [Mesto] of record
Spoje : Silnice;
Hloubka : integer;
Projito : Boolean;
end;
GSilnice : array [Silnice] of Mesto;
{ pole GMesto a GSilnice predstavuji vnitrni ulozeni grafu
- ke kazdemu vrcholu je v poli GSilnice ulozen seznam
jeho sousedu, polozka Spoje v GMesto urcuje, kde presne
jsou ulozeni sousedi kazdeho konkretniho vrcholu
- viz uvodni komentar o tvaru vstupnich dat a procedura
NactiGraf }
PocetMest : 0..MaxPocetMest;
PocetSilnic : 0..MaxPocetSilnic;
F:integer; { pomocna promenna - je potrebna pro spravne
volani procedury Pruchod v hlavnim programu }
procedure NactiGraf;
{ nacteni vstupnich dat - zadani zkoumaneho grafu }
var dummy:integer;
begin
PocetMest:=0;
PocetSilnic:=1;
repeat
PocetMest:=PocetMest+1;
read(dummy); { cislo mesta - nevyuziva se }
GMesto[PocetMest].Spoje:=PocetSilnic;
while not eoln do
begin
read(GSilnice[PocetSilnic]);
PocetSilnic:=PocetSilnic+1;
end;
readln;
until eof;
GMesto[PocetMest+1].Spoje:=PocetSilnic;
end;
function min(X,Y:integer):integer;
{ pomocna procedura - minimum ze dvou celych cisel }
begin
if X<Y then min:=X else min:=Y;
end;
procedure PisMost(odkud,kam : Mesto);
{ vypise, ze z mesta "odkud" do mesta "kam" vede most }
begin
writeln('Most z ',odkud,' do ',kam,'.');
end;
procedure PredPruchodem;
{ oznaci vsechna mesta za dosud neprojita - nutne! }
var i:Mesto;
begin
for i:=1 to PocetMest do GMesto[i].Projito := false;
end;
procedure Pruchod(Start: Mesto; hl:integer; var Z: integer);
{ Projde odpovidajici cast grafu do hloubky.
Zacina ve meste Start, jeho hloubka je hl, spocita pro nej
hodnotu Z (viz text). }
var Nasl : Mesto;
S : Silnice;
pomZ : integer;
begin
GMesto[Start].Projito := true; { vrchol navstiven }
GMesto[Start].Hloubka := hl; { ma hloubku hl }
Z := hl; { prozatimni hodnota Z }
for S:=GMesto[Start].Spoje to GMesto[Start+1].Spoje-1 do
begin
Nasl := GSilnice[S]; { mesto dostupne po silnici S }
if GMesto[Nasl].Projito then
begin { nepocitat silnici, po niz jsme prisli! }
if GMesto[Nasl].Hloubka+1 <> hl then
{ zelena silnice, bud nahoru, nebo dolu }
Z := min(Z,GMesto[Nasl].Hloubka)
{ pokud vede zelena silnice nahoru, snizime
hodnotu Z v nasem uzlu }
end
else
begin
Pruchod(Nasl,hl+1,pomZ);
if hl+1 = pomZ then
PisMost(Start,Nasl); { nalezen most v grafu }
Z := min(Z,pomZ); { pripadne snizeni hodnoty Z }
end;
end;
end;
begin
NactiGraf;
PredPruchodem;
Pruchod(1,0,F);
{ vzdy je F=0 }
end.
P-III-3
- Budeme systematicky zkoumat možnosti vítězného tahu
v situacích s malým počtem zápalek zbývajících na hromádce.
Přitom vždy musíme rozlišit, zda hráč, který je na tahu, dosud
odebral sudý nebo lichý počet zápalek. Výsledky pozorování
zapíšeme do přehledné tabulky. Čísla v tabulce udávají, jak
vypadá správný vítězný tah. Pokud vítězný tah v dané pozici
neexistuje,je v tabulce zapsána pomlčka.
počet zápalek zbývajících na hromádce
| hráč na tahu již odebral |
sudý počet | lichý počet |
1 | - | 1 |
2 | 2 | 1 |
3 | 2 | 3 |
4 | - | 3 |
5 | 1 | - |
6 | 1 | 2 |
7 | 3 | 2 |
8 | 3 | - |
9 | - | 1 |
10 | 2 | 1 |
11 | 2 | 3 |
První tři řádky tabulky pro počty zápalek 1, 2 a 3 jsme
získali prozkoumáním všech možností povoleného tahu. Další řádky
tabulky již zaplňujeme mechanicky, vždy na základě znalosti tří
bezprostředně předcházejících řádků. Hráč totiž může svým tahem
odebrat 1, 2 nebo 3 zápalky a tím se situace ve hře převede na
situaci popsanou právě jedním ze tří předcházejících řádků.
Vítězný tah existuje tehdy, jestliže přivede soupeře do situace,
v níž on naopak žádný vítězný tah nemá (v tabulce je pomlčka).
Při zaplňování tabulky využíváme skutečnost, že víme, zda soupeř
dosud odebral sudý nebo lichý počet (to je dáno paritou našeho
počtu zápalek a počtu zápalek zbývajících na hromádce, celkem
všech zápalek je lichý počet).
Po zaplnění 11 řádků tabulky zjistíme, že se hodnoty
v tabulce začínají opakovat s periodou 8. Vzhledem k tomu, že se
zopakovaly tři po sobě jdoucí řádky (řádky 9, 10 a 11 jsou shodné
s řádky 1, 2 a 3) a že každý další řádek tabulky sestrojujeme
vždy pouze na základě tří bezprostředně předcházejících řádků, je
v tuto chvíli jisté, že se obsah tabulky bude i nadále stále
opakovat s periodou 8.
Tím je úloha vyřešena a prvních 8 řádků uvedené tabulky
obsahuje přehledně sepsanou vítěznou strategii naší hry. Hráč na
tahu zjistí počet zbývajících zápalek modulo 8 a na základě této
hodnoty a parity počtu zápalek, které již sám odebral, určí
z tabulky, zda má zaručeno vítězství ve hře. Pokud ano, tabulka
udává počet zápalek, kolik má odebrat.
Počáteční počet všech zápalek N musí být lichý. Začínající
hráč nemá zatím žádnou odebranou zápalku, tzn. má sudý počet
(nula je sudé číslo). Z tabulky plyne, že na začátku hry má
začínající hráč zaručeno vítězství při dodržení popsané vítězné
strategie, je-li N tvaru 8k+3, 8k+5 nebo 8k+7. Pokud je N tvaru
8k+1, začínající hráč s dobře hrajícím soupeřem prohraje.
- Úlohu řešíme zcela stejným způsobem jako úlohu a). Opět
sestrojíme tabulku vítězné strategie:
počet zápalek zbývajících na hromádce
| hráč na tahu již odebral |
sudý počet | lichý počet |
1 | - | 1 |
2 | 2 | 1 |
3 | 2 | 3 |
4 | 4 | 3 |
5 | 4 | - |
6 | 1 | - |
7 | - | 1 |
8 | 2 | 1 |
9 | 2 | 3 |
10 | 4 | 3 |
Řádky se v tomto případě začínají opakovat s periodou délky
6. Ověřili jsme zopakovaní čtyř po sobě jdoucích řádků (řádky 7,
8, 9 a 10 jsou shodné s řádky 1, 2, 3 a 4), neboť každý řádek
závisí pouze na čtyřech svých předchůdcích. Stejnou úvahou jako
v úloze a) z toho plyne, že prvních 6 řádků zde uvedené tabulky
obsahuje úplnou vítěznou strategii hry.
Hráč začínající hru má zajištěno vítězství při dodržení
popsané vítězné strategie, je-li počáteční počet zápalek N tvaru
6k+3 nebo 6k+5. Pokud je N tvaru 6k+1, začínající hráč s dobře
hrajícím soupeřem prohraje.
P-III-4
- Hledaný stroj neexistuje. Důvodem je nejednoznačnost zápisu
čísel (vedoucí nuly) a zároveň striktní požadavek na synchronní
čtení obou vstupů. Představte si porovnávání dvou zápisů téhož
čísla, přičemž jeden obsahuje k cifer, druhý obsahuje před
zápisem dalších k nul (tedy celkem 2k cifer). Po přečtení prvních
k znaků stroj již dočte první vstup do konce, z druhého však
nepřečetl jedinou významnou cifru. To znamená, že si pro úspěšné
porovnávání musí být schopen zapamatovat hodnotu celého kratšího
operandu. To v paměti konečné velikosti není možné.
- Porovnávání je obdobné porovnávání v poziční soustavě
o kladném základu. Jen je třeba si uvědomit, že vyšší cifry
v sudých řádech představují vyšší hodnotu, zatímco vyšší cifry
v lichých řádech nižší hodnotu čísla. Tedy například 11<01
v soustavě o základu (-2). Během porovnávání tedy sledujeme:
- která z přečtených částí prvního a druhého čísla je větší resp.
že obě čísla byla doposud stejná
- sudost/lichost právě zpracovávané pozice v zápisu čísel
Stroj tedy bude mít 6 stavů:
- N (sudá pozice - stejné zápisy)
- M (lichá pozice - stejné zápisy)
- A (sudá pozice - první číslo větší)
- B (lichá pozice - první číslo větší)
- C (sudá pozice - druhé číslo větší)
- D (lichá pozice - druhé číslo větší)
Počáteční stav je N, přechodová funkce následuje. Pro stav K není
definováno žádné přechodové pravidlo. Uvědomte si, že porovnávání
lze ukončit až po přečtení delšího ze vstupujících čísel.
stav | čtené symboly |
0 0 | 0 1 | 1 0 | 1 1 | 0 _ | 1 _ | _ 0 | _ 1 | _ _ |
N | M/_ | D/_ | B/_ | M/_ | M/_ | B/_ | M/_ | D/_ | K/S |
M | N/_ | A/_ | C/_ | N/_ | N/_ | C/_ | N/_ | A/_ | K/S |
A | B/_ | D/_ | B/_ | B/_ | B/_ | B/_ | B/_ | D/_ | K/P |
B | A/_ | A/_ | C/_ | A/_ | A/_ | C/_ | A/_ | A/_ | K/P |
C | D/_ | D/_ | B/_ | D/_ | D/_ | B/_ | D/_ | D/_ | K/D |
D | C/_ | A/_ | C/_ | C/_ | C/_ | C/_ | C/_ | A/_ | K/D |
- Stroj neexistuje. Zdůvodnění je zcela analogické úloze
prvního kola P-I-4 c.
- Sčítání je podobné sčítání v pozičních soustavách o kladném
základu. Jen je třeba dát si pozor na přenosy. Kromě skutečnosti,
že přenos do vyššího řádu mění znaménko, je třeba mít na zřeteli,
že se přenos může projevit nejen v následujícím řádu, ale ve dvou
následujících řádech. Tomu je třeba věnovat pozornost na konci
sčítání - v situaci, kdy jsou oba operandy dočteny a vypisujeme
cifry, které přibyly v důsledku přenosu.
Přenos může nabývat tří hodnot: označme je 0,1,11 (to jsou
hodnoty, které je třeba přičíst k vyšším řádům ve výsledku).
Budou jim odpovídat stavy N,J,T. Stav K slouží pouze pro ukončení
výpočtu. Počátečním stavem je N.
stav | čtené symboly |
0 0 | 0 1 | 1 0 | 1 1 | 0 _ | 1 _ | _ 0 | _ 1 | _ _ |
N | N/0 | N/1 | N/1 | T/0 | N/0 | N/1 | N/0 | N/1 | K/_ |
J | N/1 | T/0 | T/0 | T/1 | N/1 | T/0 | N/1 | T/0 | K/1 |
T | J/1 | N/0 | N/0 | N/1 | J/1 | N/0 | J/1 | N/0 | J/1 |
- Při určování zbytků po celočíselném dělení záporných čísel se
někdy uvažují nezáporné zbytky a někdy záporné (např. (-5)/3 dává
zbytek 1 nebo -2). Je možné zvolit si kteroukoli z obou možností,
my si zvolíme první z nich. Uvědomme si, že všechny mocniny čísla
-2 dávají při dělení třemi zbytek 1. Jako kritérium dělitelnosti
třemi může proto posloužit dělitelnost třemi ciferného součtu
čísla. Navrhnout stroj, který zjistí, zda ciferný součet čísla je
dělitelný třemi, je snadné. Postačí čtyři stavy, z nichž stav
K je využit pouze pro ukončení výpočtu. Počáteční stav je N.
stav | čtený symbol |
0 | 1 | _ |
N | N/_ | J/_ | K/A |
J | J/_ | D/_ | K/N |
D | D/_ | N/_ | K/N |
- Hledaný stroj neexistuje. Tato skutečnost vypadá poněkud
paradoxně v souvislosti s kladným řešením bodu e. Určit zbytek
při celočíselném dělení je ovšem snazší činnost než určit podíl.
Předpokládejme, že stroj, který dělí třemi, existuje.
Uvažujme tyto dělence a jejich podíly při dělení třemi:
10000...0000011 / 3 = 0010101...010101
a 10000...0000110 / 3 = 1101010...101010.
Zápisy všech uvedených čísel obsahují (2k+3) cifer, k je
libovolné celé kladné číslo. V zápisu dělenců se opakují nuly,
v zápisu podílů se opakuje skupina 01 či 10. Výsledky výpočtů nad
uvedenými dvěma vstupy se liší již ve druhé číslici zpředu
(nepočítáme vedoucí nuly). Zda má být druhou platnou číslicí
jednička či nula však stroj zjistí až po přečtení posledních tří
cifer vstupujícího čísla. To znamená, že v okamžiku, kdy stroj
zapisuje druhou nenulovou cifru výsledku, má již přečten celý
vstup (případně až na poslední dvě cifry). Potom by měl ještě
vypsat zbytek výstupu. K tomu si ale musí pamatovat přinejmenším
počet cifer, které má do výsledku zapsat, na což mu pro
dostatečně dlouhé operandy konečná paměť nemůže stačit.