Matematická olympiáda – kategorie P

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

P-III-4 Násobek

Program:	 nasobek.pas / nasobek.c / nasobek.cpp 
Vstup:		 nasobek.in 
Výstup:		 nasobek.out 

Nejmenší kladný násobek čísla 13, který je tvořen jen číslicemi 1 a 2, je 221. I číslo 997 má násobky zapsané jen pomocí číslic 1 a 2, nejmenším z nich je 1,121,222,212 = 997 x 1,124,596. Nejmenším násobkem tří, ve kterém mohou být použity pouze číslice 4 a 7, je číslo 444.

Vaši úlohou je napsat program, který bude taková čísla hledat.

Vstup:

Na prvním řádku vstupního souboru je uveden řetězec R tvořený minimálně jednou a maximálně deseti číslicemi (od 0 do 9). Všechny tyto číslice jsou navzájem různé.

Na druhém řádku je uvedeno jedno kladné celé číslo N (1≤ N≤ 1,000,000).

Výstup:

Vypište jediný řádek a v něm jediné celé číslo – nejmenší kladný násobek čísla N, ve kterém se vyskytují pouze číslice z řetězce R. (Pozor, toto číslo může mít mnoho číslic.)

Pokud číslo N žádný takový násobek nemá, vypište místo toho řetězec „neexistuje”.

Příklad:

nasobek.in

12
997

nasobek.out

1121222212

nasobek.in

1379
2

nasobek.out

neexistuje

nasobek.in

7654321
47

nasobek.out

47

P-III-5 Stránka

Program:	 stranka.pas / stranka.c / stranka.cpp 
Vstup:		 stranka.in 
Výstup:		 stranka.out 

Rozhodli jsme se, že začneme konkurovat světoznámým vyhledávačům, jako jsou například Google a Yahoo. Hlavním klíčem k úspěchu bude samozřejmě prezentace nalezených stránek uživateli. Přesněji, chtěli bychom z každé nalezené stránky ukázat co nejkratší úsek obsahující všechna slova, která uživatel hledal. Vaší úlohou bude napsat program, který takový úsek v dané stránce nalezne.

Soutěžní úloha

Je dáno N slov, která uživatel zadal. Také je dán text stránky obsahující M slov. Napište program, který najde nejkratší úsek stránky, v němž se vyskytují všechna zadaná slova (každé alespoň jednou).

Úsek stránky tvoří několik po sobě jdoucích slov. Délka úseku je rovna součtu jejich délek plus jejich počet minus 1 (za mezery mezi nimi). Tedy například úsek „Toto je úsek” má délku 12.

Vstup:

Na prvním řádku vstupního souboru je jediné celé číslo N (1≤ N≤ 100) – počet vyhledávaných slov.

Následuje N řádků, na každém z nich je jedno vyhledávané slovo. Všechna tato slova jsou navzájem různá.

Na následujícím řádku se nachází celé číslo M (1≤ M≤ 10,000) – počet slov na stránce.

Následuje M řádků, na každém z nich je jedno slovo textu stránky, v pořadí, v jakém jsou na stránce uvedena.

Každé slovo je řetězec tvořený jen malými písmenky anglické abecedy, délka každého slova je od 1 do 100 znaků.

Výstup:

Vypište nejkratší úsek stránky, v němž se každé vyhledávané slovo vyskytuje alespoň jednou. Pokud je takových úseků více, vypište ten, který je nejblíže k začátku stránky. Úsek vypisujte tak, jak je uveden na vstupu, tedy každé slovo na samostatném řádku.

Pokud se některé vyhledávané slovo v textu stránky nenachází, vypište jediný řádek s textem „Chybná stránka!” (bez uvozovek).

Příklad:

stranka.in

3
nasi
vasi
prisli
20
poslali
me
nasi
k
vasim
aby
prisli
vasi
k
nasim
kdyz
neprijdou
vasi
k
nasim
tak
neprijdou
nasi
k
vasim

stranka.out

nasi
k
vasim
aby
prisli
vasi