A - Maľovaná krížovkaČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Počet bodov: 1 [ 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. 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 a dĺžky jednotlivých úsekov sú postupne (zľava doprava) r1,..., rK. Napríklad pre N=9, K=3 a r1=3, r2=1, r3=1 je jedno z riešení nakreslených na obrázku (šedé políčka sú vymaľované a políčka s bodkou sú nevymaľované). Ú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), o niektorých vieme, že sú určite vymaľované a o niektorých nevieme nič. 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 dve medzerou oddelené celé čísla N a K (1≤N≤100, 0≤K≤50), kde N je šírka riadku a K je počet úsekov. Druhý riadok obsahuje K medzerou oddelených kladných celých čísel popisujúcich dĺžky úsekov. Môžete predpokladať, že súčet týchto čísel nie je väčší ako N-K+1. Tretí riadok vstupu obsahuje N znakov. Jednotlivé znaky popisujú informácie o políčkach. Znak je buď '?' (otáznik) ak je príslušné políčko neznáme, '.' (bodka) ak je príslušné políčko určite prázdne, alebo 'X' (veľké písmeno x) ak je príslušné políčko určite vymaľované. Môžete predpokladať, že počet znakov ? je nanajvýš 15.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, 'X' ak je vymaľované, '?' ak existujú dve konzistentné riešenia, pričom v jednom je príslušné políčko vymaľované a v druhom prázdne.PríkladVstup9 3 3 1 1 .?????X.? Výstup.?XX?.X.X |