4235 – Perechi DivP

Sursa: Perechi DivP

---

Cerinţă

Se dă un șir cu n elemente întregi și un nr întreg p. Subprogramul returnează numărul de perechi (sir[i], sir[j]) cu i < j și suma sir[i]+sir[j] este multiplu de P.

Date de intrare

Programul va citi de la tastatură valoarean, apoi n 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

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

Explicație rezolvare

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

Pentru a verifica validitatea datelor de intrare, au fost definite mai multe funcții de verificare: verificare_nr_elemente, verificare_vector și verificare_p. Toate acestea utilizează funcția is_integer 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 exit.

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

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