CSES - Datatähti 2022 loppu - Kanava
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Kommunikaatiokanavan kautta voidaan lähettää kolmenlaisia symboleja: lyhyt (0), pitkä (1), sekä tauko (_). Jokainen lähetettävä sana tulee koodata näiden symbolien avulla.

Lähetystä vastaanotettaessa alussa ja lopussa olevia taukoja ei tunnisteta, eikä eri pituisia taukoja voida erottaa toisistaan. Siispä jos kanavaa pitkin lähetetään esimerkiksi sarja __110__01_, vastaanottaja näkee sarjan 110_01.

Lähetys koostetaan yhdistämällä nn sanan koodaukset peräkkäin. Sanat voivat olla missä tahansa järjestyksessä, ja sama sana voi esiintyä lähetyksessä useasti. Sanojen väleille ei tule ylimääräisiä taukoja.

Suunnittele ohjelma, joka koodaa sanoja kanavaa varten mahdollisimman lyhyiksi sarjoiksi ja purkaa vastaanotetun lähetyksen sisällön.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku tt, joka on joko 11, jos halutaan koodata sanoja, tai 22, jos halutaan purkaa lähetys.

Jos t=1t=1, niin toisella rivillä on kokonaisluku kk: koodattavien sanojen määrä. Seuraavat kk riviä sisältävät kukin sanan, joka koostuu merkeistä a–z.

Jos t=2t=2, niin toisella rivillä on merkkijono, joka kuvaa vastaanotetun lähetyksen merkeillä 0, 1 ja _.

Tuloste

Jos t=1t=1, tulosta omalle rivilleen jokaista sanaa vastaava koodaus käyttäen merkkejä 0, 1 ja _.

Jos t=2t=2, tulosta ensimmäiselle riville kokonaisluku nn: kuinka monta sanaa lähetys sisältää. Tämän jälkeen tulosta lähetyksestä puretut nn sanaa kukin omalle rivilleen.

Esimerkki (koodaus)

Syöte:

1
2
abc
sos

Tuloste:

_1__00
000111000

Esimerkki (purku)

Syöte:

2
1_00000111000_1_00

Tuloste:

3
abc
sos
abc

Rajat

  • k=520k = 520
  • 1n10001 \le n \le 1000
  • Jokaisen sanan pituus on korkeintaan 1010.

Arvostelu

Ohjelmallesi annetaan 520520 sanaa koodattavaksi. Eri pituisia sanoja 111010 on kutakin 5252 kappaletta. Syöte on valittu satunnaisesti niin, että jokaista merkkiä on yhteensä sama määrä. Jos sanoista muodostettu lähetys purkautuu alkuperäisten sanojen mukaisesti oikein, saat tehtävästä pisteitä seuraavasti:

Olkoon a=2860a=2860 alkuperäisten sanojen yhteispituus ja bb koodattujen sanojen symbolien määrä yhteensä, sisältäen kaikki tauot. Ansaitsemasi pistemäärä on 1000(a/b1/6)\lceil 1000(a/b - 1/6) \rceil, kuitenkin korkeintaan 100100 pistettä. Merkintä x\lceil x \rceil tarkoittaa pyöristystä ylöspäin.

Jos esimerkiksi yksi koodattu symboli esittää keskimäärin 0.2160.216 sanan merkkiä, saat 5050 pistettä.