ACM RTK - 2. skupina

Silhuete

Neko mesto ima obliko pravokotne mreže, razdeljene na w × h parcel (w stolpcev, h vrstic). Na vsaki parceli stoji stolpnica, ki ima obliko kvadra. V tlorisu so si vsi ti kvadri enaki, razlikujejo pa se po višini; na parceli v r-ti vrstici in c-tem stolpcu stoji nebotičnik z višino a_rc (to je celo število, večje od 0).

Mesto si (recimo s fotoaparatom) ”ogledamo“ od spredaj in od strani. Na tak način dobimo samo podatek o najvišji stolpnici v vsaki vrstici in vsakem stolpcu. Recimo, da je x_c višina najvišje stolpnice v c-tem stolpcu, y_r pa višina najvišje stolpnice v r-ti vrstici. Iz teh podatkov (torej x₁, x₂, ..., x_w in y₁, y₂, ..., y_h) sicer v splošnem ne moremo natančno določiti višin posameznih stolpnic (torej posameznih vrednosti a_rc), lahko pa preverimo, ali podatki sploh predstavljajo možno konfiguracijo in izračunamo eno od možnih postavitev.

Napiši program, ki prebere vhodne podatke in izpiše eno od možnih postavitev ali pa ”taka postavitev ne obstaja“, če podatki niso veljavni. Vhodni podatki so zapisani v treh vrsticah in sicer takole:

w h

x₁ x₂ ... x_w

y₁ y₂ ... y_h

Tvoj program jih lahko bere s standardnega vhoda ali pa iz datoteke silhuete.txt (kar ti je lažje). Predpostavi, da velja w ≤ 1000 in h ≤ 1000.

Primer: recimo, da imamo mrežo 4 × 3 stolpnic z višinami

Maksimalne višine po stolpcih so torej (od leve proti desni) 9, 3, 6, 9; po vrsticah pa (od zgoraj navzdol) 9, 6, 9. Program bi v tem primeru kot vhodne podatke dobil:

4 3
9 3 6 9
9 6 9

Nekaj možnih razporedov pri teh vhodnih podatkih (program bi torej lahko izpisal katerega koli izmed njih, obstaja pa še veliko drugih, ki bi bili prav tako dobri):

9 2 3 2     9 3 6 9     9 1 2 1     4 3 5 9
2 1 6 1     5 3 6 6     2 3 1 6     4 3 6 5
6 3 6 9     9 2 6 9     9 1 6 9     9 2 2 9

Primer vhodnih podatkov, pri katerih veljavna predstavitev ne obstaja:

2 2
4 2
1 1