4. Pixelová výzva

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy.

Stačí, že pôjdeš na stránku Programátorskej Liahni (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Romanovi na [email protected]

Prišli prázdniny a Bonifác sa nudil. Všetko sa ale zmenilo, keď na záchode otvoril časopis a na poslednej strane objavil maľovanú krížovku. Na nasledujúcom obrázku je jej zadanie aj s Bonifácovým riešením:

Skúste si všimnúť závislosť medzi číslami na okrajoch a výsledným obrázkom – v každom riadku je presne toľko vyfarbených úsekov (súvislých čiernych políčok), koľko je pre daný riadok za okrajom nápovedných čísel. Tieto čísla zároveň presne určujú, koľko bude daný úsek obsahovať vyfarbených políčok a tiež poradie týchto úsekov. Táto vlastnosť platí rovnako aj pre stĺpce¹.

Bonifác rýchlo prišiel na to, ako maľované krížovky riešiť, netrvalo preto dlho a vyriešil všetky, ktoré doma našiel. Teraz však potrebuje nové krížovky, pretože inak ho znovu pochytí hrozná nuda. Jeho sestra Amálka je maliarka a tak sa rozhodla, že pre Bonifáca namaľuje nové obrázky. Celý deň pilne kreslila a podarilo sa jej vytvoriť slona, stoličku, vlak či korytnačku. Z jej obrázkov je ale potrebné ešte vytvoriť zadanie maľovaných krížoviek pre Bonifáca. S touto úlohou si už nevie dať rady a tak potrebuje vašu pomoc.

Na jednom z Amálkiných obrázkov si teda ukážeme, čo bude vašou úlohou.

Úloha

Ako by vyzeralo zadanie maľovanej krížovky pre tento obrázok? Potrebujeme popísať súvislé úseky v jednotlivých riadkoch a stĺpcoch. Začneme riadkami – v prvom riadku je iba jeden úsek veľkosti \(2\). Nasleduje riadok, ktorý by sme popísali nápovedou \(2\), \(4\), pretože prvý úsek v ňom má veľkosť 2 a druhý veľkosť 4. Analogicky postupujeme pre ostatné riadky.

Pre stĺpce postupujeme rovnako – v prvom stĺpci je iba jeden úsek veľkosti \(2\), v druhom stĺpci jeden úsek veľkosti \(3\), atď..

Na vstupe máme Amálkin čiernobiely obrázok, ktorý má \(r\) riadkov a \(s\) stĺpcov. Obrázok je mriežka s rozmermi \(r \times s\), ktorá obsahuje \(1\) na pozíciach, ktoré sú vyfarbené, teda čierne a \(0\) na nevyfarbených, bielych políčkach. Vašou úlohou je z tohto obrázka vytvoriť zadanie pre maľovanú krížovku, teda spočítať súvislé úseky vyfarbených políčok v jednotlivých riadkoch a stĺpcoch.

Formát vstupu

Na prvom riadku dostanete dve čísla \(r\) a \(s\) – počet riadkov a stĺpcov obrázka. Nasleduje popis obrázka. Na každom z nasledujúcich \(r\) riadkov sa bude nachádzať \(s\) medzerou oddelených čísel. Číslo je buď \(1\) alebo \(0\), podľa toho, či je dané políčko čierne alebo biele.

Formát výstupu

Ako prvé budeme vypisovať úseky v riadkoch maľovanej krížovky. Pre každý z \(r\) riadkov obrázka, začínajúc najvrchnejším, vypíšte na samostatnom riadku medzerami oddelené veľkosti jednotlivých úsekov v danom riadku v poradí zľava doprava. Ak sa v tomto riadku žiaden úsek nenachádza, vypíšte 0.

Hneď za popisom riadkov bude nasledovať práve jeden prázdny riadok. Potom nasleduje popis stĺpcov. Ten bude rovnaký ako pri riadkoch – pre každý z \(s\) stĺpcov, začínajúc najľavším, vypíšte na samostatnom riadku medzerami oddelené veľkosti jednotlivých úsekov v danom stĺpci v poradí zhora nadol. Ak v stĺpci nie je žiadny vyfarbený úsek, vypíšte 0.

Hodnotenie

Pri testovaní bude vaše riešenie spustené na rôznych sadách vstupov, ktoré sa navzájom líšia obtiažnosťou ich riešenia. Za každú úspešne vyriešenú sadu dostanete 3 body. Obmedzenia pre \(r\) a \(s\) nájdete v nasledujúcej tabuľke.

Príklady

Input:

6 10
0 0 0 0 0 1 1 0 0 0
1 1 0 0 1 1 1 1 0 0
1 1 0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 1 1 0
0 0 0 1 0 0 0 1 0 0
0 0 1 1 0 0 1 1 0 0

Output:

2
2 4
2 6
8
1 1
2 2


2
3
1 1
4
3
4
4 1
5
2
0

Vstup je Amálkin obrázok, ktorý sme si ukázali vyššie. Vo výstupe je 7. riadok prázdny – oddeľuje popis riadkov a stĺpcov. Posledný stĺpec obrázka je nevyfarbený, čomu vo výstupe zodpovedá 0 na konci.

Input:

1 8
1 0 1 1 1 0 1 1

Output:

1 3 2


1
0
1
1
1
0
1
1

Vstup, ktorý sa môže vyskytnúť v prvej sade.