Fişierul intrare/ieşire:similar.in, similar.outSursăONIS 2014, Runda Finala
AutorStefan CiobacaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test2.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Similar

După cum ştiţi, lui Gigel îi place să se joace cu şiruri formate din 0 şi din 1 (zero şi unu).

În această problemă, lui Gigel îi plac şi caracterele * si ?.

Gigel are un şir T format din 0 şi din 1 şi un şir P format din 0, 1, * şi ?.

Gigel vrea să verifice cât de similare sunt P şi T.

El verifică similaritatea transformând şirul P în şirul T prin următoarele operaţii:

  • transformă caracterul ? în 0 sau în 1, plătind 0 RON în costuri de similaritate
  • transformă caracterul * într-un şir de 0 şi 1, plătind 0 RON în costuri de similaritate
  • transformă caracterul 0 în 1, plătind 1 RON în costuri de similaritate
  • transformă caracterul 1 în 0, plătind 1 RON în costuri de similaritate

Gradul de similaritate între P şi T este dat de cel mai mic preţ cu care se poate transforma P în T. Gigel vă roagă să-l ajutaţi să găsească gradul de similaritate.

Date de intrare

Pe prima linie din fişierul de intrare similar.in se găseşte numărul Z de teste. Pe următoarele Z * 2 linii se găsesc testele, fiecare test pe două linii. Pe prima linie dintr-un test e şirul T şi pe a doua linie şirul P.

Date de ieşire

Pentru fiecare test, afişaţi în fişierul de ieşire similar.out câte o linie cu un număr reprezentând costul minim de similaritate plătit de Gigel. Dacă nu se poate face transformarea, afişaţi -1.

Restricţii

  • pentru fiecare test, P şi T au cel puţin 1 caracter şi cel mult 1000 de caractere
  • 1Z512

Exemplu

similar.insimilar.out
3
0101
0*1
1111
??00
01
1
0
2
-1

Explicaţie

În primul test, * se transformă în şirul 01 (cost 0). În al doilea test, fiecare ? se transformă în 1 (cost 0) şi cei doi de 0 se transformă în 1 (cost 2). Pentru ultimul test, 0 nu se poate transforma în 01.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content