Program:LAMPY.PAS/LAMPY.CPP Vstup:LAMPY.IN Výstup:LAMPY.OUT
Veřejná prostranství ve městě jsou osvětlena N pouličními
lampami. Každá z lamp má jednoznačně přiřazeno číslo od 1 do
N. K zapínání a vypínání veřejného osvětlení slouží v řídicím
středisku M přepínačů. Každý z přepínačů přepne najednou několik
lamp. Přepnout lampu znamená zapnout ji, pokud zrovna nesvítí,
a vypnout ji, jestliže momentálně svítí. Přepínač číslo i přepíná
všechny lampy s čísly od ai do bi,
tzn. lampy s čísly ležícími
v uvedeném intervalu. Můžete předpokládat, že 0
Úloha
Napište program, který zjistí, zda je možné zapnout pomocí
přepínačů v řídicím středisku všechny lampy, jsou-li na začátku
všechny lampy vypnuté.
Vstupní soubor
Vstupní soubor obsahuje několik zadání. První řádek vstupního
souboru je tvořen jediným číslem, které udává počet zadání
v souboru. Pro každé zadání obsahuje vstupní soubor blok údajů
v tomto tvaru: Na prvním řádku bloku jsou uvedena čísla N a M,
kde N je počet lamp ve městě a M je počet přepínačů v řídicím
středisku. Dalších M řádků obsahuje pro jednotlivé přepínače vždy
dvojici čísel ai,
bi(pro každý přepínač interval čísel lamp,
které se pomocí něho přepnou). Jednotlivé bloky údajů jsou ve
vstupním souboru odděleny vždy jedním prázdným řádkem.
Výstupní soubor
Pro každé zadání obsažené ve vstupním souboru obsahuje výstupní
soubor jeden řádek s jednou z následujících zpráv:
Lze - pokud je možné rozsvítit všechny lampy pomocí přepínačů
v řídicím středisku
Program:MANHATAN.PAS/MANHATAN.CPP Vstup:MANHATAN.IN Výstup:MANHATAN.OUT
Ve městě Manhatan vedou všechny ulice buď ze severu na jih, nebo
ze západu na východ. Předpokládejte, že se ulice táhnou oběma
směry dostatečně daleko. V průsečíku každých dvou ulic různých
směrů je křižovatka.
Křižovatku označíme dvojicí čísel (i,j), jestliže se jedná
o křižovatku v pořadí i-té západovýchodní ulice počítáno ze
severu a j-té severojižní ulice počítáno od západu. Křižovatky
jsou tedy očíslovány od (1,1) do (M,N), kde M je počet
západovýchodních ulic a N je počet severojižních ulic. Můžete
předpokládat, že 0
Na některých křižovatkách se pracuje na opravě vozovky, a proto
přes ně není možné přejet. Na křižovatkách (1,1) a (M,N) se
nepracuje.
Arpád vyjíždí každé ráno z křižovatky (1,1) a potřebuje se dostat
do firmy, která sídlí na opačném konci města, tzn. na křižovatce
(M,N).
Úloha
Napište program, který zjistí, kolika různými cestami se může
Arpád dostat do své firmy, jestliže pojede vždy jen ve směru na
jih nebo na východ. Program dále vypíše nejmenší počet
křižovatek, přes které se může takovouto cestou do firmy dostat
(včetně křižovatek (1,1) a (M,N)).
Vstupní soubor
Vstupní soubor obsahuje několik zadání. První řádek vstupního
souboru je tvořen jediným číslem, které udává počet zadání
v souboru. Pro každé zadání obsahuje vstupní soubor blok dat. Na
prvním řádku každého bloku jsou uvedena čísla M a N, kde M je
počet východozápadních ulic a N je počet severojižních ulic. Na
dalším řádku se nachází číslo K - počet křižovatek ve městě, na
nichž se opravuje vozovka. Na každém z následujících K řádků jsou
uvedena vždy dvě čísla určující polohu křižovatky, kde se
pracuje. Jednotlivé bloky vstupních údajů jsou odděleny vždy
jedním prázdným řádkem.
Výstupní soubor
Pro každé zadání ve vstupním souboru obsahuje výstupní soubor
jeden řádek. Na něm jsou:
buď dvě čísla A a B, kde A je počet možných různých cest a B je
počet křižovatek na nejkratší z nich (včetně křižovatek (1,1)
a (M,N)), a to v případě, že existuje aspoň jedna cesta
požadovaného typu
nebo zpráva "Cesta neexistuje", jestliže cesta požadovaného
typu neexistuje