Cadenes d'ADN X98001
Una cadena d’ADN es pot veure com dues paraules de la mateixa longitud formades amb els símbols ’A’, ’C’, ’G’, ’T’ i posades una a sobre de l’altra de manera que, per a qualsevol posició, es compleix que:
- en una paraula hi apareix ’A’ si i només si en l’altra hi apareix ’T’; i
- en una paraula hi apareix ’C’ si i només si en l’altra hi apareix ’G’.
Per exemple,
| T C |
| A G |
seria una cadena d’ADN, mentre que
| T A |
| A C |
| T T |
| A C |
| C G |
| A C |
no ho serien.
Imaginem-nos que ens donen una cadena d’ADN incompleta, en què alguns dels símbols encara estan per determinar. De quines maneres es pot completar perquè sigui una cadena d’ADN?
Entrada
L’entrada consisteix en diversos casos. Cada cas comença amb un natural n, la longitud de les paraules. A la línia següent vénen n símbols ’A’, ’C’, ’G’, ’T’ o ’.’, sense espais en blanc entremig, corresponents a la primera paraula de la cadena d’ADN incompleta. A continuació a la línia següent vénen n símbols més ’A’, ’C’, ’G’, ’T’ o ’.’, sense espais en blanc entremig, corresponents a la segona paraula. Els punts ’.’ indiquen un símbol per determinar.
Sortida
Per a cada cas, escriviu totes les cadenes d’ADN que es poden formar, ordenades de manera que les primeres paraules de les cadenes segueixin l’ordre lexicogràfic. Per a cada cadena, escriviu les dues paraules en línies diferents, seguides d’una línia en blanc. Escriviu també una línia amb 10 guions després de cada cas.
Observació
Com es pot veure en els jocs de proves públics, és possible que algun cas no admeti cap solució.
Input
1 . . 2 T. .. 3 A.. ... 3 A.. C..
Output
A T C G G C T A ---------- TA AT TC AG TG AC TT AA ---------- AAA TTT AAC TTG AAG TTC AAT TTA ACA TGT ACC TGG ACG TGC ACT TGA AGA TCT AGC TCG AGG TCC AGT TCA ATA TAT ATC TAG ATG TAC ATT TAA ---------- ----------
- Author
- Enric Rodriguez
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++