Kanava

• Language:
  enfi
• 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ä $n$ 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 $t$, joka on joko $1$, jos halutaan koodata sanoja, tai $2$, jos halutaan purkaa lähetys.

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

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

Tuloste

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

Jos $t=2$, tulosta ensimmäiselle riville kokonaisluku $n$: kuinka monta sanaa lähetys sisältää. Tämän jälkeen tulosta lähetyksestä puretut $n$ 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 = 520$
  
• $1 \le n \le 1000$
  
• Jokaisen sanan pituus on korkeintaan $10$.
  

Arvostelu

Ohjelmallesi annetaan $520$ sanaa koodattavaksi. Eri pituisia sanoja $1$–$10$ on kutakin $52$ 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=2860$ alkuperäisten sanojen yhteispituus ja $b$ koodattujen sanojen symbolien määrä yhteensä, sisältäen kaikki tauot. Ansaitsemasi pistemäärä on $\lceil 1000(a/b - 1/6) \rceil$, kuitenkin korkeintaan $100$ pistettä. Merkintä $\lceil x \rceil$ tarkoittaa pyöristystä ylöspäin.

Jos esimerkiksi yksi koodattu symboli esittää keskimäärin $0.216$ sanan merkkiä, saat $50$ pistettä.