B - Farebná maľovaná krížovkaČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 2 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Väčšina z vás určite pozná maľované krížovky. Maľovaná krížovka je štvorčeková sieť, kde pri každom riadku a každom stĺpci sú napísané nejaké čísla (rôznych farieb). Podľa týchto čísel je potrebné niektoré políčka siete vymaľovať (a ostatné ponechať prázdne), čím dostaneme obrázok, ktorý krížovka skrýva. Pri riešení maľovanej krížovky sa často zameriame na jeden riadok alebo stĺpec a skúšame podľa príslušných čísel zistiť o ňom čo najviac. Jeden riadok krížovky sa skladá z N políčok a je pri ňom napísaných K čísel r1,..., rK. Riešením riadku je také vymaľovanie políčok, v ktorom počet súvislých vymaľovaných úsekov je presne K, dĺžky jednotlivých úsekov sú postupne (zľava doprava) r1,..., rK a farby f1,..., fK. Farby označíme malými písmenami. Napríklad pre N=9, K=3 a r1=3, r2=1, r3=1 a f1=a, f2=b, f3=c sú dve z riešení nakreslené na obrázku (políčka s bodkou sú nevymaľované). Medzi úsekmi rovnakej farby musí byť aspoň jedna medzera (ale políčka rôznych farieb sa môžu dotýkať, tzn. nemusí byť medzi nimi žiadna medzera). ÚlohaDaný je čiastočne vyriešený riadok maľovanej krížovky, t.j. o niektorých políčkach vieme, že sú určite prázdne (je na nich bodka) a o zvyšných nevieme nič (teda v danom riadku ešte nie je vymaľované žiadne políčko). Konzistentné riešenie je také riešenie daného riadku, ktoré neprotirečí uvedeným známym informáciám. Úlohou je zistiť, čo majú spoločné všetky konzistentné riešenia.VstupPrvý riadok vstupu obsahuje jeden riadok krížovky (dĺžky najviac 100 znakov). Jednotlivé znaky popisujú informácie o políčkach. Znak je buď '?' (otáznik) ak je príslušné políčko neznáme alebo '.' (bodka) ak je príslušné políčko určite prázdne. Druhý riadok obsahuje popis úsekov. Každý úsek je popísaný znakom farby (malé písmeno anglickej abecedy) nasledovaným dĺžkou úseku, údaje o úsekoch sú oddelene medzerou.VýstupAk neexistuje žiadne konzistentné riešenie, výstup by mal obsahovať text "Neda sa vyriesit." (bez úvodzoviek). V opačnom prípade by výstup mal obsahovať jediný riadok s N znakmi popisujúcimi konzistentné riešenia riadku. Znak je buď '.' ak je príslušné políčko nevymaľované vo všetkých konzistentných riešeniach, znak farby ak je vymaľované, '?' ak existujú dve konzistentné riešenia, (buď v jednom je príslušné políčko vymaľované a v druhom prázdne, alebo v dvoch riešeniach je vymaľované políčko rôznymi farbami)Príklad 1Vstup:??????.????.??? a2 a4 b3 Vystup:??????.aaaa.bbb Príklad 2Vstup:??????.????.??? a2 x4 b3 Vystup:??????.????.??? Príklad 3Vstup:??????.????.??? a2 x4 b4 Výstup:aaxxxx.bbbb.... Príklad 4Vstup:???.????.???? a4 b3 Výstup:....aaaa.?bb? Príklad 5Vstup:???.??? a4 Výstup:Neda sa vyriesit. |