Les granotes cantores del Titicaca


Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Bucles simples, Simple Math
Category
Codejam

El 1984, la biòloga peruana María Ortiz va descobrir un fet sorprenent sobre les granotes que habiten el llac Titicaca, a la regió de Cusco. Les granotes cantores del Titicaca es coneixen perquè, al contrari que la major part de granotes del món, rauquen utilitzant patrons de diversos sons, que acaben formant paraules, com ara Titiqaqa, d’on prové el nom del llac. Doncs bé, la doctora María Ortiz va ser la primera persona al món que desxifrà els patrons que utilitzen les granotes cantores del Titicaca.

Les granotes parteixen d’un conjunt de sons que poden fer, i canten sempre seguint un ordre, mai dues a la vegada. La primera granota emet el primer dels sons possibles. A partir d’aquí, es pot determinar els sons que faran la resta de granotes segons les següents regles:

  • Si la granota ocupa una posició parell, repetirà el so emès per la granota anterior.
  • Una granota que ocupi una posició senar evitarà repetir els sons anteriors. Cada cop que una granota emet un so, aquest queda descartat. Quan tots els sons han estat emesos, tots tornen a estar disponibles.
  • Una granota que ocupa una posició senar, per triar el so que emet, avançarà en la llista de sons tantes posicions com granotes quedin per cantar en aquella ronda. Si cau a un so que s’ha descartat, seguirà avançant per la llista fins a trobar-ne un que estigui disponible.
  • Quan totes les granotes han cantat, torna a començar la primera, seguint les mateixes regles. El cant acaba quan coincideix que totes les granotes han cantat el mateix nombre de vegades, i tots els sons tornen a estar disponibles.

Entrada

L'entrada sempre contindrà dues línies. La primera línia indica la quantitat de granotes que hi ha (sempre n’hi ha almenys una), i la segona línia, la llista de sons disponibles, separats per espai (sempre hi ha almenys un so).

Sortida

La sortida consisteix en la seqüència de sons que pronunciaran les granotes.

Exemple d'Entrada

2
Ti Qa
5
Ti Qa
3
Ti Qa Re Mo Gru

Exemple de Sortida

Ti Ti Qa Qa
Ti Ti Qa Qa Ti Qa Qa Ti Ti Qa
Ti Ti Qa Gru Gru Re Mo Mo Gru Re Re Mo Qa Qa Ti

Explicació de l'exemple

  • Primera granota: primer dels sons possibles – Ti
  • Segona granota: repeteix – Ti
  • Tercera granota: avança una posició - Qa
  • Primera granota: avança tres posicions - Gru
  • Segona granota: repeteix - Gru
  • Tercera granota: avança una posició, cau a Ti, però Ti i Qa ja s’han usat – Re
  • Primera granota: avança tres posicions, cau a Ti, però Ti, Qa i Re s’han usat – Mo
  • Segona granota: repeteix – Mo
  • Tercera granota: avança una posició, tots els sons tornen a estar disponibles – Gru
  • Primera granota: avança 3 – Re
  • Segona granota: repeteix – Re
  • Tercera granota: avança 1 – Mo
  • Primera granota: avança 3 – Qa
  • Segona granota: repeteix – Qa
  • Tercera granota: avança 1, cau a Re, però Re, Mo, Gru s’han usat – Ti

Acaba el programa perquè totes les granotes han cantat 5 vegades, i en aquests moments tots els sons tornen a estar disponibles.


Comments

There are no comments at the moment.