NAKUP.PAS
/ NAKUP.C
/ NAKUP.CPP
NAKUP.IN
NAKUP.OUT
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).
NAKUP.IN
jsou postupně uvedeny tyto údaje (mezi libovolnými
dvěma z nich může být rozhraní řádků):
NAKUP.OUT
.
Jednotlivá čísla budou oddělena mezerami nebo konci řádek.
SIFRA.PAS
/ SIFRA.C
/ SIFRA.CPP
SLOVNIK.TXT
*.POM
SIFRA.IN
SIFRA.OUT
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
).