https://wiki.universitas.ro/index.php?action=history&feed=atom&title=3134_-_INF3134 - INF - Revision history2026-05-01T10:13:38ZRevision history for this page on the wikiMediaWiki 1.42.1https://wiki.universitas.ro/index.php?title=3134_-_INF&diff=9705&oldid=prevAurelia Raluca at 21:17, 22 March 20242024-03-22T21:17:15Z<p></p>
<a href="//wiki.universitas.ro/index.php?title=3134_-_INF&diff=9705&oldid=9067">Show changes</a>Aurelia Ralucahttps://wiki.universitas.ro/index.php?title=3134_-_INF&diff=9067&oldid=prevAurelia Raluca: Pagină nouă: == Cerinta == Se consideră șirul infinit inf="INFINFINFINF...". Se dau două numere naturale n și k și un șir de caractere s de lungime n format doar din caracterele 'I' , 'N' și 'F'. Să se afle numărul minim de modificări ce trebuie realizate în șirul s pentru a obține o subsecvență de lungime k a șirului infinit inf. O modificare constă în schimbarea unui caracter din șirul s cu un alt caracter din mulțimea {'I','N','F'}. De exemplu, în urma unei mo...2024-01-05T09:40:34Z<p>Pagină nouă: == Cerinta == Se consideră șirul infinit inf="INFINFINFINF...". Se dau două numere naturale n și k și un șir de caractere s de lungime n format doar din caracterele 'I' , 'N' și 'F'. Să se afle numărul minim de modificări ce trebuie realizate în șirul s pentru a obține o subsecvență de lungime k a șirului infinit inf. O modificare constă în schimbarea unui caracter din șirul s cu un alt caracter din mulțimea {'I','N','F'}. De exemplu, în urma unei mo...</p>
<p><b>New page</b></p><div>== Cerinta ==<br />
<br />
Se consideră șirul infinit inf="INFINFINFINF...".<br />
<br />
Se dau două numere naturale n și k și un șir de caractere s de lungime n format doar din caracterele 'I' , 'N' și 'F'.<br />
<br />
Să se afle numărul minim de modificări ce trebuie realizate în șirul s pentru a obține o subsecvență de lungime k a șirului infinit inf.<br />
<br />
O modificare constă în schimbarea unui caracter din șirul s cu un alt caracter din mulțimea {'I','N','F'}.<br />
<br />
De exemplu, în urma unei modificări a ultimului caracter, șirul "IIIFN" devine "IIIFF".<br />
<br />
== Date de intrare == <br />
<br />
Fișierul de intrare inf.in conține pe prima linie numerele n și k, iar pe a doua linie șirul s format din n caractere.<br />
<br />
== Date de iesire ==<br />
<br />
Fișierul de ieșire inf.out va conține pe prima linie numărul de modificări necesare.<br />
<br />
== Restrictii si precizari ==<br />
<br />
*2 ≤ n ≤ 1.500.000<br />
*1 ≤ k ≤ 500.000<br />
*k ≤ n<br />
*Rezultatul poate fi 0<br />
*O subsecvență de lungime k a șirului s reprezintă un șir format din k elemente de pe poziții consecutive din șirul s.<br />
<br />
== Exemplul 1 ==<br />
<br />
;infin.txt<br />
<br />
:5 2<br />
<br />
:FNNNN<br />
<br />
;infout.txt<br />
<br />
:Datele introduse corespund restrictiilor impuse.<br />
<br />
:1<br />
<br />
== Exemplul 2 ==<br />
<br />
;infin.txt<br />
<br />
:10 12<br />
<br />
:FFNNI<br />
<br />
;infout.txt<br />
<br />
:Datele de intrare nu corespund restrictiilor impuse.<br />
<br />
== Rezolvare ==<br />
<syntaxhighlight lang="python3" line="1"><br />
<br />
def numar_minim_modificari(s, k):<br />
n = len(s)<br />
<br />
# Calculăm numărul necesar de caractere 'I', 'N', 'F' pentru subsecvența dorită<br />
numar_i = k<br />
numar_n = k - 1<br />
numar_f = k<br />
<br />
# Numărăm caracterele existente în șirul dat<br />
numar_i_s = s.count('I')<br />
numar_n_s = s.count('N')<br />
numar_f_s = s.count('F')<br />
<br />
# Calculăm numărul minim de modificări<br />
modificari_necesare = max(0, numar_i - numar_i_s) + max(0, numar_n - numar_n_s) + max(0, numar_f - numar_f_s)<br />
<br />
return modificari_necesare<br />
<br />
rezultat = numar_minim_modificari(sir, lungime_subsecventa)<br />
print(f"Numărul minim de modificări necesare: {rezultat}")<br />
<br />
</syntaxhighlight></div>Aurelia Raluca