Code Submission Evaluation System Login

Datatähti 2019 loppu

Start:2019-01-17 12:00:00
End:2019-01-17 17:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - Datatähti 2019 loppu - LuokittelijaCSES - Luokittelija

Luokittelija

Time limit:1.00 s
Memory limit:512 MB

Tässä tehtävässä sinun tulee rakentaa luokittelija, jonka toiminta perustuu sääntölistaan. Luokittelijalle annetaan syötteenä merkkijono, jonka jokainen merkki on 0 tai 1. Luokittelija käsittelee merkkijonon sääntölistan avulla ja antaa vastauksena "kyllä" tai "ei" riippuen siitä, onko merkkijonolla haluttu ominaisuus.

Sääntölista muodostuu säännöistä muotoa $x$ → $y$, missä $x$ on vasen osa ja $y$ on oikea osa. Säännöissä voi esiintyä merkkejä 0 tai 1 sekä apumerkkejä A–Z. Lisäksi oikea osa voi olla _, mikä tarkoittaa tyhjää merkkijonoa.

Luokittelijan muistissa on merkkijono, joka on aluksi syötteenä annettu merkkijono. Joka askeleella luokittelija etsii listan ensimmäisen säännön, jonka vasen osa esiintyy merkkijonossa, ja korvaa vasemman osan ensimmäisen esiintymän oikealla osalla. Luokittelija toistaa samaa, kunnes listalla ei ole enää mitään sääntöä, jota voisi soveltaa. Jos lopullinen merkkijono on tyhjä, vastaus on "kyllä", ja muuten "ei".

Esimerkiksi seuraava luokittelija tarkastaa, onko merkkijonossa tasan yksi nolla. Ensimmäisellä rivillä on sääntöjen määrä ja muut rivit kuvaavat säännöt.
5
B1 -> B
B -> _
10 -> 01
00 -> A
0 -> B
Esimerkiksi jos syöte on 1101, sen käsittely etenee näin: 1101 → 1011 → 0111 → B111 → B11 → B1 → B → _. Merkkijono on tyhjä, joten vastaus on "kyllä".

Jos taas syöte on 1010, sen käsittely etenee näin: 1010 → 0110 → 0101 → 0011 → A11. Merkkijono ei ole tyhjä, joten vastaus on "ei".

Tehtävä

Suunnittele luokittelija, joka tarkastaa, voiko merkkijonon muodostaa toistamalla $k$ kertaa samaa merkkijonoa. Esimerkiksi jos $k=2$, merkkijonolle 0101 vastaus on "kyllä" ja merkkijonolle 0100 vastaus on "ei".

Ohjelmasi syötteenä on yksi rivi, jossa on luku $k$, ja sen tulee tulostaa luokittelijan sääntölista aiemman esimerkin mukaisesti.

Rajoitukset
Osatehtävä 1 (19 pistettä)
Osatehtävä 2 (24 pistettä)
Osatehtävä 3 (27 pistettä)
Osatehtävä 4 (30 pistettä)