Zadanie

Bôby… Predo mnou bôby, za mnou bôby, pred bôbom bôby, za bôbom bôby, pred Bobom bôby… Všade samé bôby. Ako keby sa s nimi vrece roztrhlo. A veru sa aj roztrhlo. A nie jedno.

Farmár Bob, vlastní obrovské pole a na ňom pestuje bôby. Bôby sú zdravé a sadia sa veľmi jednoducho: stačí priniesť vrece semienok bôbov na pole a vrece roztrhnúť. Semienka z roztrhnutého vreca sa rozprsknú po okolí a pokryjú súvislú plochu poľa. Bob je v trhaní vrecí neskutočne zručný a dokáže roztrhnúť vrece tak, aby semienka pokryli ľubovoľnú súvislú plochu poľa.

Predvčerom si Bob zaumienil, že spraví zo svojho poľa umelecké dielo. Neznáša stereotypy a tak chce, aby každý kúsok jeho poľa vyzeral inak. Cez internet si kúpil niekoľko rôznych odrôd bôbov a semienka každého druhu si dal zabaliť do osobitného vreca. Teraz rozmýšľa, ako vysadiť semienka.

Úloha

Bob má \(n\) vriec so semienkami bôbov a v každom vreci má inú odrodu. Bobove pole je mriežka políčok \(r\times s\), pričom celkový počet políčok je \(r\cdot s = 2^n\). Na každom políčku môžu rásť bôby ľubovoľných odrôd (kľudne viac odrôd na jednom políčku) a dve políčka vyzerajú inak práve vtedy, ak na nich rastie iná množina bôbov.

Bob môže každú odrodu bôbov vysadiť na nejakú súvislú plochu políčok – políčka sú považované za susedné, ak sa dotýkajú stranami. Chce to spraviť tak, aby každé políčko vyzeralo inak, teda na každom políčku poľa bola iná množina bôbov – bude teda existovať aj políčko, na ktorom nie sú žiadne bôby, aj políčko na ktorom sú všetky bôby.

Vašou úlohou je pre dané \(r\) a \(s\) navrhnúť, ako má Bob roztrhnúť jednotlivé vrecia. Pre každú odrodu určite, na ktorých políčkach sa bude nachádzať.

Formát vstupu

Na vstupe sú dve čísla \(r\) a \(s\), oddelené medzerou. (\(4\leq r,s\leq 256\), \(rs = 2^n\), pre nejaké celé \(n\).)

Formát výstupu

Vypíšte popisy \(n\) odrôd oddelené prázdnymi riadkami.

Popis \(k\)-tej odrody pozostáva z \(r\) riadkov dlhých \(s\) znakov, pričom \(j\)-ty znak v \(i\)-tom riadku má byť veľké \(k\)-te písmeno anglickej abecedy, v prípade, že na políčku \((i,j)\) má byť zasadená \(k\)-ta odroda, a bodka v opačnom prípade. Pre istotu si pozri ukážkový výstup.

Plocha pokrytá každým písmenom musí byť súvislá, hoci plocha pokrytá bodkami nemusí. Za posledným popisom nevypisujte prázdny riadok.

Pokiaľ je možných riešení viacero, vypíšte ľubovoľné z nich.

Príklad

Input:

4 4

Output:

AAAA
AAAA
....
....

BBB.
B...
BBBB
....

.CCC
.C..
CC..
CC..

.D..
DDD.
D.D.
D.D.

V tejto úlohe stačilo nájsť zopár dobrých patternov a naprogramovať ich. Možností je mnoho, napríklad jeden spôsob, ako sa dalo postupovať je popísaný v tomto návode.

Keby jednotlivé plochy nemuseli byť súvislé tak jednotlivé patterny (napríklad pre veľkosť \(16\times 4\)) budú vyzerať takto.

AAAAAAAAAAAAAAAA   BBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAA   ................
................   BBBBBBBBBBBBBBBB
................   ................

CCCCCCCC........   DDDD....DDDD....   EE..EE..EE..EE..   F.F.F.F.F.F.F.F.
CCCCCCCC........   DDDD....DDDD....   EE..EE..EE..EE..   F.F.F.F.F.F.F.F.
CCCCCCCC........   DDDD....DDDD....   EE..EE..EE..EE..   F.F.F.F.F.F.F.F.
CCCCCCCC........   DDDD....DDDD....   EE..EE..EE..EE..   F.F.F.F.F.F.F.F.

Niektoré časti plôch môžeme preklopiť a tým zlepiť niektoré pásiky dokopy bez toho, aby sme niečo pokazili.

AAAAAAAAAAAAAAAA   ................
AAAAAAAAAAAAAAAA   BBBBBBBBBBBBBBBB
................   BBBBBBBBBBBBBBBB
................   ................

CCCCCCCC........   ....DDDDDDDD....   EE....EEEE....EE  .FF..FF..FF..FF.
CCCCCCCC........   ....DDDDDDDD....   EE....EEEE....EE  .FF..FF..FF..FF.
CCCCCCCC........   ....DDDDDDDD....   EE....EEEE....EE  .FF..FF..FF..FF.
CCCCCCCC........   ....DDDDDDDD....   EE....EEEE....EE  .FF..FF..FF..FF.

Takéto zlepené pásiky sa dajú kompletne zlepiť do jedného kusa, vhodnou zmenou prvých troch riadkov. Tieto prvé riadky sú akokeby “čapaté” zatiaľ čo ostatné sú rovné.

AA....AAAA....AAAA....AAAA....AA     .BB..BB..BB..BB..BB..BB..BB..BB.
.AA..AA..AA..AA..AA..AA..AA..AA.     ..BBBB....BBBB....BBBB....BBBB..
..AAAA....AAAA....AAAA....AAAA..     .BB..BB..BB..BB..BB..BB..BB..BB.
.AA..AA..AA..AA..AA..AA..AA..AA.     BB....BBBB....BBBB....BBBB....BB
.AA..AA..AA..AA..AA..AA..AA..AA.     BB....BBBB....BBBB....BBBB....BB
.AA..AA..AA..AA..AA..AA..AA..AA.     BB....BBBB....BBBB....BBBB....BB
.AA..AA..AA..AA..AA..AA..AA..AA.     BB....BBBB....BBBB....BBBB....BB
.AA..AA..AA..AA..AA..AA..AA..AA.     BB....BBBB....BBBB....BBBB....BB

CCCC........CCCCCCCC........CCCC     ..DDDD....DDDD....DDDD....DDDD..
..CCCC....CCCC....CCCC....CCCC..     ....DDDDDDDD........DDDDDDDD....
....CCCCCCCC........CCCCCCCC....     ..DDDD....DDDD....DDDD....DDDD..
..CCCC....CCCC....CCCC....CCCC..     DDDD........DDDDDDDD........DDDD
..CCCC....CCCC....CCCC....CCCC..     DDDD........DDDDDDDD........DDDD
..CCCC....CCCC....CCCC....CCCC..     DDDD........DDDDDDDD........DDDD
..CCCC....CCCC....CCCC....CCCC..     DDDD........DDDDDDDD........DDDD
..CCCC....CCCC....CCCC....CCCC..     DDDD........DDDDDDDD........DDDD

Pokiaľ sa zaujímame len o zvislé pásiky, tak sme je všetko super. Týmto spôsobom vieme robiť súvislé plochy tak, že nájdeme políčko s každou podmnožinou. Bohužiaľ v rohoch takéto zvislé patterny nie sú kompatibilné podobnými vodorovnými. Napríklad nesledujúce dva nepasujú:

AA..   B...
.AA.   BB.B
..AA   .BBB
.AA.   ..B.

Hoci tieto by pasovali (ak chcete hlbšie pochopiť, ktoré patterny pasujú a ktoré nie, spočítajte, na koľkých políčkach je \(\{\}\), \(\{A\}\), \(\{B\}\) a \(\{A,B\}\)):

AA..   ....
.AA.   BBBB
..AA   BBBB
.AA.   ....

Preto musíme patterny poohýbať, aby sa na žiadnom mieste nestretla zvislá “čapatá” vec s vodorovnou “čapatou” vecou. Inšpirujte sa nasledovnými obrázkami:

..A.............................     ...BBBBBBBBBBBBBBBBBBBBBBBBBBBBB
.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA     B.BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AA.AAAAAAAAAAAAAAAAAAAAAAAAAAAAA     BBB.............................
A...............................     .B..............................
A..............................A     .B............................B.
AA.AAAAAAAAAAAAAAAAAAAAAAAAAA.AA     BBB..........................BBB
.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.     B.BBBBBBBBBBBBBBBBBBBBBBBBBBBB.B
..A..........................A..     ...BBBBBBBBBBBBBBBBBBBBBBBBBB...
..A..........................A..     ...BBBBBBBBBBBBBBBBBBBBBBBBBB...
.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.     B.BBBBBBBBBBBBBBBBBBBBBBBBBBBB.B
AA.AAAAAAAAAAAAAAAAAAAAAAAAAA.AA     BBB..........................BBB
A..............................A     .B............................B.
...............................A     ..............................B.
AAAAAAAAAAAAAAAAAAAAAAAAAAAAA.AA     .............................BBB
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.     BBBBBBBBBBBBBBBBBBBBBBBBBBBBBB.B
.............................A..     BBBBBBBBBBBBBBBBBBBBBBBBBBBBB...

.CC..CC..CC.CC....CCCC....CCCC..     DD....DDDD...DD..DD..DD..DD..DD.
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD..DD....DDDD....DDDD..
.CC..CC..CC...CCCC....CCCC....CC     DD....DDDD...DD..DD..DD..DD..DD.
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     DD....DDDD....DDDD....DDDD....DD
CC....CCCC....CCCC...CC..CC..CC.     .DD..DD..DD..DD..DD...DDDD....DD
.CC..CC..CC..CC..CC..CC..CC..CC.     ..DDDD....DDDD....DD..DDDD....DD
..CCCC....CCCC....CC.CC..CC..CC.     .DD..DD..DD..DD..DD...DDDD....DD

Tieto patterny nazveme čapaté pásiky. Všimnime si, že sú to v skutočnosti stále naše pôvodné pásiky, ktoré sme trocha počapatili aby tvorili súvislú plochu. Už je to teda súvislé aj to pasuje, ale stále tomu niečo chýba. Veru, keď máme práve dva pásiky, nedajú sa sčapatiť tak, aby boli rohy rovné. Vzniklo by niečo takéto.

..A..........................A..    
.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.
AA.AAAAAAAAAAAAAAAAAAAAAAAAAA.AA
A..............................A
A..............................A
AA.AAAAAAAAAAAAAAAAAAAAAAAAAA.AA
.AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.
..A..........................A..

Preto namiesto zvislého dvojpásikového patternu a vodorovného dvojpásikového patternu vieme použiť takúto dvojicu patternov. Nazveme ich dvojité kríže.

....MMMM....MMMM................     ................NNNN....NNNN....
....MMMM....MMMMMMMMMMMMMMMMMMMM     NNNNNNNNNNNNNNNNNNNN....NNNN....
....MMMM....MMMM................     ................NNNN....NNNN....
....MMMM....MMMMMMMMMMMMMMMMMMMM     NNNNNNNNNNNNNNNNNNNN....NNNN....
MMMMMMMMMMMMMMMMMMMM....MMMM....     ....NNNN....NNNNNNNNNNNNNNNNNNNN
................MMMM....MMMM....     ....NNNN....NNNN................
MMMMMMMMMMMMMMMMMMMM....MMMM....     ....NNNN....NNNNNNNNNNNNNNNNNNNN
................MMMM....MMMM....     ....NNNN....NNNN................

Ktoré navyše pasujú s patternami takéhoto typu, nazvime ich postupne patterny typu A, B, C, D.

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA     ................................
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA     ................................
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA     BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA     BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
................................     BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
................................     BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
................................     ................................
................................     ................................

CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........
CCCCCCCCCCCCCCCC................     ........DDDDDDDDDDDDDDDD........

Občas však musíme použiť namiesto dvojitých krížov jednoité kríže alebo takéto miešané kríže:

....EEEE........   ........FFFF....   .G.G....   ....H.H.
....EEEEEEEEEEEE   FFFFFFFFFFFF....   .G.GGGGG   HHHHH.H.
....EEEE........   ........FFFF....   GGGGG.G.   .H.HHHHH
....EEEEEEEEEEEE   FFFFFFFFFFFF....   ....G.G.   .H.H....
EEEEEEEEEEEE....   ....FFFFFFFFFFFF   
........EEEE....   ....FFFF........   
EEEEEEEEEEEE....   ....FFFFFFFFFFFF   
........EEEE....   ....FFFF........

Avšak tu si treba dávať pozor, že v tom smere v ktorom je kríž jednoitý, nemôžeme použiť pattern s jedným stredným pásikom. Teda kríže E, F nie sú kompatibilné s patternom typu D a kríže G, H nie sú kompatibilné s patternom typu B.

Keď rozmery plochy sú \(2^r \times 2^s\), potrebujeme \(r+s\) patternov. Z nich \(2\) budú typu A, C. Potom \(2\lfloor\frac{r-2}{2}\rfloor\) bude vodorovných čapatých, \(2\lfloor\frac{s-2}{2}\rfloor\) bude zvislých a potom (podľa parity \(r\) a \(s\)) bude treba doplniť 1 až 2 patterny v každom rozmere. Keď dopĺňame 1, tak kríž má byť v tom smere jednoitý, keď 2 tak použijeme dvojitý kríž a k nemu pattern typu B resp. D.

Keď už ste videli všetky tieto obrázky, mali by ste byť schopní naprogramovať riešenie bez veľkých ťažkostí. Oplatí sa spraviť to. Ak chcete, môžete si vymyslieť aj úplne iné patterny.

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.