CSES - Datatähti 2015 loppu - Kartta
  • Time limit: 5.00 s
  • Memory limit: 128 MB

Aikaraja: 5 s

Vuosisatojen aikana merenpinta Uolevin asuinseudulla on kohonnut. Kun perinnepäivät koittivat, Uolevi pyydettiin pitämään esitelmä aiheesta.

Uolevilla on käytössä korkeuskartta seudusta, ja hän haluaa pystyä näyttämään jokaiselle korkeudelle x kuvan, jossa sinisellä on merkitty alueet, joiden korkeus on enintään x-1, ja vihreällä alueet, joiden korkeus on x tai enemmän.

Ongelmana on kuitenkin, että Uolevilla on käytössään vain dokumenttikamera, 40 kalvoa sekä vihreää ja sinistä läpinäkymätöntä maalia. Tehtäväsi on päättää, miten Uolevin tulisi maalata kalvot, jotta hän voi mille tahansa korkeudelle x muodostaa kalvoista oikeanlaisen kuvan.

Uolevi muodostaa kalvoista kuvan valitsemalla joukon kalvoja ja pinoamalla ne johonkin järjestykseen. Tämän jälkeen jokaisessa pisteessä näkyy väri, joka on mahdollisimman korkealla pinossa olevassa kalvossa kyseisessä pisteessä. Jos pisteen kohdalla missään kalvossa ei ole väriä, kuva on virheellinen.

Uolevi pinoaa kalvot tarkalleen päällekkäin eikä hän muuta niiden asentoa.

Syöte

Ensimmäisellä rivillä on kolme kokonaislukua: korkeuskartan korkeus n ja leveys m sekä suurin mahdollinen korkeus h.

Seuraavat n riviä sisältävät korkeuskartan: kukin rivi sisältää sen rivin korkeudet (m kokonaislukua väliltä 1\ldots h).

Tuloste

Ohjelmasi tulee tulostaa ensin, miltä kukin 40 kalvosta näyttää. Jokaista kalvoa kohden tulosteessa tulee olla n riviä, joilla on m merkkiä. Jokainen rivi koostuu merkeistä S (sininen), V (vihreä) ja L (läpinäkyvä). Kalvot on numeroitu kokonaisluvuin 1,2,\ldots,40.

Sitten ohjelman tulee tulostaa h riviä: jokaiselle korkeudelle x = 1, 2, \ldots, h jokin tapa esittää kuva kalvojen avulla. Rivin alussa on käytettävien kalvojen määrä, minkä jälkeen rivillä on kalvojen numerot järjestyksessä pinon pohjalta ylös. Samaa kalvoa saa käyttää vain kerran.

Esimerkki

Syöte:

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

Tuloste:

VVVVV
VVVVV
VVVVV
SSLSL
LSSSL
SSLSL
LLSLS
LLLLL
LLLLL
LLLLL
SLLLS
LLLLS
LLLLL
LLLLL
LLSLL
...
1 1
2 1 2
3 1 2 3
4 1 2 3 4

Merkinnän ... kohdalle kuuluu 35 mitä tahansa kalvon kuvausta (niitä ei tarvita kuvien muodostamisessa tässä syötteessä).

Rajat

  • 1 \leq n, m \leq 100

Osatehtävä 1 (12 pistettä)

1 \leq h \leq 40

Osatehtävä 2 (27 pistettä)

1 \leq h \leq 200

Osatehtävä 3 (15 pistettä)

1 \leq h \leq 1000

Osatehtävä 4 (46 pistettä)

1 \leq h \leq 10^4