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

• Sääntölistalla saa olla enintään 100 sääntöä.
• Jokaisessa säännössä vasemman osan pituus ja oikean osan pituus saa olla enintään 10 merkkiä.
• Kun luokittelijaasi testataan, jokaisessa testissä merkkijonon pituus on enintään 100 merkkiä.
• Luokittelija saa suorittaa merkkijonon käsittelyssä enintään 10000 askelta.
• Luokittelijan muistissa olevassa merkkijonossa saa olla joka vaiheessa enintään 1000 merkkiä.

Osatehtävä 1 (19 pistettä)

• k=2

Osatehtävä 2 (24 pistettä)

• k=3

Osatehtävä 3 (27 pistettä)

• k=4

Osatehtävä 4 (30 pistettä)

• k=5