Fişierul intrare/ieşire:joben.in, joben.outSursăAlgoritmiada 2010, Runda 3
AutorPaul-Dan BaltescuAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.125 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Joben

Marcel are T perechi de şiruri ce conţin litere mici ale alfabetului englez. El mai are la dispoziţie un joben magic care poate efectua una din următoarele două operaţii:

  • permutare: se permută caracterele şirului introdus în joben. De exemplu, dacă este introdus şirul abb, acesta poate deveni abb, bab sau bba.
  • transformare: pentru fiecare caracter din mulţimea {'a', ..., 'z'} se alege un caracter tot din mulţimea {'a', ..., 'z'}, astfel încât oricăror două litere diferite să le corespundă caractere diferite. Fiecare caracter din şirul introdus în joben este înlocuit cu corespondentul său. De exemplu, transformările abcca -> zdffz şi rdbarb -> rbdkrd sunt valide, în timp ce transformările abcca -> zdfgz şi abcde -> ghhij nu sunt valide.

Cerinţă

Pentru fiecare din cele T perechi de şiruri să se precizeze dacă al doilea şir poate fi obţinut din primul şir efectuând oricâte operaţii cu jobenul.

Date de intrare

Fişierul de intrare joben.in conţine pe prima linie numărul întreg T. Pe următoarele 2*T linii sunt descrise perechile de şiruri, câte un şir pe linie. Pentru orice 1 ≤ i ≤ T, şirurile ce alcătuiesc perechea i se află pe liniile 2*i şi 2*i+1 din fişier.

Date de ieşire

Fişierul de ieşire joben.out va conţine T linii. Pe linia i (1 ≤ i ≤ T) va fi scris mesajul DA dacă pentru a i-a pereche cel de-al doilea şir poate fi obţinut din primul şir după oricâte operaţii cu jobenul, respectiv NU în caz contrar.

Restricţii

  • 1 ≤ T ≤ 100
  • Lungimea oricărui şir nu depăşeşte 100 000 de caractere.
  • Două şiruri ce aparţin aceleiaşi perechi au acelaşi număr de caractere.

Exemplu

joben.injoben.out
2
esarfa
iepure
morcov
pepene
DA
NU

Explicaţie

Pe primul test, o soluţie posibilă este esarfa -> aserfe -> aesfre -> iepure, constând în două transformări şi o permutare. Pentru al doilea test, nu există nicio secvenţă de operaţii care să transforme şirul morcov în şirul pepene.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content