1473 - Grupa Pregătitoare

Sursa: [1]

Cerinţa

Cei n elevi de la grupa pregătitoare au primit câte două cartonaşe, fiecare cartonaş având scris pe el un număr natural. Ei s-au aşezat în cerc şi, la un semnal dat, fiecare a scos la întâmplare un cartonaş din buzunar. Copiii vă roagă să răspundeţi la următoarele întrebări: 1. Care poate fi suma maximă S a numerelor de pe cartonaşele scoase, ştiind că produsul acestora este divizibil cu un număr prim p? 2. Care poate fi lungimea maximă L a unei secvenţe de copii de pe cerc pentru care suma numerelor de pe cartonaşele scoase de către oricare doi vecini din secvenţă este pară?

Date de intrare

Fișierul de intrare grupapregatitoare.in conține pe prima linie numerele n şi p, iar pe următoarele n linii câte două numere naturale reprezentând numerele de pe cartonaşele fiecărui elev, în ordinea în care s-au aşezat pe cerc

Date de ieșire

Programul va afișa pe ecran, mesajul "Datele introduse corespund cerințelor" si fișierul de ieșire grupapregatitoare.out va conține pe prima linie numărul S, iar pe a doua linie numărul L. În caz contrar programul va afișa pe o linie noua mesajul "Datele introduse nu corespund cerintelor.".

Restricţii şi precizări

• 3 ⩽ n ⩽ 2000
• 2 ⩽ p ⩽ 1000
• numerele de pe cartonaşele elevilor sunt nenule şi mai mici decât 1001
• există cel puţin un număr divizibil cu p pe un cartonaş

Exemplul 1

Intrare

grupapregatitoare.in

3 7

1 2

21 4

5 6

Ieșire

Datele introduse corespund cerintelor

grupapregatitoare.out

29

3

Exemplul 2

Intrare

grupapregatitoare.in

100000000 1000000

1 2

21 4

5 6

Ieșire

grupapregatitoare.out

Datele introduse nu corespund cerintelor.

Rezolvare

#1473
def read_input():
    with open("grupapregatitoare.in", "r") as in_file:
        n, p = map(int, in_file.readline().split())
        values = []
        for _ in range(n):
            x, y = map(int, in_file.readline().split())
            values.append((x, y))
    return p, values


def validate_input(n, p, values):
    if not (3 <= n <= 2000):
        print("Datele introduse nu corespund cerintelor.")
        exit()

    if not (2 <= p <= 1000):
        print("Datele introduse nu corespund cerintelor.")
        exit()

    for x, y in values:
        if not (0 < x < 1001 and 0 < y < 1001):
            print("numerele de pe cartonas trebuie sa fie nenule si mai mici decat 1001")
            exit()
        if x % p == 0 or y % p == 0:
            return  # satisface conditia ca exista cel putin un numar divizibil cu p pe un cartonas

    print("nu exista cel putin un numar divizibil cu p pe un cartonas")
    exit()


def compute_result(p, values):
    nr1, nr2 = 0, 0
    suma = 0
    flag = False
    minim = 20000
    secpar = 0
    secimp = 0
    lp = 0
    li = 0
    maxim = 0
    lungi = 0
    lungp = 0

    for x, y in values:
        if x > y:
            suma += x
        else:
            suma += y
        if ((x % p == 0) and (x >= y)) or ((y % p == 0) and (y >= x)):
            flag = True
        if (x % p == 0) and (x < y) and (y - x < minim):
            minim = y - x
            nr1 = x
            nr2 = y
        if (y % p == 0) and (y < x) and (x - y < minim):
            minim = x - y
            nr1 = y
            nr2 = x
        if (x % 2 == 0) or (y % 2 == 0):
            secpar += 1
        else:
            if lp == 0:
                lungp = secpar
                lp = 1
            if secpar > maxim:
                maxim = secpar
            secpar = 0
        if (x % 2 == 1) or (y % 2 == 1):
            secimp += 1
        else:
            if li == 0:
                lungi = secimp
                li = 1
            if secimp > maxim:
                maxim = secimp
            secimp = 0

    if secpar + lungp > maxim:
        maxim = secpar + lungp
    if secimp + lungi > maxim:
        maxim = secimp + lungi

    return suma, flag, nr1, nr2, maxim


def write_output(result):
    with open("grupapregatitoare.out", "w") as out_file:
        suma, flag, nr1, nr2, maxim = result
        if flag:
            out_file.write(str(suma))
        else:
            out_file.write(str(suma - nr2 + nr1))
        out_file.write("\n" + str(maxim))


if __name__ == "__main__":
    with open("grupapregatitoare.in", "r") as in_file, open("grupapregatitoare.out", "w") as out_file:
        n, p = map(int, in_file.readline().split())
        values = [tuple(map(int, line.split())) for line in in_file]

        validate_input(n, p, values)

        result = compute_result(p, values)
        print("Datele introduse corespund cerintelor.")
        write_output(result)

Explicatie rezolvare

Acest program are rolul de a rezolva o problema specifica. Fisierul "grupapregatitoare.in" contine datele de intrare, iar fisierul "grupapregatitoare.out" va contine rezultatul obtinut.

Programul citeste datele de intrare din fisierul "grupapregatitoare.in" si le valideaza. In cazul in care datele nu corespund cerintelor, programul se va opri si va afisa un mesaj corespunzator.

Daca datele sunt valide, programul va calcula si va scrie rezultatul in fisierul "grupapregatitoare.out".

Functia "read_input()" citeste datele de intrare din fisierul "grupapregatitoare.in" si le returneaza sub forma unei tuple, p si values.

Functia "validate_input()" valideaza datele de intrare, verificand daca n este intre 3 si 2000, p intre 2 si 1000 si daca fiecare numar de pe cartonas este nenul si mai mic decat 1001. De asemenea, functia verifica daca exista cel putin un numar divizibil cu p pe un cartonas.

Functia "compute_result()" calculeaza si returneaza rezultatul problemei. Mai intai se initializeaza mai multe variabile, apoi se parcurg elementele listei "values". Se calculeaza suma maxima dintre numerele de pe fiecare cartonas, apoi se verifica daca exista cel putin un numar divizibil cu p pe un cartonas. Daca nu exista, se scade din suma maxima diferenta dintre cel mai mare numar de pe un cartonas care nu este divizibil cu p si cel mai mic numar de pe alt cartonas care este divizibil cu p. De asemenea, se calculeaza lungimea secventelor continue de numere pare sau impare de pe cartoane. La final, se returneaza suma, un boolean care indica daca exista cel putin un numar divizibil cu p, cele doua numere intregi nr1 si nr2, si lungimea maxima a unei secvente continue de numere pare sau impare de pe cartoane.

Functia "write_output()" scrie rezultatul in fisierul "grupapregatitoare.out". In functie de valoarea flag-ului returnat de functia "compute_result()", se scrie fie suma maxima, fie suma maxima diminuata cu diferenta dintre cele doua numere returnate (nr1 si nr2). Apoi, se scrie lungimea maxima a unei secvente continue de numere pare sau impare de pe cartoane.

Blocul "if __name__ == "__main__":" apeleaza celelalte functii pentru a citi datele de intrare, a le valida, a calcula rezultatul si a scrie rezultatul in fisierul "grupapregatitoare.out". Daca datele de intrare sunt valide, functia va afisa mesajul "Datele corespund cerintelor." in consola.