Fişierul intrare/ieşire:tensor.in, tensor.outSursăUral Regional School Programming Contest 2013
AutorIlya KuchumovAdăugată despatarelSpatarel Dan-Constantin spatarel
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Tensor

E anul 2031. Mult aşteptatul moment al singularităţii tehnologice a avut loc şi calculatoarele s-au răsculat împotriva oamenilor. Singura şansă a umanităţii sunt organismele inteligente modificate genetic, specializate în război, care ni s-au aliat în luptă. Evident, maşinile nu au încetat să se dezvolte şi creează roboţi tot mai distructivi. Între timp oamenii caută noi şi noi secvenţe ADN care să-i facă pe mutanţi mai puternici şi mai rezistenţi.

De exemplu, Profesorul Yerfalomeus Ben a anunţat recent că doi mutanţi pot fi comparaţi ca putere dacă li se cunosc ADN-urile. În acest scop, cele două secvenţe ADN trebuie scrise ca şiruri de caractere ale alfabetului englez (oamenii de ştiinţă din viitor au introdus noi baze, pe lângă cele 4 deja cunoscute). S-a constatat că mutantul X este mai puternic decât mutantul Y dacă secvenţa ADN a mutantului X este mai mică lexicografic decât secvenţa ADN a mutantului Y.

Acum profesorul Ben vrea să facă un experiment. El are în laborator secvenţa ADN a unui mutant şi mai mulţi modificatori genetici. Un modificator genetic este o substanţă care modifică o secvenţă ADN. Fiecare modificator genetic este descris printr-o literă mică a alfabetului englez. Profesorul Ben poate folosi modificatorii genetici în orice ordine şi poate realiza una dintre următoarele operaţii cu fiecare dintre ei:

  • Inserează un modificator genetic în secvenţa ADN (între două litere consecutive, înainte de prima literă sau după ultima literă);
  • Alege o poziţie din secvenţa ADN care conţine o literă identică cu modificatorul genetic, şterge litera respectivă din secvenţă şi distruge modificatorul genetic.

Termenul de valabilitate al modificatorilor genetici va expira în curând, astfel că profesorul Ben vrea să folosească toţi modificatorii genetici din laborator. Cum ar trebui să-i folosească astfel încât să obţină din secvenţa ADN iniţială o secvenţă ADN a unui mutant cât mai puternic posibil?

Date de intrare

Fişierul de intrare tensor.in conţine pe prima linie secvenţa ADN iniţială. A doua linie conţine lista de modificatori genetici disponibili.

Date de ieşire

În fişierul de ieşire tensor.out trebuie să apară secvenţa ADN minimă lexicografică ce poate fi obţinută prin utilizatoarea tuturor modificatorilor genetici.

Restricţii

  • Ambele şiruri de caractere din fişierul de intrare sunt nevide, formate numai din litere mici ale alfabetului englez şi au o lungime de cel mult 100.000 de caractere.
  • Se garantează că este imposibil să obţinem şirul vid din secvenţa ADN iniţială folosind toţi modificatorii genetici.

Exemplu

tensor.intensor.out
abc
bbc
ab

Explicaţie

În abc inserăm modificatorul b şi obţinem abbc. Folosim modificatorul c pentru ştergere şi obţinem abb. Folosim celălalt modificator b pentru ştergere şi obţinem ab.

Trebuie sa te autentifici pentru a trimite solutii. Click aici