Fórum studentů MFF UK

zufaly dispecer

v meste je velke mnozstvo lamp, ktore su ocislovane. dispecerovi bolo nakazane, ze ak je to mozne, tak ma v meste zazat vsetky lampy (na zaciatku su vsetky zhasnute) s tym, ze k dispozicii ma vela prepinacov. prepinacov je menej ako lamp (priklad: mame 10^5 lamp a napriklad 10^3 prepinacov).
prepinac i zazina/zhasina lampy z nejakeho uzavreneho intervalu a s indexom i az b s indexom i.
ulohou je vymysliet nejaky algoritmus, ktory riesi toto zadanie a nema exponencialnu zlozitost, tj vyskusanie vsetkych moznosti nie je spravne.

Zdar, zadání ze včerejška jest následující:

Máme stát, v něm hodně měst (ale ne zas tolik, aby se to nevešlo do paměti; jde o rychlost), mezi dvěma městy může (nebo nemusí) vést libovolný počet přímých silnic. Všechny silnice jsou šotolinové.

Konaly se volby, které vyhrála strana A, která slíbila vyasfaltovat všechny silnice. Načež strana B se rozhodla, že jim úkol stíží, a prosadila následující legislativní úpravu:
(i) v každém dni se mohou vyasfaltovat právě dvě na sebe navazující silnice (X->Y, Y->Z),
(ii) žádná silnice se nesmí asfaltovat dvakrát.

Vládní strana A proto zadala softwarové firmě, aby problém vyřešila. SW firma jste vy. Otázky jsou nasnadě: Jde to? Pokud ano, vytvořte harmonogram prací.

Dr. Kryl celou dobu utěšoval, že jde o lehký příklad, nicméně u ústního připustil, že se mu moc nepovedl. Řešení se dalo nějak spatlat přes grafy atd.