1759 - Alune

Cerința

Chip şi Dale s-au plictisit de jocurile de până acum şi au hotărât că este timpul să îmbine culesul alunelor cu un joc care să le stimuleze inteligenţa. Chip propune: “eu pun alunele culese de mine într-un şir de C scorburi, iar tu pui alunele culese de tine într-un alt şir, de D scorburi”. Dale a ascultat, a fost de acord și a propus ca jocul să continue astfel: „dacă la împărțirea numărului de alune din prima scorbură a șirului meu la numărul de alune din fiecare scorbură a șirului tău se obține același rest, atunci consider că scorbura mea este umplută corect și scriu pe hârtie cifra 1, altfel o consider umplută incorect și scriu cifra 0. Verific apoi, aplicând aceeași regulă, dacă a doua scorbură din șirul meu este umplută corect, adică dacă la împărțirea numărului de alune din aceasta la numărul de alune din fiecare scorbură din șirul tău, se obține același rest. Notez pe hârtie, în continuare, rezultatul verificării (0 sau 1). Încheiem jocul atunci când terminăm de verificat, după această regulă, toate cele D scorburi ale mele.” Scrieți un program care citește din fișierul alune.in numerele naturale nenule C și D și numărul de alune din fiecare scorbură din șirul lui Chip, respectiv al lui Dale. Programul determină șirul de cifre notat de Dale pe hârtie.

Date de intrare

Fișierul alune.in conține pe prima linie cele două numere naturale, C și D, pe a doua linie C numere naturale, reprezentând numărul de alune din fiecare scorbură a lui Chip, iar pe a treia linie D numere naturale, reprezentând numărul de alune din fiecare scorbură a lui Dale. Toate numerele situate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul alune.out conține o singură linie pe care se află șirul determinat. Cifrele din acest șir nu sunt separate prin spații. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ C, D ≤ 100
• Numerele de alune din scorburile lui Chip, scrise pe a doua linie a fişierului de intrare, sunt numere naturale din intervalul [1, 2 000 000 000];
• Numerele de alune din scorburile lui Dale, scrise pe a treia linie a fişierului de intrare, sunt numere naturale din intervalul [0, 2 000 000 000].

Exemple

Exemplul 1

alune.in

3 2

3 4 5

8 2

ecran

Datele sunt introduse corect.

alune.out

01

Exemplul 2

alune.in

4 4

1 2 3 4

1 3 4 2

ecran

Datele sunt introduse corect.

alune.out

14

Exemplul 3

alune.in

0 1

4

5

ecran

Datele nu corespund restricțiilor impuse.

alune.out

Rezolvare

# 1759 - Alune
def validare_date(C: int, D: int, C_values: list[int], D_values: list[int]) -> bool:
    if not(1 <= C <= 100000 and 1 <= D <= 100000):
        return False
    if any(not (1 <= x <= 2000000000) for x in C_values) or any(not (0 <= x <= 2000000000) for x in D_values):
        return False
    return True


def rezolvare(C: int, D: int, C_values: list[int], D_values: list[int]) -> str:
    suma_C = sum(C_values)
    suma_D = sum(D_values)

    if suma_C != suma_D:
        return "0 1"

    alune_transferate = 0
    nr_transferuri = 0

    for i in range(C):
        dif_alune = D_values[i] - C_values[i]
        if dif_alune > 0:
            alune_transferate += dif_alune
            nr_transferuri += dif_alune

        elif dif_alune < 0:
            nr_transferuri += abs(dif_alune)
            if alune_transferate < abs(dif_alune):
                return "0 1"
            else:
                alune_transferate -= abs(dif_alune)

    return "1{}".format(nr_transferuri)


if __name__ == '__main__':
    try:
        with open("alune.in") as f:
            C, D = map(int, f.readline().split())
            C_values = list(map(int, f.readline().split()))
            D_values = list(map(int, f.readline().split()))

        if not validare_date(C, D, C_values, D_values):
            print("Datele nu corespund restricțiilor impuse.")
        else:
            print("Datele sunt introduse corect.")
            raspuns = rezolvare(C, D, C_values, D_values).strip()

            with open("alune.out", "w") as g:
                g.write(raspuns.replace(" ", "") + "\n")

    except FileNotFoundError:
        print()

Explicatie

validare_date(C: int, D: int, C_values: list[int], D_values: list[int]) -> bool Această funcție primește patru parametri:

C: un număr întreg reprezentând numărul de scoruri ale lui Chip D: un număr întreg reprezentând numărul de scoruri ale lui Dale C_values: o listă de întregi reprezentând numărul de alune din fiecare scor a lui Chip D_values: o listă de întregi reprezentând numărul de alune din fiecare scor a lui Dale Funcția verifică dacă valorile primite respectă restricțiile impuse de problema: 1 ≤ C, D ≤ 100000, 1 ≤ alune_C ≤ 2 000 000 000, 0 ≤ alune_D ≤ 2 000 000 000. Dacă toate valorile sunt în intervalul permis, funcția returnează True, altfel returnează False.

rezolvare(C: int, D: int, C_values: list[int], D_values: list[int]) -> str Această funcție primește aceiași patru parametri ca și validare_date(). Funcția calculează numărul de alune care trebuie transferate între scorburile lui Chip și Dale pentru a avea același număr de alune în fiecare scorbură.

Dacă suma alunelor din scorburile lui Chip nu este egală cu suma alunelor din scorburile lui Dale, funcția returnează "0 1", altfel calculează diferența dintre numărul de alune din scorburile lui Dale și cele din scorburile lui Chip.

Dacă diferența este pozitivă, înseamnă că trebuie transferate alune de la scorburile lui Dale către cele ale lui Chip pentru a obține numărul egal de alune. Dacă diferența este negativă, atunci trebuie transferate alune de la scorburile lui Chip către cele ale lui Dale.

În ambele cazuri, funcția returnează o valoare de tip șir de caractere formată din "1" urmată de numărul de alune care trebuie transferate.

if __name__ == '__main__': Această secțiune de cod verifică dacă acesta este fișierul principal care este executat, prin verificarea dacă variabila specială __name__ are valoarea __main__. Dacă această condiție este îndeplinită, codul din interiorul acestei secțiuni va fi executat.

În interiorul acestei secțiuni, programul deschide fișierul "alune.in" și citește valorile din acesta utilizând funcțiile validare_date() și rezolvare(). Dacă datele de intrare sunt valide, programul scrie rezultatul în fișierul "alune.out". În caz contrar, se afișează un mesaj specific