Fişierul intrare/ieşire:cristale.in, cristale.outSursăConcursul National Urmasii lui Moisil 2012, Clasa a 9-a
AutorVlad StoianAdăugată deandrici_cezarAndrici Cezar andrici_cezar
Timp execuţie pe test0.1 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Cristale

Pentru a adera la cultul shaman al vechilor vindecători, pretendenţii trebuie să treacă testul cu mai multe probe pregătit de Marea Shamaniţă Bulbuka. Pretendentului i se arată trei tipuri de cristale cu o proprietate cu totul şi cu totul nemaivăzută: dacă oricare două cristale de tipuri diferite sunt combinate, acestea se vor transforma ireversibil într-un singur cristal de tipul al treilea (de exemplu, având cristale de tipurile x y z, dacă sunt alăturate x şi z, se transformă în y). Testul constă din P probe pe care trebuie să le parcurgă în ordine. La fiecare probă i se oferă câte un şirag format din mai multe cristale din cele trei tipuri, într-o ordine specială şi bine gândită. Pretendentul trebuie să folosească proprietatea ce i-a fost dezvăluită pentru a determina numărul minim de cristale la care se poate ajunge în şiragul dat. El poate transforma oricare două cristale alăturate, de tipuri diferite, înlocuindu-le în şirag cu cristalul nou obţinut.

Cerinţă

Scrieţi un program care să rezolve toate probele din testul Shamaniţei Bulbuka.

Date de intrare

Pe prima linie a fişierului cristale.in se află trei caractere diferite separate prin câte un spaţiu, reprezentând cele trei tipuri de cristale. Pe a doua linie se află numărul P de probe din care este format testul. Fiecare dintre următoarele P linii conţine: n-numărul de cristale din şirag urmat de un spaţiu, apoi de o succesiune de n caractere reprezentând cristalele din şirag, în ordinea dată.

Date de ieşire

În fişierul cristale.out se va scrie pe fiecare dintre cele P linii câte un număr, reprezentând numărul minim de cristale la care se poate reduce şiragul respectiv.

Restricţii

  • 1 ≤ P ≤ 1000
  • numărul de cristale dintr-un şirag este nenul şi nu va depăşi 100
  • şiragurile sunt liniare

Exemplu

cristale.incristale.out
a b c
3
3 cab
4 bcab
5 ccccc
2
1
5

Explicaţie

cab -> bb sau cc
bcab -> aab -> ac -> b
ccccc nu se mai poate reduce

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content