Revizia anterioară Revizia următoare
| 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.
Î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 similar 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
Fişierul de intrare similar.in ...
Date de ieşire
În fişierul de ieşire similar.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| similar.in | similar.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
