| Fişierul intrare/ieşire: | similar.in, similar.out | Sursă | ONIS 2014, Runda Finala |
| Autor | Stefan Ciobaca | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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
- 1 ≤ Z ≤ 512
Exemplu
| similar.in | similar.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.
