3600 - Numbers Tree

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

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>