Napište program na řešení této hry. Váš program přečte ze
vstupního souboru P-II-1.INP:
P-II-1.OUT program zapíše:Robot se může pohybovat po cestě, která je tvořena úsečkami spojujícími sousední body schodovité množiny A[1], A[2], ..., A[n], n >= 2, tedy po cestě sestavené z úseček A[1]A[2], A[2]A[3], ..., A[n-1]A[n]. Schodovitou množinu je možné upravit odstraněním jedné nebo více úseček. Odstranění úsečky A[i]A[i+1] z cesty znamená ztotožnění bodu A[i+1] s bodem A[i] a posun všech bodů A[i+2],..., A[n] o stejnou vzdálenost ve směru osy x a ve směru osy y jako u bodu A[i+1]. Po odstranění této úsečky vzniká opět schodovitá množina s počtem bodů o 1 menším.
Máme dva roboty A a B a pro každého z nich je dána schodovitá množina bodů určující cestu, po níž se robot pohybuje. Množina robota A je tvořena n body A[1], A[2], ..., A[n], množina robota B obsahuje m bodů B[1], B[2], ..., B[m]. Navrhněte co nejlepší algoritmus na určení minimálního počtu úseček, které je třeba odstranit z cest robotů, aby se oba roboti při současném odstartování z prvního bodu své upravené schodovité množiny pohybovali (při stejné rychlosti) stále rovnoběžně vůči sobě. Svou cestu musí skončit zároveň v posledním bodě upravené schodovité množiny.
Vstupní soubor P-II-2.INP obsahuje:
P-II-2.OUT ukládáme pouze dvě celá čísla
představující počet úseček vynechaný z cesty robota A a počet
úseček vynechaných z cesty robota B.
P-II-3
Orient-expres projíždí n různými státy (předpokládejme n < 100).
Státy si pro jednoduchost očíslujeme od 1 do n v tom pořadí, jak
jimi Orient-expres projíždí. Každý stát má svou vlastní měnu
(měny také očíslujeme, stát k má měnu k). Měny jsou mezi sebou
volně směnitelné s tím, že ve státě k můžeme nakupovat jakékoliv
jiné měny, ale vždy jen za měnu k. Cestujeme ze státu i do státu
j (i < j), takže potřebujeme nakoupit měnu j. Kladné reálné číslo
K[i,j] určuje, kolik jednotek měny j dostaneme při přímé výměně
za jednu jednotku měny i. Někdy ale mohou být výhodnější nepřímé
obchody: vyměníme měnu i za l a potom měnu l za j (i < l < j),
příp. i za l, l za m a m za j (i < l < m < j), atd.
Vlády některých států se rozhodly zvýšit své příjmy z turistického ruchu, a proto každého cestujícího, který vystoupí z Orient-expresu, aby si například vyměnil peníze, na několik dní zdrží. Nezáporné celé číslo T[i] určuje, kolik dní musí turista strávit ve státě i, pokud si tam vyměnil peníze. (Náklady spojené s tímto pobytem nadále neuvažujeme a pro jednoduchost budeme předpokládat, že cestující na mezistanicích vystupují z vlaku pouze za účelem výměny peněz.) Po uplynutí T[i] dní pokračuje cestující v cestě (Orient-expres jezdí denně). Žádný cestující není ochoten obětovat více než určitý počet dní (maximálně 10) na "turistický pobyt" na mezistanicích.
Předpokládejme například, že cestujeme ze státu 1 do státu 3 a měny států 1, 2 a 3 se jmenují vony, tugriky a dongy. Jestliže za 1 von dostaneme 1,50 tugriku nebo 1,25 dongu a za 1 tugrik dostaneme 0,90 dongu, je výhodnější vyměnit vony nejdříve za tugriky a potom takto získané tugriky za dongy. Za sto vonů tak dostaneme 135 dongů namísto 125 dongů, které bychom obdrželi přímou výměnou. Pokud ovšem T[2]=5 a my si můžeme dovolit zdržení nejvýše 3 dny, výhodnější způsob výměny peněz nemůžeme použít. (Všimněte si, že T[1] a T[3] v této úvaze nehrají žádnou roli).
Napište program, který po načtení tabulky výměnných kurzů K a tabulky zdržení T dokáže odpovídat na otázky typu "jaký je nejvýhodnější (přímý nebo nepřímý) výměnný kurz při cestě ze státu i do státu j, jsme-li ochotni strávit nejvýše k dní turistikou?".
Vstupem programu v souboru P-II-3.INP je:
Vstupy a výstupy celého obvodu, stejně jako vstupy a výstupy jednotlivých hradel, se mohou nacházet v jednom ze dvou logických stavů 0 (false) nebo 1 (true). Výpočet obvodu je taktován. Jestliže jsou vstupy hradla H v čase t v logických stavech x1[t], x2[t], ..., xp[t], výstup hradla H bude v čase t+1 v logickém stavu z[t+1] určeném vstupy a typem hradla. Pokud je na tento výstup napojen například vstup x' hradla H', bude v čase t+1 vstup x' v logickém stavu z[t+1], tzn. logický stav se po spojnicích šíří bez zdržení.
Budeme používat tři typy hradel: NAND, NOR (s alespoň dvěma
vstupy) a NOT (s jedním vstupem). Závislost výstupu těchto tří
typů hradel na vstupech je popsána následující tabulkou (pro
p=2):
| x[t] | y[t] | z[t+1] |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| x[t] | y[t] | z[t+1] |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
| x[t] | z[t+1] |
| 0 | 1 |
| 1 | 0 |
Vstupem celého obvodu je n-tice logických stavů, v nichž se nacházejí jednotlivé vstupní body obvodu. Logický stav vstupů obvodu se během výpočtu nemění. Hradla postupně reagují na logické stavy svých vstupů a mění podle toho stavy svých výstupů. Samozřejmě, jakmile se v čase t ustálí (tj. dále se nemění) logické stavy vstupů hradla, od okamžiku t+1 se ustálí také jeho výstup. Po konečném čase se ustálí i logické stavy výstupů obvodu. Výsledkem výpočtu je m-tice logických stavů jednotlivých výstupů obvodu.
Výstupy obvody odpovídají jednotlivým segmentům displeje:
y0 ovládá horní vodorovný segment
y1 ovládá levý horní svislý segment
y2 ovládá pravý horní svislý segment
y3 ovládá střední vodorovný segment
y4 ovládá levý dolní svislý segment
y5 ovládá pravý dolní svislý segment
y6 ovládá dolní vodorovný segment
Přesné chování obvodu můžeme popsat tabulkou, kde 0 znamená
"nesvítí", 1 znamená "svítí" a ? je "libovolná hodnota" (0 nebo
1):
| x3x2x1x0 | y0 | y1 | y2 | y3 | y4 | y5 | y6 |
| 0000 (0) | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
| 0001 (1) | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0010 (2) | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0011 (3) | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0100 (4) | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 0101 (5) | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
| 0110 (6) | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0111 (7) | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1000 (8) | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1001 (9) | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
| jiné | ? | ? | ? | ? | ? | ? | ? |