3055 - pericol

From Bitnami MediaWiki

Enunt[edit | edit source]

Avem o clasă cu N elevi inventivi. Pentru fiecare dintre ei se cunoaște un coeficient de atitudine reprezentat printr-un număr natural nenul vk. Interacțiunile din cadrul grupului de elevi al clasei produc efecte secundare importante și conducerea școlii a definit o mărime scalară numită indicator de pericol care măsoară influența pe care un elev o are asupra celorlalți elevi din clasă. Indicatorul de pericol asociat elevului k, 1 ≤ k ≤ N, se obține calculând cel mai mare divizor comun dk,j pentru fiecare pereche (vk, vj), 1 ≤ j ≤ N, j ≠ k și apoi însumând valorile calculate.

Cerința[edit | edit source]

Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.

Date de intrare[edit | edit source]

În fișierul text pericolIN.txt pe prima linie se află numărul natural N. Pe a doua linie se află N numere naturale nenule, separate prin câte un spațiu, reprezentând coeficienții de atitudine ai celor N elevi.

Date de ieșire[edit | edit source]

În fișierul text pericolOUT.txt se vor scrie, pe prima linie, N numere naturale, separate prin câte un spațiu, al k-lea număr natural reprezentând indicatorul de pericol asociat celui de-al k-lea elev.

Restricții și precizări[edit | edit source]

  • 1 ≤ N ≤ 200.000
  • 1 ≤ vk ≤ 10.000.000, 1 ≤ k ≤ N
  • Pentru teste în valoare de 14 puncte N ≤ 2000
  • Pentru alte teste în valoare de 5 puncte vk ≤ 2000
  • Pentru alte teste în valoare de 39 de puncte vk ≤ 2.000.000

Exemplul 1:[edit | edit source]

pericolIN.txt

6
2 3 4 5 6 4

pericolOUT.txt

8 7 10 5 10 10

Explicație[edit | edit source]

De exemplu indicatorul de pericol al celui de-al cincilea elev se calculează astfel

(2,6) + (3,6) + (4,6) + (5,6) + (4,6) = 2+3+2+1+2 = 10

Exemplul 2:[edit | edit source]

pericolIN.txt

20000000000
2 3 4 5 6 4

pericolOUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def verifica_restrictiile(N, V):

   if not (2 <= N <= 200000 and all(1 <= v <= 10000000 for v in V)):
       with open("pericolOUT.txt", "w") as outfile:
           outfile.write("Datele nu corespund restrictiilor impuse\n")
       exit(1)

def main():

   with open("pericolIN.txt", "r") as infile, open("pericolOUT.txt", "w") as outfile:
       N = int(infile.readline().strip())
       V = list(map(int, infile.readline().split()))
       verifica_restrictiile(N, V)
       max_value = max(V) + 1
       count = [0] * max_value
       for x in V:
           count[x] += 1
       elementary = [True] * max_value
       primes = [0] * max_value
       formula = [0] * max_value
       answer = [0] * max_value
       primes[1] = 2
       for i in range(1, max_value):
           if primes[i] == 0:
               for j in range(i, max_value, i):
                   primes[j] += 1
               if i * i < max_value:
                   for j in range(i * i, max_value, i * i):
                       elementary[j] = False
           if elementary[i]:
               sign = 1 if primes[i] % 2 == 0 else -1
               for j in range(i, max_value, i):
                   formula[j] += sign * (j // i)
           frequency = sum(count[j] for j in range(i, max_value, i))
           for j in range(i, max_value, i):
               answer[j] += formula[i] * frequency
       result = [answer[x] - x for x in V]
       outfile.write(" ".join(map(str, result)) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>