- 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ä 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ä.