3055 - pericol
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
puncteN ≤ 2000
- Pentru alte teste în valoare de
5
punctevk
≤ 2000
- Pentru alte teste în valoare de
39
de punctevk
≤ 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>