Matematická olympiáda – kategorie P

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

P-III-4 Nákup

Program: NAKUP.PAS / NAKUP.C / NAKUP.CPP
Vstup: NAKUP.IN
Výstup: NAKUP.OUT

V obchodním domě prodávali n druhů zboží o cenách c1,...,cn. Aby obchodníci přilákali zákazníky, nabízejí ještě speciální slevy typu "když si koupíte tři balení laku na vlasy a dvě balení odstraňovače starých nátěrů, bude to stát dohromady pouze 300". Každou zlevněnou nabídku je možno charakterizovat počty nabízených druhů zboží pij (kolik si musíte koupit předmětů druhu j, aby se uplatnila i-tá sleva) a cenou nabídky w_i (všechny nabídky jsou výhodné, to jest wi < pi1c1+pi2c2+...).

Vy jste si z nabídky obchodního domu vybrali maximálně 5 druhů předmětů a od každého z nich maximálně 6 kusů a chcete toto zboží nakoupit co nejlevněji. Není vám proti mysli, když si z obchodního domu odnesete ještě něco navíc, pokud tím ušetříte.

Napište program, který dostane na vstupu ceny zboží, informace o zlevněných nabídkách, jakož i seznam toho, co má být nakoupeno, a nalezne optimální využití nabídek (to jest, kolikrát má být využito které nabídky, aby bylo dosaženo nejnižší možné celkové ceny dané součtem cen nabídek a cen jednotlivých výrobků, jež je nutno k nabídkám doplnit, abyste nakoupili vše, co potřebujete).

Vstup

Ve vstupním textovém souboru NAKUP.IN jsou postupně uvedeny tyto údaje (mezi libovolnými dvěma z nich může být rozhraní řádků):

Výstup

Výstupem programu bude minimální dosažená cena wmin spolu se seznamem využitých nabídek ve tvaru d1 e1 d2 e2 ... dq eq, kde di jsou čísla využitých nabídek a ei čísla udávající, kolikrát byla která nabídka využita. Vypisujte pouze ty nabídky, které mají ei nenulové. Výsledky program zapíše do výstupního textového souboru NAKUP.OUT. Jednotlivá čísla budou oddělena mezerami nebo konci řádek.

Příklad

Pro vstup 10 10 11 12 13 14 15 16 17 18 19 5 1 3 2 5 4 2 8 2 9 1 3 1 1 2 2 4 1 0 20 1 1 2 1 3 1 0 10 5 3 6 3 0 30 je jedním ze správných řešení výstup 102 1 2 2 1

P-III-5 Vigenerova šifra

Program: SIFRA.PAS / SIFRA.C / SIFRA.CPP
Slovník: SLOVNIK.TXT
Pomocné soubory: *.POM
Vstup: SIFRA.IN
Výstup: SIFRA.OUT

Uvažujme následující způsob šifrování, nazývaný Vigenerova šifra. Pro jednoduchost budeme šifrovat pouze texty obsahující jen malá písmena anglické abecedy a mezery. Při šifrování se používá tajný klíč, který je sestaven z malých písmen anglické abecedy. Písmena klíče napíšeme pod jednotlivá písmena šifrovaného textu a je-li klíč příliš krátký, použijeme ho vícekrát za sebou. Každé písmeno textu potom zašifrujeme tak, že k němu přičteme pod ním napsané písmeno klíče. Sčítání písmen se provádí tak, že obě písmena nahradíme čísly od 0 do 25 představujícími jejich pořadí v abecedě a tato dvě čísla sečteme. Pokud je výsledek sčítání větší než 25, odečteme od něj 26 a nakonec nahradíme výsledné číslo opět písmenem, které je v abecedě na odpovídajícím místě. Mezery se opisují z původního textu do šifrovaného textu beze změny.

Zašifrujme například text quicksort is an algorithm for sorting pomocí klíče programming. V tabulce je na prvním řádku původní text, na druhém řádku klíč a na třetím výsledný text:
quicksort is an algorithm for sorting
programmi ng pr ogramming pro grammin
flwibsadb vy pe orxodubus uff yfrfuvt
Při dešifrování se postupuje podobně, místo přičítání se však klíč odčítá. Jestliže zašifrovanou zprávu zachytí osoba, která nezná klíč, může se pokusit zprávu dešifrovat tak, že předpokládá, že zpráva byla napsána v nějakém přirozeném jazyce, a hledá takový klíč, aby dostala smysluplnou zprávu v tomto jazyce. Vaším úkolem bude nyní napsat program, který pro daný zašifrovaný text hledá nějaký "smysluplný" klíč.

Zašifrovaný text je umístěn ve vstupním souboru SIFRA.IN. Je to posloupnost slov složených z malých písmen, přičemž jednotlivá slova jsou oddělena mezerou nebo koncem řádku (konec řádku se při šifrování a dešifrování chová stejně jako mezera). Soubor neobsahuje více než 10000 znaků.

Vaším úkolem je napsat program, který najde pro zašifrovaný text uložený v souboru SIFRA.IN klíč Vigenerovy šifry a zapíše ho do souboru SIFRA.OUT. Přípustný je pouze takový klíč, jehož použitím k dešifrování souboru SIFRA.IN dostaneme text, který obsahuje pouze povolená slova přirozeného jazyka. Seznam všech povolených slov přirozeného jazyka se nachází v souboru SLOVNIK.TXT. Váš klíč nesmí být delší než 50 znaků. Můžete předpokládat, že takový klíč existuje a že délka textu je velká v porovnání s délkou klíče.

Poznámka: Ve vašem pracovním adresáři se nachází soubor SLOVNIK.TXT, který obsahuje seznam všech povolených slov přirozeného jazyka. Kromě samotného zdrojového souboru s programem můžete vytvořit a spolu s řešením úlohy odevzdat několik pomocných souborů s příponou .POM, které při testování umístíme do aktuálního adresáře. V aktuálním adresáři se bude nacházet také soubor SLOVNIK.TXT, který bude totožný se souborem ve vašem pracovním adresáři (sada povolených slov bude tedy při testování stejná jako v původním souboru SLOVNIK.TXT).