3526 - String Query: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: Cerința Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y]. Date de intrare Programul citește de la tastatură n, s, q si cele q query-uri. Date de ieșire Programul va afișa pe ecran raspunsurile la query-urile de tipul 0, fiecare pe linie nouă. R...) |
Fără descriere a modificării |
||
Linia 1: | Linia 1: | ||
Cerința | ==Cerința== | ||
Se dă un string '''s''' de lungime '''n''' și '''q''' query-uri de forma ('''op''', '''x''', '''y'''), unde '''op''' poate fi '''0''' sau '''1'''. Dacă '''op''' este egal cu '''1''', atunci caracterul de pe poziția '''x''' din '''s''' va deveni '''y'''. Dacă '''op''' este egal cu '''0''', se va afișa numărul de caractere distincte ale lui '''s''' din intervalul '''[x, y]'''. | |||
Date de | ==Date de intrare== | ||
Programul citește de la tastatură '''n, s, q''' si cele '''q''' query-uri. | |||
==Date de ieșire== | |||
2 | Programul va afișa pe ecran raspunsurile la query-urile de tipul '''0''', fiecare pe linie nouă. | ||
3 | |||
Explicație | ==Restricții și precizări== | ||
După primele 2 operatii, s = "abca". | |||
*'''1 ≤ n ≤ 5.000.000''' | |||
*'''1 ≤ q ≤ 250.000''' | |||
*'''s''' este format doar din litere mici ale alfabetului englez | |||
==Exemplul 1:== | |||
'''Intrare''' | |||
4 | |||
aaaa | |||
4 | |||
1 2 b | |||
1 3 c | |||
0 1 2 | |||
0 2 4 | |||
'''Ieșire''' | |||
Datele de intrare corespund restrictiilor impuse. | |||
2 | |||
3 | |||
==Exemplul 2:== | |||
'''Intrare''' | |||
string | |||
'''Ieșire''' | |||
Datele de intrare nu corespund restrictiilor impuse. | |||
==Explicație== | |||
După primele '''2''' operatii, '''s''' = '''"abca"'''. | |||
==Rezolvare== | |||
<syntaxhighlight lang="python" line="1" start="1"> | |||
def verificare_restrictii(nr_n, nr_q): | def verificare_restrictii(nr_n, nr_q): | ||
Linia 69: | Linia 93: | ||
except IndexError: | except IndexError: | ||
print("Datele de intrare nu corespund restrictiilor impuse.") | print("Datele de intrare nu corespund restrictiilor impuse.") | ||
</syntaxhighlight> |
Versiunea curentă din 3 ianuarie 2024 17:21
Cerința
Se dă un string s de lungime n și q query-uri de forma (op, x, y), unde op poate fi 0 sau 1. Dacă op este egal cu 1, atunci caracterul de pe poziția x din s va deveni y. Dacă op este egal cu 0, se va afișa numărul de caractere distincte ale lui s din intervalul [x, y].
Date de intrare
Programul citește de la tastatură n, s, q si cele q query-uri.
Date de ieșire
Programul va afișa pe ecran raspunsurile la query-urile de tipul 0, fiecare pe linie nouă.
Restricții și precizări
- 1 ≤ n ≤ 5.000.000
- 1 ≤ q ≤ 250.000
- s este format doar din litere mici ale alfabetului englez
Exemplul 1:
Intrare
4 aaaa 4 1 2 b 1 3 c 0 1 2 0 2 4
Ieșire
Datele de intrare corespund restrictiilor impuse. 2 3
Exemplul 2:
Intrare
string
Ieșire
Datele de intrare nu corespund restrictiilor impuse.
Explicație
După primele 2 operatii, s = "abca".
Rezolvare
def verificare_restrictii(nr_n, nr_q):
if 1 <= nr_n <= 5000000 and 1 <= nr_q <= 250000:
return True
else:
return False
def procesare_query(nr_s, nr_q, intrebare):
for i in range(nr_q):
nr_op, nr_x, nr_y = intrebare[i]
if nr_op == 1:
nr_s[nr_x - 1] = nr_y
elif nr_op == 0:
print(len(set(nr_s[nr_x - 1:nr_y])))
if __name__ == '__main__':
try:
n = int(input("Introduceti lungimea sirului: "))
s = list(input("Introduceti sirul: "))
q = int(input("Introduceti numarul de query-uri: "))
query = []
for _ in range(q):
op, x, y = input("Introduceti query-ul: ").split()
x = int(x)
if op == '1':
query.append((1, x, y))
else:
y = int(y)
query.append((0, x, y))
if verificare_restrictii(n, q):
print("Datele de intrare corespund restrictiilor impuse.")
procesare_query(s, q, query)
else:
print("Datele de intrare nu corespund restrictiilor impuse.")
except ValueError:
print("Datele de intrare nu corespund restrictiilor impuse.")
except IndexError:
print("Datele de intrare nu corespund restrictiilor impuse.")