Vizualizare sursă pentru „3055 - pericol”

== Enunt ==

Avem o clasă cu <code>N</code> elevi inventivi. Pentru fiecare dintre ei se cunoaște un coeficient de atitudine reprezentat printr-un număr natural nenul <code>vk</code>. 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 <code>k</code>, <code>1 ≤ k ≤ N</code>, se obține calculând cel mai mare divizor comun <code>dk,j</code> pentru fiecare pereche (<code>vk</code>, <code>vj</code>), <code>1 ≤ j ≤ N</code>, <code>j ≠ k</code> și apoi însumând valorile calculate.

= Cerința =
Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.

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

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

= Restricții și precizări =

* <code>1 ≤ N ≤ 200.000</code>
* <code>1 ≤ vk</code> <code>≤ 10.000.000</code>, <code>1 ≤ k ≤ N</code>
* Pentru teste în valoare de <code>14</code> puncte <code>N ≤ 2000</code>
* Pentru alte teste în valoare de <code>5</code> puncte <code>vk</code> <code>≤ 2000</code>
* Pentru alte teste în valoare de <code>39</code> de puncte <code>vk</code> <code>≤ 2.000.000</code>

= Exemplul 1: =
<code>pericolIN.txt</code>
 6
 2 3 4 5 6 4
<code>pericolOUT.txt</code>
 8 7 10 5 10 10

=== Explicație ===
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: ==
<code>pericolIN.txt</code>
 20000000000
 2 3 4 5 6 4
<code>pericolOUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<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>