ŽUPANIJSKO NATJECANJE 2014. / Srednja škola, II. podskupina (3. i 4. razred) - 1. zadatak

Goran ima mali zaslon, a velike ambicije. U jednom trenutku shvatio je da se ne uspijeva snaći u velikom broju istovremeno otvorenih prozora te ih je odlučio rasporediti tako da se nijedna dva prozora ne preklapaju.

Kako je svaki prozor već smanjio na najmanju moguću veličinu, odlučio je koristi jednostavan postupak. Na početku potpuno očisti zaslon, a zatim jedan po jedan prozor uzima i pokušava ga na ekranu smjestiti tako da je prozor u potpunosti unutar zaslona te se ne preklapa s nijednim ranije smještenim prozorom. Kako bi sačuvao mjesto, pokušava gornji lijevi kut prozora smjestiti na što višu poziciju, a ukoliko postoji više takvih pozicija na istoj visini, Goran odabire onu koja se nalazi najviše lijevo. Jednom kada smjesti određeni prozor, taj prozor više ne pomiče.

+---+ 
|###| 
+---+

Slika \(1\): Prozor dimenzija \(3\times5\)

Napišite program koji će pronaći konačan raspored prozora na zaslonu. Goranov zaslon možemo zamisliti kao kvadratnu mrežu koja se sastoji od \(R\) redaka te \(S\) stupaca. Svaki jedinični kvadratić u mreži je na početku prazan, što se označava znakom . (točka). Dobiveni raspored prozora potrebno je prikazati na zaslonu korištenjem znakova #, +, | i -, gdje znak # koristimo kako bismo prikazali unutrašnjost prozora, dok se preostala tri znaka nalaze na rubovima, kao na Slici \(1\). Svi prozori u zadatku sastojat će se od barem tri retka i tri stupca.

Ulazni podaci

U prvom redu nalaze se tri prirodna broja \(R\), \(S\) i \(K\) \((1 \leq R, S, K \leq 30)\), broj redaka i stupaca od kojih se sastoji zaslon te broj prozora koje je potrebno razmjestiti.

U sljedećih \(K\) redaka nalaze se parovi prirodnih brojeva \(A_k\), \(B_k\) \((3 \leq A_k, B_k \leq 30)\), dimenzije \(k\)-tog prozora, \(A_k\) je broj redaka a \(B_k\) broj stupaca od kojih se prozor sastoji. Prozore je potrebno razmjestiti poretkom kojim su dani u ulazu, a ulazni podaci bit će takvi da je opisanim Goranovim postupkom uvijek moguće razmjestiti sve prozore.

Izlazni podaci

Potrebno je ispisati \(R\) redova, u svaki red točno \(S\) znakova – izgled zaslona nakon što su svi prozori razmješteni, prema uputama u tekstu zadatka.

Primjeri test podataka

Ulaz

10 10 4
3 3
4 4
5 4
5 5

Izlaz

+-++--+...
|#||##|...
+-+|##|...
...+--+...
+--++---+.
|##||###|.
|##||###|.
|##||###|.
+--++---+.
..........

Ulaz

14 18 5
10 4
4 10
10 4
4 15
6 6

Izlaz

+--++--------++--+
|##||########||##|
|##||########||##|
|##|+--------+|##|
|##|+----+....|##|
|##||####|....|##|
|##||####|....|##|
|##||####|....|##|
|##||####|....|##|
+--++----+....+--+
+-------------+...
|#############|...
|#############|...
+-------------+...

Ulaz

20 20 16
4 5
8 4
4 7
6 4
4 7
5 4
3 5
3 8
6 7
5 4
6 5
6 4
3 6
3 8
3 4
4 3

Izlaz

+---++--++-----++--+
|###||##||#####||##|
|###||##||#####||##|
+---+|##|+-----+|##|
+--+.|##|+-----+|##|
|##|.|##||#####|+--+
|##|.|##||#####|.+-+
|##|.+--++-----+.|#|
+--++---++------+|#|
....|###||######|+-+
....+---++------+...
+-----++--++---++--+
|#####||##||###||##|
|#####||##||###||##|
|#####||##||###||##|
|#####|+--+|###||##|
+-----+....+---++--+
+----++------++--+..
|####||######||##|..
+----++------++--+..