Algoritmizační úloha: žalmy pro svátky
Při jednom z rozhovorů přes dva monitory o tom, co jejich obsluhy dělají ve volném čase, jsem kolegovi popisoval algoritmizační problém, který řeším v souvislosti se sazbou žaltáře. "Fuj, hlavně to neříkej nikomu z FITu, ještě by to třeba začali používat jako domácí úkol," zareagoval kolega, který na zmiňované fakultě ČVUT studoval a domácí úkoly na tvrdě optimalizovaná řešení náročných úloh neměl rád. Mám podezření, že normální budoucí programátor se špetkou nadání mou úlohu vyřeší lusknutím prstu, a jako domácí úkol z algoritmizace tudíž příliš výživná není, ale můj opičí mozek ("ti, co dělají weby, to nejsou žádní programátoři, ale cvičené opice," říká bratranec matfyzák) ji každopádně zatím uspokojivě nevyřešil, takže úplně triviální zřejmě také není. Tady je.
(Následující text nepředpokládá znalost liturgie hodin a některé skutečnosti záměrně zjednodušuje, aby vynikla podstata algoritmizačního problému.)
Mějme knihu s texty modliteb (žaltář). Kniha obsahuje všechny texty potřebné pro všechny modlitby v pořadí, v jakém se používají o běžných dnech. Modlitba sestává obvykle ze tří textů. Texty jsou rozloženy na čtyři týdny a v tomto čtyřtýdenním cyklu se některé z nich vícenásobně opakují.
O některých svátcích se modlitby neberou z tohoto pravidelného cyklu, ale jsou volně vybrané z jeho různých míst. K vyhledání modliteb o takovýchto svátcích slouží zvláštní index na konci žaltáře, který pro každou denní modlitbu odkazuje na tři nebo více textů.
Napište program, který dostane seznam textů potřebných pro každou denní modlitbu a seznam textů, jak jdou v knize za sebou (reálná data: texty pro svátky, normální pořadí textů) a vypíše, kolikátý z případných více výskytů téhož textu v knize se má použít, aby ten, kdo se z knihy modlí, při jedné denní modlitbě listoval právě jen nezbytně málo. Za větší dobro je přitom považováno to, že jsou dva nebo více použitých textů bezprostředně za sebou, než to, že uživatel v průběhu modlitby obrátí nejmenší možné množství stránek.
[EDIT 28.6.2014] Řešení hrubou silou, které by na cvičeních z algoritmizace samozřejmě neprošlo, je na githubu.