Pátá série desátého ročníku KSP

Zadání úloh

10-5-1 Společná podmatice (10 bodů)

Jsou dány matice A[n×n] a B[n×n]. Nalezněte jejich největší společnou podmatici (to jest taková a,b,c,d,p,q, že pro každé 0≤ i<p a 0 ≤ j<q je Aa+i,b+j = Bc+i,d+j a c·d je největší možné).

Řešení

10-5-2 Kob ýlam ám alybok? (10 bodů)

Don Coyote, pán zámku Barabizonu, měl podivnou zálibu: hledal v knihách co nejdelší úseky, které vypadají stejně i při čtení pozpátku (například slova `nepochopen' a `nepotopen' nebo větu `Jelenovi pivo nelej' – na mezery nehleděl). Zkuste napsat program, který jeho problém snadno a rychle vyřeší.

Řešení

10-5-3 Cycloose (8 bodů)

Mějme následující jednoduchý Pascalský prográmek:

var r:real;
begin r := 1; while r < 1e30 do r := r+1; end.

Nebo ekvivalent v Céčku:

main() { float r; for(r=0;r<1e30;r++); }

Otázka zní: Doběhne při rychlostech dnešních běžných počítačů do konce příštího století? Tisíciletí? A nebo do zítřejšího rána?

Řešení

10-5-4 S radostí přijmi svůj (o)sud (10 bodů)

Ztroskotali jste na pustém ostrově … tedy on alespoň na začátku pustě vypadal, ale ke svému nemalému úžasu jste zjistili, že jej obývají duchové dávno ztroskotavších byzantských obchodníků s vínem a že se neustále hádají o jednom problému: mají několik (řekněme k) nádob známých objemů v1, … , vk pint a potřebují jimi odměřit p pint vína. Chtějí to ovšem odměřit přesně (žádné odhadování, to do seriózního obchodu nepatří! … tedy alespon v říši neviných duchů vinných obchodníků), takže vždy mohou jen naplnit určitou nádobu až po okraj vínem (ať již ze sudu nebo z jiné nádoby) nebo nějakou nádobu zcela vyprázdnit (ať již zpět do sudu či do jiné nádoby).

Zkuste vymyslet, jak pro dané velikosti nádob vymyslet, jak na co nejmenší počet přelití odměřit p pint vína. (Duchové vám totiž slíbili, že když jim pomůžete, žízní nezahynete…)

Přiklad: Jsou-li objemy nádob 3,5,7 pint a potřebujeme odměřit 1 pintu vína, přeléváme S→3 (S je sud; máme 0,0,7), 3→1 (3,0,4), 1→S (0,0,4) a 3→1 (3,0,1).

Řešení