Řešení úloh oblastního kola 43. ročníku
P-II-1
Úloha je zobecněním úlohy P-I-1 z domácího kola. Postup
řešení je zcela analogický, potřebujeme pouze trochu složitější
průběžnou evidenci informací o dané posloupnosti čísel.
V zadání úlohy je stanoveno, že neznáme žádné předběžné
omezení hodnoty N a že N může být vysoké. Tato skutečnost nám
zakazuje použít v řešení úlohy pole, do něhož bychom si uložili
všechna čísla posloupnosti. Podobné pole by také bylo naprosto
zbytečné, k vyřešení úlohy nám bude stačit paměťový prostor
úměrný hodnotě K (nezávislý na N), tzn. vzhledem k uvedenému
omezení přípustných hodnot K vlastně prostor konstantní
velikosti. Optimální algoritmus řešení, který zde uvedeme, má
lineární časovou složitost. Lepší řešení nemůže existovat, neboť
každé z daných N čísel je třeba jednou přečíst a zpracovat.
Postup řešení úlohy je následující. Postupně budeme číst za
vstupu jednotlivá čísla tvořící zadanou posloupnost a budeme je
vyhodnocovat takovým způsobem, aby ve vhodně zvolené sadě
pomocných proměnných byly stále aktuálně uloženy správné údaje
charakterizující již přečtenou část vstupní posloupnosti čísel.
Důležité je průběžně si udržovat informace o právě zkoumaném
K-hladkém úseku: kde začíná, jaké hodnoty čísel obsahuje
a hlavně, na kterém místě v posloupnosti se naposledy vyskytla
každá z těchto hodnot. Pro uložení poslední uvedené informace
potřebujeme pole velikosti K+1, neboť každý K-hladký úsek může
obsahovat nejvýše K+1 různých hodnot. Údaje z tohoto pole jsou
důležité proto, že se K-hladké úseky mohou částečně překrývat.
Při ukončení zkoumaného úseku potom můžeme určit, kde začíná
další K-hladký úsek, aniž by bylo třeba nějak se vracet v dané
posloupnosti čísel. Evidence potřebných údajů může být
následující:
- CISLO - právě přečtené číslo
- INDEX - pořadové číslo právě přečteného čísla
- HLADKY - pořadové číslo, kde začíná právě sledovaný
K-hladký úsek
- MINHODNOTA - minimální hodnota čísel tvořících práv
sledovaný K-hladký úsek
- MAXHODNOTA - maximální hodnota čísel tvořících právě
sledovaný K-hladký úsek
- MAXUSEK - délka maximálního dosud nalezeného K-hladkého
úseku
- POSLEDNI - pole indexované od 0 do K, které obsahuje
pořadová čísla posledních výskytů všech hodnot
obsažených v právě sledovaném K-hladkém úseku:
- POSLEDNI[0] = poslední výskyt hodnoty MINHODNOTA
- POSLEDNI[MAXHODNOTA-MINHODNOTA] = poslední výskyt
hodnoty MAXHODNOTA
- POSLEDNI[X-MINHODNOTA] = poslední výskyt hodnoty X
Na začátku výpočtu přečteme první číslo posloupnosti
a dosadíme do proměnných vhodné počáteční hodnoty odpovídající
tomu, že zatím známe první hladký úsek délky 1 tvořený prvním
číslem posloupnosti. Po přečtení každého dalšího čísla
posloupnosti jsme schopni s využitím zaznamenaných údajů
aktualizovat hodnoty všech zde uvedených proměnných. Po
zpracování všech N čísel bude výsledek uložen v proměnné MAXUSEK.
Způsob zpracování každého čísla je již zřejmý z programu, kde
jsou uvedeny vysvětlující komentáře.
program Max_K_hladky_Usek;
const MaxK=10; {maximální možná hodnota K}
var N:integer; {počet čísel v posloupnosti}
K:0..MaxK; {stupeň "hladkosti"}
Cislo:integer; {přečtené číslo}
MinHodnota:integer; {minimální hodnota čísel
v aktuálním hladkém úseku}
MaxHodnota:integer; {maximální hodnota čísel
v aktuálním hladkém úseku}
NovaMezHodnota:integer; {nová max. nebo min. hodnota
v aktuálním hladkém úseku}
Index:integer; {index právě přečteného čísla}
Hladky:integer;
{index začátku aktuálního hladkého úseku}
Posledni:array[0..MaxK] of integer;
{index posledního výskytu jednotlivých hodnot
MinHodnota..MaxHodnota v aktuálním hladkém úseku}
Posun:integer; {posun hodnot v hladkém úseku}
MaxUsek:integer; {délka max. K-hladkého úseku}
I,J:integer;
begin
write('Počet čísel v posloupnosti N: ');
readln(N);
write('Stupeň hladkosti K: ');
readln(K);
read(Cislo); {první číslo dané posloupnosti}
Index:=1; Hladky:=1; MaxUsek:=1;
MinHodnota:=Cislo; MaxHodnota:=Cislo;
Posledni[0]:=1; {úsek tvořen jen prvním číslem}
for J:=2 to N do
begin
read(Cislo);
Index:=Index+1;
{rozlišíme 6 možností, jaké je další přečtené číslo
vzhledem k právě zkoumanému K-hladkému úseku:}
if (Cislo>=MinHodnota) and (Cislo<=MaxHodnota) then
{nové číslo prodlouží zkoumaný hladký úsek,
nezvětší se ani rozsah hodnot čísel v úseku}
Posledni[Cislo-MinHodnota]:=Index {zaznamenáme výskyt}
else if (Cislo>MaxHodnota) and (Cislo<=MinHodnota+K) then
{nové číslo prodlouží zkoumaný hladký úsek,
zvětší se jen rozsah hodnot čísel v úseku,
a to směrem k vyšším hodnotám}
begin
for I:=MaxHodnota-MinHodnota+1 to Cislo-MinHodnota-1 do
Posledni[I]:=0;
Posledni[Cislo-MinHodnota]:=Index; {zaznamenáme výskyt}
MaxHodnota:=Cislo {zvětší se MaxHodnota}
end
else if (Cislo<MinHodnota) and (Cislo>=MaxHodnota-K) then
{nové číslo prodlouží zkoumaný hladký úsek,
zvětší se jen rozsah hodnot čísel v úseku,
a to směrem k nižším hodnotám, je proto nutné
posunout údaje uložené v poli Posledni}
begin
for I:=MaxHodnota-MinHodnota downto 0 do
Posledni[I+MinHodnota-Cislo]:=Posledni[I];
for I:=1 to MinHodnota-Cislo-1 do
Posledni[I]:=0;
Posledni[0]:=Index; {zaznamenáme výskyt}
MinHodnota:=Cislo {zmenší se MinHodnota}
end
else if (Cislo>MaxHodnota+K) or (Cislo<MinHodnota-K) then
{nové číslo ukončuje dosud zkoumaný K-hladký úsek
a zahajuje nový úsek, tento nový úsek se s předchozím
nepřekrývá a bude tudíž zatím tvořen tímto jediným
číslem}
begin
if Index-Hladky>MaxUsek then {kontrola délky úseku}
MaxUsek:=Index-Hladky; {nalezen dosud nejdelší}
Hladky:=Index;
MinHodnota:=Cislo;
MaxHodnota:=Cislo;
Posledni[0]:=Index {úsek tvořen jedním číslem}
end
else if Cislo>MaxHodnota then
{jistě platí:
(Cislo>MinHodnota+K) and (Cislo<=MaxHodnota+K) }
{nové číslo ukončuje dosud zkoumaný K-hladký úsek
a zahajuje nový úsek, tento nový úsek se s předchozím
může částečně překrývat}
begin
if Index-Hladky>MaxUsek then {kontrola délky úseku}
MaxUsek:=Index-Hladky; {nalezen dosud nejdelší}
NovaMezHodnota:=Cislo-K; {nová min. hodnota}
for I:=0 to NovaMezHodnota-1-MinHodnota do
if Posledni[I]>Hladky then Hladky:=Posledni[I];
Hladky:=Hladky+1; {nový začátek K-hladkého úseku}
while (NovaMezHodnota<Cislo) and
(Posledni[NovaMezHodnota-MinHodnota]<Hladky) do
NovaMezHodnota:=NovaMezHodnota+1;
Posun:=NovaMezHodnota-MinHodnota;
{potřebný posun hodnot v poli Posledni}
for I:=Posun to MaxHodnota-MinHodnota do
if Posledni[I]<Hladky then
Posledni[I-Posun]:=0 {staré výskyty rušíme}
else
Posledni[I-Posun]:=Posledni[I]; {posun hodnoty}
for I:=MaxHodnota-NovaMezHodnota+1
to Cislo-NovaMezHodnota-1 do
Posledni[I]:=0;
Posledni[Cislo-NovaMezHodnota]:=Index; {zaznamenáme}
MinHodnota:=NovaMezHodnota;
MaxHodnota:=Cislo
end
else
{jistě platí:
(Cislo<MinHodnota) and (Cislo>=MinHodnota-K)
and (Cislo<MaxHodnota-K) }
{nové číslo ukončuje dosud zkoumaný K-hladký úsek
a zahajuje nový úsek, tento nový úsek se s předchozím
může částečně překrývat}
begin
if Index-Hladky>MaxUsek then
MaxUsek:=Index-Hladky;
NovaMezHodnota:=Cislo+K; {nová max. hodnota}
for I:=NovaMezHodnota+1-MinHodnota
to MaxHodnota-MinHodnota do
if Posledni[I]>Hladky then Hladky:=Posledni[I];
Hladky:=Hladky+1; {nový začátek K-hladkého úseku}
while (NovaMezHodnota>Cislo) and
(Posledni[NovaMezHodnota-MinHodnota]<Hladky) do
NovaMezHodnota:=NovaMezHodnota-1;
Posun:=MinHodnota-Cislo;
{potřebný posun hodnot v poli Posledni}
for I:=NovaMezHodnota-MinHodnota downto 0 do
if Posledni[I]<Hladky then
Posledni[I+Posun]:=0 {staré výskyty rušíme}
else
Posledni[I+Posun]:=Posledni[I]; {posun hodnoty}
for I:=1 to Posun-1 do
Posledni[I]:=0;
Posledni[0]:=Index; {zaznamenáme výskyt}
MinHodnota:=Cislo;
MaxHodnota:=NovaMezHodnota
end
end;
{ještě zbývá provést test, zda nejdelší K-hladký úsek nebyl
až na úplném konci posloupnosti:}
if Index-Hladky+1>MaxUsek then
MaxUsek:=Index-Hladky+1;
writeln(MaxUsek)
end.
Popsaný postup řešení je pro každá vstupní data jistě
konečný, neboť počet opakování jediného cyklu v algoritmu je
pevně určen délkou vstupní posloupnosti čísel. Odtud také plyne
již zmíněná lineární časová složitost algoritmu.
Správnost řešení vyplývá ze způsobu zpracování čísel.
V každé posloupnosti čísel jistě existuje pro libovolné K nějaký
K-hladký úsek, přinejmenším každé číslo samo tvoří jednoprvkový
K-hladký úsek. V konečné posloupnosti čísel je K-hladkých úseků
jenom konečně mnoho, takže některý (případně některé) z nich má
maximální délku. Tento úsek bude algoritmem jistě nalezen a jeho
délka bude uložena do výsledné proměnné MAXUSEK. V proměnné
MAXUSEK se totiž průběžné počítá maximum ze všech hodnot
INDEX-HLADKY před každým zvýšením hodnoty proměnné HLADKY, tj. ze
všech délek již neprodloužitelných K-hladkých úseků v dané
posloupnosti.
P-II-2
Úloha P-II-2 je drobnou modifikací jedné 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. Úkolem je zjistit, zda je doplněk daného grafu
bipartitní.
Postup řešení úlohy si můžeme názorně představit tak, že při
rozdělování měst do skupin budeme jednotlivá města "obarvovat"
dvěma barvami podle toho, do které skupiny bylo město zařazeno.
Městům zařazeným do první skupiny přiřadíme barvu 1 a městům
z druhé skupiny barvu -1. Na začátku výpočtu není žádné město
nijak obarveno, neboť dosud nebylo zařazeno do žádné ze skupin.
Celý proces rozdělování měst do skupin zahájíme tím, že
jedno libovolné město (zde město s číslem 1) obarvíme barvou 1.
Města, do kterých z tohoto města nevede přímá silnice, nesmí
podle zadání patřit do stejné skupiny. Obarvíme je proto barvou
-1. Podobně postupujeme stále dál. Obecně platí, že bylo-li
nějaké město zařazeno do jedné ze skupin, musí být všechna města,
která s ním nejsou spojena přímou silnicí, zařazena do opačné
skupiny. Přitom musíme průběžně kontrolovat, zda nedojde ke
konfliktu. Konflikt nastane tehdy, potřebujeme-li nějaké již
obarvené město obarvit opačnou barvou. V takovém případě
rozdělení měst do skupin neexistuje a výpočet ihned ukončíme.
Jinak pokračujeme v obarvování měst tak dlouho, dokud jsme nuceni
obarvovat další města (vlastně jako důsledek počátečního obarvení
prvního města). Jestliže se tento proces zastaví a přitom ještě
existují neobarvená města, můžeme jedno libovolné z nich (zde to
s nejmenším číslem) obarvit libovolnou barvou (zde barvou 1)
a pokračujeme pak v obarvování stejným způsobem. Celé rozdělování
měst skončí ve chvíli, kdy jsou všechna města obarvena
a zkontrolována, zda jejich obarvení nezpůsobuje žádný konflikt
(obarvení měst pak určuje jedno možné rozdělení měst do skupin)
nebo když při obarvování dojde ke konfliktu (rozdělení měst
v takovém případě neexistuje).
Pro efektivní naprogramování uvedeného postupu je důležitá
vhodná volba datových struktur. Informace o existujících
silnicích uložíme do čtvercového pole A logických hodnot
velikosti N x N (tj. vytvoříme matici sousednosti zkoumaného
grafu). Pro evidenci obarvení měst, tj. zařazení měst do skupin,
použijeme jednorozměrné pole Barva indexované čísly měst od 1 do
N. Neobarvená města budou mít v tomto poli přiřazenu hodnotu 0,
obarvená pak hodnotu 1 nebo -1 podle zvolené barvy. Dále
potřebujeme udržovat si seznam čísel měst, která jsme již
obarvili, ale dosud jsme nezajistili, aby města, do kterých
nevede přímá silnice, patřila do opačné skupiny. Pro uložení
tohoto seznamu použijeme jednorozměrné pole Seznam o N prvcích.
Z uvedeného postupu již plyne správnost algoritmu. Postupem
obarvování je zajištěno, že se nikdy nemohou dostat do téže
skupiny dvě města, mezi nimiž nevede přímá silnice. Pokud tedy
nalezneme bez konfliktu obarvení všech měst, určuje toto obarvení
správné rozdělení měst do skupin. Naopak, konflikt nastane jedině
ve chvíli, kdy by již obarvené město mělo být zařazeno do opačné
skupiny, než kam bylo dříve zařazeno, tj. když rozdělení měst do
skupin neexistuje. Konečnost výpočtu je dána tím, že v každém
kroku je obarveno jedno město. Počet kroků výpočtu je tedy roven
nejvýše počtu všech měst N. Odtud plyne, že časová složitost
algoritmu je úměrná N2, neboť každý krok výpočtu představuje
provedení řádově N operací (jeden průchod přes všech N měst).
program Rozdeleni_Mest;
const MaxN=100; {maximální možný počet měst}
var A:array[1..MaxN,1..MaxN] of Boolean; {matice silnic}
Barva:array[1..MaxN] of -1..1; {rozdělení měst}
Seznam:array[1..MaxN] of 1..MaxN; {pracovní seznam měst}
Posledni:0..MaxN; {index posledního prvku seznamu}
N:integer; {počet měst}
Zarazena:integer; {počet měst zařazených do skupin}
Konflikt:Boolean; {města nelze rozdělit}
I,J:integer;
begin
{Vstup dat:}
write('Počet měst: ');
readln(N);
for I:=1 to N do
begin
for J:=1 to N do A[I,J]:=false;
Barva[I]:=0
end;
write('Seznam všech silnic');
writeln(' - každá je zadána dvojicí čísel měst ODKUD a KAM vede:');
while not eof do
begin
read(I,J);
A[I,J]:=true; A[J,I]:=true
end;
{Rozdělování měst:}
Seznam[1]:=1; {výchozí město}
Posledni:=1; {v seznamu zařazených je zatím samo}
Barva[1]:=1; {zařazeno do skupiny 1}
Zarazena:=1; {jedno město je zařazeno}
Konflikt:=false;
while (Posledni>0) and not Konflikt do
begin
I:=Seznam[Posledni];
Posledni:=Posledni-1;
for J:=1 to N do
if (J<>I) and not A[I,J] then
if Barva[J]=Barva[I] then
Konflikt:=true
else if Barva[J]=0 then
begin
Barva[J]:=-Barva[I];
Posledni:=Posledni+1;
Seznam[Posledni]:=J;
Zarazena:=Zarazena+1
end;
if (Posledni=0) and (not Konflikt) and (Zarazena<N) then
begin
{libovolné dosud nezařazené město můžeme zařadit
do kterékoliv skupiny -> první dosud nezařazené
dáme do skupiny 1}
J:=1;
while Barva[J]<>0 do J:=J+1;
Seznam[1]:=J; {nově zařazené město}
Posledni:=1; {v seznamu zařazených je nyní samo}
Barva[J]:=1; {zařazeno do skupiny 1}
Zarazena:=Zarazena+1; {další město je zařazeno}
end
end;
{Vyhodnocení procesu rozdělování měst:}
if Konflikt then
writeln('Rozdělení měst do dvou skupin neexistuje.')
else
begin
writeln('Rozdělení měst do dvou skupin je možné.');
writeln('Jedno takové přípustné rozdělení vypadá takto:');
write('1.skupina:');
for I:=1 to N do
if Barva[I]=1 then write(I:3);
writeln;
write('2.skupina:');
for I:=1 to N do
if Barva[I]=-1 then write(I:3);
writeln
end
end.
P-II-3
- Nejprve se pokusíme hlouběji proniknout do průběhu uvedené hry
tím, že budeme sledovat situaci pro malé počty zápalek zbývající
na hromádce:
- zbývá 0 hráč na tahu prohrává
- zbývá 1 hráč na tahu vyhrává (vezme 1)
- zbývá 2 hráč na tahu vyhrává (vezme 2)
- zbývá 3 hráč na tahu prohrává (odebráním 1 nebo 2 se
soupeř dostane do pozice s vyhrávajícím tahem)
- zbývá 4 hráč na tahu vyhrává (vezme 1 nebo 4)
- zbývá 5 hráč na tahu vyhrává (vezme 2)
- zbývá 6 hráč na tahu prohrává (odebráním 1, 2 nebo 4 se
soupeř dostane do pozice s vyhrávajícím tahem)
Po vyšetření dalších pozic zjistíme, že vyhrané a prohrané
pozice se pravidelně opakují (s periodou délky 3). Na základě
provedeného rozboru hry můžeme vyslovit následující hypotézu.
Je-li počet zápalek na hromádce N tvaru 3k, začínající hráč
nemůže proti dobrému soupeři vyhrát. Pro ostatní hodnoty N má
naopak začínající hráč jisté vítězství, bude-li se držet vítězné
strategie. Pro N tvaru 3k+1 bude brát 1 zápalku, pro N tvaru
3k+2 vezme 2 zápalky.
Správnost vyslovené hypotézy nyní dokážeme. Je-li počáteční
počet zápalek tvaru 3k+1 nebo 3k+2 a zahrajeme svůj tah podle
uvedené strategie, dostane se soupeř do situace, že je na tahu
a na hromádce je 3k zápalek. Ať zahraje jakkoliv, po jeho tahu
zbude na hromádce počet zápalek, který není dělitelný třemi, tj.
počet tvaru 3m+1 nebo 3m+2. Soupeř totiž musí odebrat počet
zápalek, který je mocninou 2, a žádná mocnina dvou není beze
zbytku dělitelná třemi. Nemůže tudíž svým tahem sebrat poslední
zápalku a my se po jeho tahu opět dostaneme do situace, v níž
použijeme vítězný tah podle uvedené strategie. Tak se situace
opakuje pro stále se zmenšující počet zápalek zbývajících na
hromádce. Po konečném počtu tahů budeme na tahu v pozici s 1 nebo
2 zápalkami na hromádce, což znamená již bezprostřední výhru.
Naopak, pro počáteční počet zápalek N tvaru 3k vede
jakýkoliv tah začínajícího hráče do pozice, v níž není počet
zápalek zbývajících na hromádce dělitelný třemi. Bude-li se pak
náš soupeř držet uvedené strategie, má jisté vítězství ve hře.
- Úlohu můžeme řešit zcela analogicky jako úlohu a). Místo
postupného zkoumání jednotlivých hodnot N je ovšem lepší nejprve
se trochu zamyslet nad paritou (tj. sudostí resp. lichostí) počtu
zápalek na hromádce. V jednom tahu se odebírá pokaždé počet
zápalek, který je mocninou tří, tedy vždy lichý počet. Po každém
tahu jednoho z hráčů se tudíž změní parita počtu zápalek
zbývajících na hromádce. Po konečně mnoha tazích se hromádka
zcela vyprázdní. Tohoto vítězného stavu dosáhne určitě ten hráč,
který je na tahu vždy, když zbývá na hromádce lichý počet
zápalek. Odtud již plyne následující závěr: Je-li počáteční počet
zápalek lichý, hru vyhraje začínající hráč, při sudém počtu
naopak zvítězí ten hráč, který hru nezahajuje. Přitom vůbec
nezáleží na tom, jaké počty zápalek hráči ve svých tazích
odebírají.
P-II-4
- Požadovaný stroj neexistuje. Zdůvodnění je stejné jako v úloze
prvního kola P-I-4 c).
- Čísla v doplňkovém kódu lze sčítat odzadu stejně jako celá
nezáporná čísla v poziční soustavě. V jednom kroku stroj přečte
z obou sledů po jedné cifře a zapíše jednu cifru do výsledku.
Pomocí vnitřních stavů si bude pamatovat přenos mezi řády. Je
však třeba vyřešit technické problémy. Jakmile jedno z čísel
skončí, musí stroj počítat stejně, jako by ve vstupním sledu
následovaly další cifry rovné naposledy čtené cifře. Jakmile
skončí oba sledy, je třeba vypsat ještě alespoň jednu cifru
výsledku (zkuste si sečíst 2k+2k).
Stroj si tedy musí pamatovat tyto informace:
- zda došlo k přenosu (P=přenos, B=bez přenosu)
- poslední čtenou cifru v prvním sledu (0 nebo 1)
- poslední čtenou cifru v druhém sledu (0 nebo 1)
Stavy stroje budou vlastně představovat trojice informací, celkem
jich bude osm. Označíme je B=(B,0,0), C=(B,0,1), D=(B,1,0),
Q=(P,0,1), R=(P,1,0), S=(P,1,1). Rozmyslete si, že do stavů
(B,1,1) a (P,0,0) se stroj nemůže nikdy dostat. Počáteční stav je
B, přechodová funkce je dána tabulkou. Pro stav K není přechodová
funkce definována.
| stav | čtené symboly |
| 0 0 | 0 1 | 1 0 | 1 1 | 0 _ | 1 _ | _ 0 | _ 1 | _ _ |
| B | B/0 | C/1 | D/1 | S/0 | B/0 | D/1 | B/0 | C/1 | K/0 |
| C | B/0 | C/1 | D/1 | S/0 | C/1 | S/0 | B/0 | C/1 | K/0 |
| D | B/0 | C/1 | D/1 | S/0 | B/0 | D/1 | D/1 | S/0 | K/0 |
| Q | B/1 | Q/0 | R/0 | S/1 | Q/0 | S/1 | B/1 | Q/0 | K/1 |
| R | B/1 | Q/0 | R/0 | S/1 | B/1 | R/0 | R/0 | S/1 | K/1 |
| S | B/1 | Q/0 | R/0 | S/1 | Q/0 | S/1 | R/0 | S/1 | K/1 |
- Řešme společně s úlohou d.
Obdobně jako v prvním kole sestrojíme konečný sekvenční
stroj, který bude vstupující číslo dělit třemi. Podíl zapíše do
výstupního sledu, zbytek po dělení bude dán stavem, v němž
výpočet skončí. Na rozdíl od úlohy v prvním kole odpadá technická
starost o případ, kdy by ve výsledku byly nadbytečné vedoucí nuly
nebo jedničky. Počátečním stavem je X.
| stav | čtený symbol |
| 0 | 1 | _ |
| X | N/_ | D/_ | - |
| N | N/0 | J/0 | - |
| J | D/0 | N/1 | - |
| D | J/1 | D/1 | - |