3055 - pericol: Difference between revisions
No edit summary |
|||
(One intermediate revision by the same user not shown) | |||
Line 1: | Line 1: | ||
== Enunt == | == 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 | == 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__": | if __name__ == "__main__": |
Latest revision as of 15:59, 12 February 2024
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>