Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 45. ročníku

Bílovec, 26.4.1996

P-III-4

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:

Příklad

Soubor LAMPY.IN

2 5 3 1 3 2 5 2 3 10 5 1 9 2 10 3 10 4 10 5 10

Soubor LAMPY.OUT

Lze Nelze

P-III-5

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:

Příklad

Soubor MANHATAN.IN

2 4 3 2 2 2 3 2 2 4 2 1 2 2 3

Soubor MANHATAN.OUT

2 6 Cesta neexistuje