3055 - pericol: Difference between revisions

From Bitnami MediaWiki
No edit summary
 
(One intermediate revision by the same user not shown)
Line 1: Line 1:
== Enunt ==
== Enunt ==


Fiind dat un șir V format din N numere întregi V[1], …, V[N], definim o tăietură în poziția pos ca fiind o subsecvență care conține elementul de pe poziția pos. Formal, tăieturile în poziția pos sunt de forma V[k], V[k+1], , V[pos], , V[r-1], V[r] pentru orice k, 1 ≤ k ≤ pos și orice r, pos ≤ r ≤ N. Valoarea unei tăieturi este suma tuturor elementelor care fac parte din tăietura respectivă. Definim funcția MulT(pos) ca fiind numărul de tăieturi în poziția pos care au valoarea 0.
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 ==
= Cerința =
Să se calculeze, pentru fiecare elev, indicatorul de pericol asociat lui.


Ioana, fiind foarte curioasă din fire, dar și foarte fascinată de această funcție numită MulT, este foarte interesată în a afla rezultatul pentru MulT(i), unde 1 ≤ i ≤ N.
= 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 intrare ==
= 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.


Fișierul de intrare taietura.in conţine pe prima linie un număr natural N, reprezentând numărul de elemente din șirul V. Următoarea linie va conține exact N valori întregi despărțite prin câte un spațiu, și anume elementele șirului V.
= Restricții și precizări =


== Date de ieșire ==
* <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>


Fișierul de ieșire taietura.out va conţine pe prima linie N numere naturale separate prin câte un spațiu, și anume valorile funcției MulT(i), unde 1 ≤ i ≤ N.
= Exemplul 1: =
<code>pericolIN.txt</code>
6
2 3 4 5 6 4
<code>pericolOUT.txt</code>
8 7 10 5 10 10


== Restrictii si precizari ==
=== Explicație ===
De exemplu indicatorul de pericol al celui de-al cincilea elev se calculează astfel


*1 ≤ N ≤ 100 000
(2,6) + (3,6) + (4,6) + (5,6) + (4,6) = 2+3+2+1+2 = 10
*Orice element al șirului V este mai mic sau egal în valoare absolută cu 1 000 000 000
*Pentru teste în valoare de 20 de puncte N ≤ 100
*Pentru teste în valoare de încă 20 de puncte N ≤ 1000


== Exemplul 1 ==
== Exemplul 2: ==
<code>pericolIN.txt</code>
20000000000
2 3 4 5 6 4
<code>pericolOUT.txt</code>
Datele nu corespund restrictiilor impuse


;taieturain.txt
== 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)


:3
def main():
 
    with open("pericolIN.txt", "r") as infile, open("pericolOUT.txt", "w") as outfile:
:0 1 0
        N = int(infile.readline().strip())
 
        V = list(map(int, infile.readline().split()))
;taieturaout.txt
 
:Datele introduse corespund restrictiilor impuse.
 
:1 0 1


== Exemplul 2 ==
        verifica_restrictiile(N, V)


;taieturain.txt
        max_value = max(V) + 1


:-2 4
        count = [0] * max_value
        for x in V:
            count[x] += 1


:0
        elementary = [True] * max_value
        primes = [0] * max_value
        formula = [0] * max_value
        answer = [0] * max_value


;taieturaout.txt
        primes[1] = 2


:Datele de intrare nu corespund restrictiilor impuse.
        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


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


<syntaxhighlight lang="python3" line="1"
            frequency = sum(count[j] for j in range(i, max_value, i))
def MulT(N, V):
    prefix_sum = [0] * (N + 1)
    count_sum = {0: 1}
    result = 0


    for i in range(1, N + 1):
            for j in range(i, max_value, i):
        prefix_sum[i] = prefix_sum[i - 1] + V[i - 1]
                answer[j] += formula[i] * frequency
        result += count_sum.get(prefix_sum[i], 0)
        count_sum[prefix_sum[i]] = count_sum.get(prefix_sum[i], 0) + 1
 
    return result
 
def main():
    N = int(input("Introduceți lungimea șirului V: "))
    V = list(map(int, input("Introduceți elementele șirului V, separate prin spațiu: ").split()))


    rezultat = MulT(N, V)
        result = [answer[x] - x for x in V]
    print(f"Rezultatul pentru funcția MulT este: {rezultat}")
        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 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>