AjM: Pagină nouă: == Cerinţa == Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații: * 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val; * 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori); * 3 st dr – se cere să se afișeze lu...

2024-06-03T15:33:40Z

Pagină nouă: == Cerinţa == Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații: * 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val; * 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori); * 3 st dr – se cere să se afișeze lu...

New page

== Cerinţa ==
Se dă un șir a de n numere naturale nenule strict mai mari decât 1, indexat de la 1. Asupra acestui șir se aplică 3 tipuri de operații:
* 1 st dr val – toate valorile a[i] cu i din intervalul [st, dr] devin egale cu val;
* 2 st dr – se cere să se afle câte elemente ale șirului a care au indicii aflați în intervalul [st, dr] sunt numere compuse(un număr natural este compus dacă are cel puțin 3 divizori);
* 3 st dr – se cere să se afișeze lungimea cele mai lungi secvențe de numere prime alcătuită exclusiv din elemente ale șirului care au indicii aflați în intervalul [st, dr](o secvență a unui șir este alcătuită din elemente aflate poziții consecutive).
Dându-se Q operații, să se raspundă în ordine la cele de tip 2 și 3.
== Date de intrare ==
Fișierul de intrare numbers_tree.in conține pe prima linie numerele n și Q, reprezentând numărul de elemente ale șirului a, respectiv numărul de operații, pe a doua linie n numere naturale separate prin spații reprezentând elementele șirului inițial, iar pe următoarele Q linii sunt descrise operațiile.
== Date de ieșire ==
Fișierul de ieșire numbers_tree.out va conține pe câte o linie răspunsurile la operațiile de tip 2 și 3 în ordinea în care acestea apar în fișierul de intrare.
== Restricţii şi precizări ==
* 1 ≤ n, Q ≤ 100.000
* 2 ≤ a[i], val ≤ 1.000.000
* 1 ≤ st ≤ dr ≤ n
== Exemplu ==
; numbers_tree.in
7 7
2 3 4 5 6 7 8
2 1 7
3 1 7
1 2 5 4
2 2 5
3 2 5
1 2 4 3
3 1 6
; numbers_tree.out
3
2
4
0
4
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def read_input(filename):
with open(filename, 'r') as f:
n, Q = map(int, f.readline().split())
a = list(map(int, f.readline().split()))
operations = [list(map(int, line.split())) for line in f.readlines()]
return n, a, operations

def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True

def apply_operation_2(a, st, dr):
count_composite = 0
for i in range(st - 1, dr):
if a[i] > 1 and not is_prime(a[i]):
count_composite += 1
return count_composite

def apply_operation_3(a, st, dr):
max_prime_sequence = 0
current_prime_sequence = 0
for i in range(st - 1, dr):
if is_prime(a[i]):
current_prime_sequence += 1
max_prime_sequence = max(max_prime_sequence, current_prime_sequence)
else:
current_prime_sequence = 0
return max_prime_sequence

def process_operations(n, a, operations):
result = []
for op in operations:
if op[0] == 2:
count_composite = apply_operation_2(a, op[1], op[2])
result.append(count_composite)
elif op[0] == 3:
max_prime_sequence = apply_operation_3(a, op[1], op[2])
result.append(max_prime_sequence)
return result

def write_output(filename, result):
with open(filename, 'w') as f:
for res in result:
f.write(str(res) + '\n')

def main():
input_file = "numbers_tree.in"
output_file = "numbers_tree.out"
n, a, operations = read_input(input_file)
result = process_operations(n, a, operations)
write_output(output_file, result)

if __name__ == "__main__":
main()

</syntaxhighlight>

3600 - Numbers Tree - Revision history