Državna razina / Primjena algoritama OŠ 2022. / Osnovna škola (7. razred) - 2. zadatak

Zaslon jako starog Mirkovog računala može prikazati NxM znakova raspoređenih u N redaka i M stupaca. Mirko je na zaslonu otvorio nekoliko prozora. Prozor iz tog vremena lako prepoznajemo jer su mu rubovi opisani znakom "#", unutrašnjost ispunjena znakovima ".", a u unutrašnjosti se mogu naći i mala slova engleske abecede. Primjer nekoliko prozora:

<h8>######### ############### ###</h8>

...bob.......# #..abc........# #.# #a

.graditelj...# #.............# #.#

.............# #......def....#

<h8>######### #.............</h8>

.............

.............

.............

<h8>#</h8>

Otvoreni prozori se međusobno ne preklapaju, tj. u potpunosti se vidi unutrašnjost i svi rubovi svih prozora. Svaki prozor je takvih dimenzija da unutar njega stane barem jedan znak. Površina prozora određuje se kao broj znakova koji bi se mogao napisati unutar njega. Površine prozora iz primjera su redom: 39, 91, 2 i 1. A sada problemi. Prvi! Mirko je primijetio da su svi otvoreni prozori na zaslonu različitih površina. Zanima ga koliko je uopće otvorenih prozora te kolike su površine tih prozora. Drugi! Zanima ga kako će zaslon izgledati ako se prozori rasporede na način da se i dalje ne preklapaju i da onaj s najvećom površinom bude u gornjem lijevom kutu, da gornji lijevi kut drugog po redu s najvećom površinom bude što je više moguće, a ako u obzir dolazi više pozicija tada se odabire ona najljevija. Postupak se ponavlja sve do prozora najmanje površine.

Ulazni podaci

U prvom su retku prirodni brojevi N (1 ≤ N ≤ 50) i M (1 ≤ M ≤ 50), dimenzije zaslona Mirkovog računala. U sljedećih N redaka nalazi se po M znakova (znak "#", mala slova engleske abecede ili znak '.', tj. točka) koji opisuju izgled ekrana. Testni primjeri će biti takvi da će uvijek biti moguće rasporediti prozore na opisani način.

Izlazni podaci

U prvom redak ispiši prirodan broj B, broj prozora na ekranu. U drugi redak ispiši B prirodnih brojeva, površine prozora na ekranu, redom od najmanje do najveće. U sljedećih N redaka ispiši po M znakova, izgled zaslona Mirkovog računala nakon željenog razmještaja prozora.

Bodovanje

Točan ispis prvog retka vrijedi jedan bod, točan ispis drugog retka još jedan bod, a točan ispis izgleda ekrana nakon razmještaja tri boda po testnom primjeru. U testnim primjerima ukupno vrijednima 10 bodova na ekranu će biti samo jedan prozor. U testnim primjerima ukupno vrijednima dodatnih 10 bodova na ekranu će biti dva prozora. U testnim primjerima ukupno vrijednima dodatnih 10 bodova prozori na ekranu neće se dodirivati. U testnim primjerima ukupno vrijednima dodatnih 10 bodova unutar niti jednog prozora neće biti malih slova engleske abecede.

Primjer zadatka

Ulaz

8 8
#######.
#criti#.
#rsc..#.
#j..v.#.
#######.
........
........
........

Izlaz

izlaz
1
15
#######.
#criti#.
#rsc..#.
#j..v.#.
#######.
........
........
........

---

Ulaz

12 13
.....#####...
.....#...#...
.....#...#...
.....#...#...
.....#####...
.............
#####........
#...#........
#...#........
#...#........
#...#........
#####........

Izlaz

2
9 12
##########...
#...##...#...
#...##...#...
#...##...#...
#...######...
#####........
.............
.............
.............
.............
.............
.............

Ulaz

15 15
#############..
#...........#..
#...........#..
#...........#..
#############..
###############
#.......##....#
#.......##....#
#.......##....#
##########....#
#####....#....#
#.p.#....#....#
#.ps#....#....#
#...#....######
#####..........

Izlaz

4
9 21 28 33
#############..
#...........#..
#...........#..
#...........#..
#############..
###############
#....##.......#
#....##.......#
#....##.......#
#....##########
#....######....
#....##.p.#....
#....##.ps#....
#######...#....
......#####....

Opis prvog probnog primjera:

Na ekranu je samo jedan prozor, njegova površina je 15 i već je smješten na poziciju na kojoj ga Mirko želi vidjeti.

Opis drugog probnog primjera:

Na ekranu su 2 prozora. Površina jednog je 9, a drugog 12.