Editing 4235 – Perechi DivP

Sursa: [https://www.pbinfo.ro/probleme/4235/perechidivp Perechi DivP]
----
==Cerinţă==
Se dă un șir cu <code>n</code> elemente întregi și un nr întreg p. Subprogramul returnează numărul de perechi <code>(sir[i], sir[j])</code> cu <code>i < j</code> și suma sir<code>[i]+sir[j]</code> este multiplu de <code>P</code>.
==Date de intrare==
Programul va citi de la tastatură valoarea<code>n</code>, apoi <code>n</code> numere întregi reprezentând elementele șirului, urmate de elementul p.
==Date de ieșire==
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele introduse sunt corecte!", apoi se va afișa numărul de perechi care îndeplinesc condițiile mai sus precizate. În cazul în care datele nu respectă restricțiile, se va afișa mesajul "Datele introduse nu sunt corecte!".
==Restricţii şi precizări==
*2 <= n <= 20000
*valorile elementelor șirului vor fi cuprinse între 1 și 30.000
*2 <= p <= 1000
==Exemple==
===Exemplul 1===
;Intrare
:Introduceti numarul de elemente a sirului: 5
:Introduceti 5 numere separate prin spatiu:9 2 4 7 3
:Introduceti elementul p: 3
;Ieșire
:Datele introduse sunt corecte!
:3
===Exemplul 2===
;Intrare
:Introduceti numarul de elemente a sirului: 6
:Introduceti 6 numere separate prin spatiu:1 411 3 4 1 2
:Introduceti elementul p: 2
;Ieșire
:Datele introduse sunt corecte!
:7
===Exemplul 3===
;Intrare
:Introduceti numarul de elemente a sirului: 3
:Introduceti 3 numere separate prin spatiu:131 131 41 2
;Ieșire
:Datele introduse sunt incorecte!
:
==Rezolvare==
<syntaxhighlight lang="python" line="1">
def is_integer(value):
    return value.isdigit()


def verificare_nr_elemente(n):
    if is_integer(n):
        if 2 <= int(n) <= 200000:
            return n
        else:
            print("Datele introduse sunt incorecte!")
            exit()
    else:
        print("Datele introduse sunt incorecte!")
        exit()


def verificare_vector(n, vector):
    if len(vector) != int(n):
        print("Datele introduse sunt incorecte!")
        exit()
    else:
        for i in vector:
            if is_integer(i):
                if 1 <= int(i) <= 30000:
                    continue
                else:
                    print("Datele introduse sunt incorecte!")
                    exit()
            else:
                print("Datele introduse sunt incorecte!")
                exit()


def verificare_p(p):
    if is_integer(p):
        if 2 <= int(p) <= 1000:
            return p
        else:
            print("Datele introduse sunt incorecte!")
            exit()
    else:
        print("Datele introduse sunt incorecte!")
        exit()


def nr_perechi_multiplu_p(sir, n, P):
    cnt = [0] * int(P)
    res = 0

    for i in range(int(n)):
        if sir[i] % int(P) == 0:
            res += cnt[0]
        else:
            res += cnt[int(P) - sir[i] % int(P)]
        cnt[sir[i] % int(P)] += 1

    return res


if __name__ == '__main__':
    n = input("Introduceti numarul de elemente a sirului: ")
    verificare_nr_elemente(n)
    elem = input(f"Introduceti {n} numere separate prin spatiu:").split()
    verificare_vector(n, elem)
    lst_int = list(map(int, elem))
    p = input("Introduceti elementul p: ")
    verificare_p(p)
    print("Datele introduse sunt corecte!")
    print(nr_perechi_multiplu_p(lst_int, n, p))





</syntaxhighlight>
==Explicație rezolvare==
Această soluție implementează o funcție numită <code>nr_perechi_multiplu_p</code> care primește ca argumente un vector de numere întregi <code>sir</code>, lungimea acestuia <code>n</code> și un număr întreg <code>P</code>. Scopul acestei funcții este de a returna numărul de perechi <code>(a[i], a[j])</code> pentru care <code>i < j</code> și <code>a[i] + a[j]</code> este multiplu de <code>P</code>.

Pentru a verifica validitatea datelor de intrare, au fost definite mai multe funcții de verificare: <code>verificare_nr_elemente</code>, <code>verificare_vector</code> și <code>verificare_p</code>. Toate acestea utilizează funcția <code>is_integer</code> pentru a verifica dacă valorile introduse sunt numere întregi valide. Dacă valorile introduse nu sunt corecte, programul afișează un mesaj de eroare și se oprește prin utilizarea funcției <code>exit</code>.

Funcția <code>nr_perechi_multiplu_p</code> utilizează un vector <code>cnt</code> inițializat cu valori de 0 pentru a număra aparițiile fiecărui rest modulo <code>P</code> al elementelor din vectorul <code>sir</code>. Pe măsură ce se parcurge vectorul, se calculează restul fiecărui element <code>sir[i]</code> împărțit la <code>P</code>, iar apoi se adaugă numărul de perechi în care suma lor este multiplu de <code>P</code>. Numărul de astfel de perechi este reprezentat de <code>cnt[0]</code> dacă <code>sir[i]</code> este el însuși multiplu de <code>P</code>. În caz contrar, numărul de perechi corespunzătoare este reprezentat de <code>cnt[P - sir[i] % P]</code>. La sfârșit, funcția returnează numărul total de perechi găsite.

În blocul <code>if __name__ == '__main__':</code>, programul citește datele de intrare (lungimea vectorului, elementele acestuia și numărul <code>P</code>), verifică dacă acestea sunt corecte și, dacă sunt, afișează numărul de perechi cerute utilizând funcția <code>nr_perechi_multiplu_p</code>.