Matematická olympiáda – kategorie P

Řešení úloh oblastního kola 46. ročníku

P-II-1

 Pro analýzu této hry potřebujeme nalézt charakterizaci jednotlivých situací, která by určovala, jak sa daná situace liší od koncové, "uspořádané" situace. Vhodnou charakteristikou je například počet inverzí: dvojic figurek modrá(červená, kde modrá figurka je nalevo od červené. Je jasné, že počet inverzí koncové situace je 0 (neboť všechny červené figurky jsou nalevo od modrých), situace mmcmccm uvedená v zadaní má 3+3+2+0=8 inverzí. Maximální počet inverzí (n2) nastává v situaci mm...mcc...c (n modrých figurek následovaných n červenými). Když provedeme krok hry (obrácení pořadí 3 nebo 4 sousedních figurek), změníme jen vzájemné pořadí těchto 3(4) figurek a inverze mezi nimi a ostatními figurkami zůstanou zachované. Celkový počet inverzí se proto zmenší (příp. zvětší) nejvýše o 4, o čemž se můžeme přesvědčit vyzkoušením všech 23+24 = 24 možných rozložení barev (změna o 4 nastává při kroku mmcc(r)ccmm, resp. ccmm(r)mmcc). Z těchto úvah je jasné, že:
Zkusme nyní nalézt takovou pozici v dané nekoncové situaci, v okolí které by sa dal provést vhodný krok. Dobrým kandidátem je pozice s červenou figurkou, nalevo od níž je modrá figurka. Z implementačních důvodů si zvolíme nejlevější takovou pozici (p) a nazveme ji přechodem, dvojici figurek (mc) nazveme přechodovou dvojicí. Přechod znázorníme znakem | umístněným mezi znaky přechodové dvojice (m|c). Další diskuse se bude týkat barvy figurek stojících vedle přechodové dvojice. Rozlišíme 2 možnosti:
  1. nalevo od přechodové dvojice je červená figurka (příp. okraj (#) hracího plánu, t.j. p = 2)
  2. nalevo od přechodové dvojice je modrá figurka
Rozeberme nejdříve případ 1 (cm|c). Je-li napravo od přechodové dvojice červená figurka (případ 1.1, cm|cc), provedeme krok délky 3, který obrátí přechodovou dvojici a ještě figurku napravo od ní:
cm|cc -> cccM
#m|cc -> #ccM
Počet inverzí jsme tím snížili o 2. Musíme ještě nalézt nový přechod, tj. nejlevější dvojici mc. Z pozice starého přechodu (p) je jasné, že bude napravo od pozice p+1, na níž je nyní modrá figurka. Hledání nového přechodu začneme tedy na této pozici, což je znázorněno znakem M.

Pokud napravo od přechodové dvojice je sice modrá figurka, ale za ní je červená (případ 1.2, cm|cmc), provedeme krok délky 4 (počet inverzí klesne o 2):
cm|cmc -> ccMcm
#m|cmc -> #cMcm
Konečně jestliže napravo od přechodové dvojice jsou (aspoň) dvě modré figurky (případ 1.3, cm|cmm), vykonáme dva kroky, jeden délky 3 a další délky 4:
cm|cmm -> cmmmc -> ccmmM
#m|cmm -> #mmmc -> #cmmM
Počet inverzi klesne o 1 (po druhém kroku), tedy počet inverzí jsme snížili o 1/2 za jeden krok. To je sice méně, než jsme slíbili v (*), ale stále to dává kvadratický odhad počtu kroků.

Zůstává nám vyřešit případ 2 (mm|c). Je-li napravo od přechodové dvojice červená figurka (případ 2.1, mm|cc), provedeme krok délky 4 a snížíme tím počet inverzí o 4:
mmm|cc -> Mccmm
cmm|cc -> cccmM
#mm|cc -> #ccmM
Pokud napravo od přechodové dvojice je modrá figurka nebo pravý okraj pole (případ 2.2, mm|cm, mm|c#), provedeme krok délky 3 a snížíme počet inverzí o 2:
mmm|cm -> Mcmmm
cmm|cm -> ccmMm
#mm|cm -> #cmMm
mmm|c# -> Mcmm#
cmm|c# -> ccmM#
#mm|c# -> #cmM#
V případě 2 musíme počítat ještě s jednou komplikací (případ 2.K). Jsou-li nalevo od přechodové dvojice dvě modré figurky (mmm|c), nový přechod bude oproti starému (p) posunutý o 2 pozice doleva (viz 1. a 4. řádek z předcházející šestice). Pečlivé sledování pozice nového přechodu nám zabezpečí, aby nejen počet kroků hry, ale i časová složitost algoritmu byla kvadratická.

P-II-2

Z daného bodu může robot pokračovat třemi směry, označme je a, b, c. Průchodem po první cestě a zaznamenáním typu směru pro každou úsečku dostaneme řetězec Aret charakterizující cestu. Analogicky získáme řetězec Bret. Oba průchody je možné vykonat v lineárním čase O(n), resp. O(m).

Problém sa tak redukuje na určení délky nejdelší společné podposloupnosti dvou řetězců. Algoritmus má složitost O(mn) a je založen na následujícím principu:
Předpokládejme, že máme určené délky nejdelších společných podposloupností tří dvojic podřetězců

Máme vypočítat délku nejdelší společné podposloupnosti dvojice podřetězců A[1]... A[i], B[1]... B[j]. Je třeba rozlišit, zda se prvky A[i] a B[j] rovnají nebo ne.
(protože hledáme nejdelší společnou podposloupnost, vezmeme maximum z uvedených dvou hodnot)

Celý výpočet je třeba provést pro i=1,...,m a j=1,...,n. Pomocné hodnoty, je-li některý z podřetězců prázdný, jsou nulové. Po určení této délky získáme hledané počty odečtením od délek cest.

program Roboty; const nmax=100; { maximální počet bodů } type bod = record x, y:integer end; Cesta = array[1..nmax] of bod; Ret = array[1..nmax] of char; var A, B: Cesta; { schodovité množiny bodů } Ret_A, Ret_B: Ret; { řetězce patřící k cestám } m,n : integer; { počty bodů v množinách } poc: integer; { počet rovnoběžných úseček } function dnsp(Ret_A, Ret_B: Ret; m, n: integer): integer; { určí délku nejdelší společné podposloupnosti dvou řetězců } var i, j: integer; t: integer; p: array[1..2, 0..nmax] of integer; { pole obsahující délky společných prefixů podposloupností } begin for j:=0 to n do p[1,j]:=0; p[2,0]:=0; for i:=1 to m do begin { průchod jedním řetězcem} for j:=1 to n do { průchod druhým řetězcem} if Ret_A[i]=Ret_B[j] then p[2,j] := p[1,j-1]+1 else begin t:=p[1,j]; if t < p[2,j-1] then t:=p[2,j-1]; p[2,j]:=t end; { p[2,j] = dnsp(A[1..i],B[1..j]} for j:=1 to n do p[1,j]:=p[2,j]; end; dnsp:=p[2,n]; end; {dnsp} procedure nacti( var A, B:Cesta; var m, n: integer); { načtení bodů schodovitých množin a jejich počtů ze souboru } var i:integer; f:text; begin assign(f,'II_2.dat'); reset(f); readln(f,m); for i:=1 to m do readln(f,A[i].x, A[i].y); readln(f,n); for i:=1 to n do readln(f,B[i].x, B[i].y); close(f); end; {nacti} procedure preved(A: Cesta; m: integer; var Ret_A: Ret); { převod schodovité množiny na řetězec směrů přechodů z bodu do bodu} var i:integer; begin for i:=1 to m-1 do if (A[i+1].x=A[i].x+1) and (A[i+1].y=A[i].y-1) then Ret_A[i]:='b' else if (A[i+1].x=A[i].x+2) and (A[i+1].y=A[i].y-1) then Ret_A[i]:='a' else if (A[i+1].x=A[i].x+1) and (A[i+1].y=A[i].y-2) then Ret_A[i]:='c' else writeln('Množina není schodovitá',i:3); end; {preved} begin nacti(A,B,m,n); preved(A,m, Ret_A); preved(B,n, Ret_B); poc:=dnsp(Ret_A,Ret_B,m-1,n-1); writeln('Počet úseček, které je třeba odstranit z 1. množiny, je ', m-poc-1:2,'.'); writeln('Počet úseček, které je třeba odstranit z 2. množiny, je ', n-poc-1:2,'.'); end.

P-II-3

 Řešení této úlohy je podobné řešení úlohy P-I-3. Jediný rozdíl spočívá v tom, že pro každou dvojici států (i,j), kde i < j, spočítáme 11 čísel: optimální výměnné kurzy při maximálním zdržení 0, 1, 2, ..., 10 dní. Tyto výsledky budou uloženy v trojrozměrném poli kurzy. Myšlenka algoritmu je jednoduchá: když cestujeme z i do j a máme povolené zdržení k dní, optimální kurz získáme jako maximum z následujících čísel:
Program nejprve nastaví (Inicializuj) počáteční hodnoty nepřímých kurzů na přímé kurzy (bez mezistanic) a potom postupuje (VypocitejKurzy) v cyklu podle rostoucí hodnoty j(i (délka cesty) a ve vnořeném cyklu pro všechny možné výchozí stanice i. Ve vnořeném cyklu třetí úrovně se zkoumají mezistanice l. Pro každou hodnotu (i, j, l) se určí výměnné kurzy pro všechny možné hodnoty zdržení (for-cykly pro k a kpom), přičemž tělo nejvíce vnořeného for-cyklu (pro kpom) se vykoná nejvýše 0+1+2+...+10 = 55-krát (maximální možné zdržení je 10). Časová složitost celého programu je O(n3).

Zde uvedený program nebere v úvahu omezení některých překladačů na maximální velikost datových struktur, např. v Turbo Pascalu 7.0 je maximální možná hodnota maxn rovna 31, pro vyšší hodnoty hlásí překladač překročení povolené velikosti pole kurzy.

program OrientExpress; const maxn = ...; maxz = 10; var kurzy: array [1..maxn, 1..maxn, 0..maxz] of real; zdrzeni: array [1..maxn] of integer; n: 1..maxn; p: integer; vstup, vystup : text; procedure Inicializuj; var i,j,k: integer; begin assign(vstup, 'p-ii-3.inp'); assign(vystup, 'p-ii-3.out'); reset(vstup); rewrite(vystup); read(vstup, n); for i := 1 to n - 1 do begin for k := 0 to maxz do kurzy[i,i,k] := 1.0; for j := i + 1 to n do begin read(vstup, kurzy[i,j,0]); for k := 1 to maxz do kurzy[i,j,k] := kurzy[i,j,0]; end; end; for i := 1 to n do read(vstup, zdrzeni[i]); read(vstup, p); end; procedure VypocitejKurzy; var d, i, j, l: 1..maxn; { délka cesty, začátek cesty, konec cesty, mezistanice } k, kpom: 0..maxz; { zdržení, zdržení mezi i a l} npk: real; { nepřímý kurz } begin for d := 2 to n - 1 do for i := 1 to n - d do begin j := i + d; for l := i + 1 to j - 1 do for k := 0 to maxz do for kpom := 0 to k-zdrzeni[l] do begin npk := kurzy[i,l,kpom] * kurzy[l,j,k-zdrzeni[l]-kpom]; if (kurzy[i,j,k] < npk) then kurzy[i,j,k] := npk; end; end; end; procedure VypisKurzy; var i, j, k: integer; begin while (p > 0) do begin read(vstup, i,j,k); write(vystup, kurzy[i,j,k]:0:2, ' '); p := p - 1; end; end; procedure Ukonci; begin close(vstup); close(vystup); end; begin Inicializuj; VypocitejKurzy; VypisKurzy; Ukonci; end.

P-II-4

 Jednou možností, jak vytvořit přehledný obvod řešící úlohu, je rozložit problém na dvě časti:

Dekodér

  1. Začneme tím, že vytvoříme negace x0,x1,x2,x3 vstupů x0, x1, x2, x3, tzn. použijeme čtyři hradla typu NOT:
    • H1 = NOT(I1) =x0
    • H2 = NOT(I2) =x1
    • H3 = NOT(I3) =x2
    • H4 = NOT(I4) =x3
  2. Následujících deset hradel typu NAND se 4 vstupy vytvoří požadované výstupy z0, z1, z2, ..., z9:
    • H5 = NAND(H1,H2,H3,H4) = ((x0 & x1 & x2 & x3) = z0
    • H6 = NAND(I1,H2,H3,H4) = (( x0 & x1 & x2 & x3) = z1
    • H7 = NAND(H1,I2,H3,H4) = ((x0 & x1 & x2 & x3) = z2
    • H8 = NAND(I1,I2,H3,H4) = (( x0 & x1 & x2 & x3) = z3
    • H9 = NAND(H1,H2,I3,H4) = ((x0 & x1 & x2 & x3) = z4
    • H10 = NAND(I1,H2,I3,H4) = (( x0 & x1 & x2 & x3) = z5
    • H11 = NAND(H1,I2,I3,H4) = ((x0 & x1 & x2 & x3) = z6
    • H12 = NAND(I1,I2,I3,H4) = (( x0 & x1 & x2 & x3) = z7
    • H13 = NAND(H1,H2,H3,I4) = ((x0 & x1 & x2 & x3) = z8
    • H14 = NAND(I1,H2,H3,I4) = (( x0 & x1 & x2 & x3) = z9

Kodér

Sedm hradel kodéru realizuje funkce jednotlivých segmentů displeje tak, jak je popsáno výše. Všechna hradla jsou typu NAND, každé má 4 až 9 vstupů vybraných z H5 až H14: