Rezolvare PBinfo #4609

Se consideră o pereche de șiruri de caractere, 𝑆 și 𝑇 , de lungime 𝑛, respectiv 𝑚, formate exclusiv din litere mici ale alfabetului englez. Pozițiile literelor sunt numerotate în șir începând de la 1.

Sunt două tipuri de operații ce se pot efectua asupra șirului 𝑇:

• 1 𝑝: se șterge litera de pe poziția 𝑝;
• 2 𝑠𝑡 𝑑𝑟 (cu 𝑠𝑡 ≤ 𝑑𝑟): se sortează crescător (alfabetic) literele din subsecvența ce corespunde intervalului de poziții [𝑠𝑡, 𝑑𝑟];

unde 𝑝, 𝑠𝑡 și 𝑑𝑟 sunt poziții ale unor litere din șirul 𝑇.

Inițial, toate literele șirului 𝑇 sunt necolorate. O operație de tip 2 poate fi realizată doar dacă toate literele din subsecvența corespunzătoare intervalului de poziții [𝑠𝑡,𝑑𝑟] sunt necolorate. După efectuarea sortării, toate literele din această subsecvență devin colorate.

Cerința

Pentru fiecare dintre perechile de șiruri de tipul 𝑆 și 𝑇 date:

1. Să se afișeze literele distincte care apar în cel puțin unul dintre șiruri și, pentru fiecare dintre acestea, sim-
   bolul șirului (literele 𝑆 sau 𝑇) în care apare de mai multe ori. În caz de egalitate, se alege șirul 𝑇.
2. Să se determine o succesiune de operații de tipul 1 și/sau 2 ce pot fi aplicate șirului 𝑇, care să îl transforme
   într-un șir egal cu 𝑆. Să se afișeze DA în cazul în care există o astfel de succesiune de operații, sau NU în
   caz contrar.

Date de intrare

Fișierul de intrare opsir.in conține pe prima linie numărul natural 𝑐, reprezentând cerința care trebuie rezolvată
(1 sau 2) pentru fiecare dintre perechile de șiruri date.

Pe a doua linie a fișierului se găsește numărul natural 𝑘, ce reprezintă numărul de teste. Fiecare test cuprinde datele specifice pentru o pereche de șiruri de tipul celei precizate în enunț, date care se găsesc pe câte trei linii în fișier, astfel: pe prima linie 𝑛 și 𝑚, în această ordine, cu semnificația din enunț, pe a doua linie șirul 𝑆, iar pe a treia linie șirul 𝑇.

Date de ieșire

Pentru 𝑐 = 1, fișierul de ieșire opsir.out va conține, pentru fiecare test, câte un număr natural 𝑛𝑟, ce reprezintă
numărul de litere distincte ce apar în cel puțin unul dintre șiruri, iar pe următoarele 𝑛𝑟 linii, câte o astfel de litera, precum și litera mare 𝑆 sau 𝑇, corespunzătoare șirului în care apare de mai multe ori. Literele mici vor fi afișate în ordine alfabetică.

Pentru 𝑐 = 2, fișierul de ieșire opsir.out va conține 𝑘 linii, pe fiecare linie aflându-se răspunsul (DA sau NU) corespunzător câte unui test, în ordinea în care acestea se găsesc în fișierul de intrare.

Restricții și precizări

• 1 ≤ 𝑘 ≤ 100
• 1 ≤ 𝑛 ≤ 𝑚 ≤ 200 000
• Suma lungimilor șirurilor de tip 𝑆 din cele 𝑘 teste nu depășește 200 000.
• Suma lungimilor șirurilor de tip 𝑇 din cele 𝑘 teste nu depășește 200 000.
• Punctaj:
  1. pentru 20 de puncte, 𝑐 = 1
  2. pentru 15 puncte, 𝑐 = 2 șirurile de tip 𝑆 din fiecare test au literele sortate crescător/alfabetic.
  3. pentru 25 de puncte, 𝑐 = 2 șirurile de tip 𝑇 din fiecare test pot fi transformate în șirul corespunzător de tip 𝑆 aplicând doar operații de tip 1.
  4. pentru 40 de puncte, 𝑐 = 2 fără alte restricții.

Exemplul 1

opsir.in

1
3
2 4
cc
cbbd
3 2
aab
aa
2 2
ac
da

opsir.out

3
b T
c S
d T
2
a T
b S
3
a T
c S
d T

Explicație

Pentru primul test sunt 3 litere distincte conform cerinței: litera 𝑏 apare de mai multe ori în 𝑇 , 𝑐 apare de mai multe ori în 𝑆, iar 𝑑 apare doar în 𝑇.

Exemplul 2

opsir.in

2
1
2 2
zx
zx

opsir.out

DA

Explicație

Șirurile sunt egale fără a fi necesară aplicarea vreunei operații.

Exemplul 3

opsir.in

2
2
2 3
ab
bca
4 4
bacc
cbac

opsir.out

DA
NU

Explicație

Pentru primul test putem sorta întregul șir 𝑇 , obținând "abc". Putem șterge apoi a treia literă, obținând un șir egal cu 𝑆.

Pentru al doilea test, dacă aplicăm o operație de tip 2 pentru subsecvența formată din primele 2 litere, obținem "bcac". Având în vedere că primele 2 litere devin colorate în urma sortării, nu mai putem aplica o operație de tip 2 pentru subsecvența "ca". Prin urmare, nu putem transforma șirul 𝑇 într-un șir egal cu 𝑆.