3024 - ou

Sursa: 3024 - ou

---

Cerinţa

Pe strada lui Dorel casele sunt aşezate doar de o parte a străzii. Cu ocazia sărbătorilor de Paşti, fiecare proprietar împarte ouă roşii vecinilor cei mai apropiaţi de casa lui. Se ştie că pe strada lui Dorel sunt n case, fiecare proprietar i are O[i] ouă, fiecare proprietar împarte ouă la un număr egal de case situate în stânga şi în dreapta lui, de asemenea fiecare vrea să împartă ouă la un număr maxim de case, un număr egal de ouă, cât mai mare, la fiecare casă. Dacă obiceiul de împărţire a ouălor are loc simultan, aflaţi câte ouă va avea fiecare la sfârşitul zilei.

Date de intrare

Fișierul de intrare ou.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, reprezentând numărul ouălor din fiecare casă.

Date de ieșire

Fișierul de ieșire ou.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou pe prima linie n numere, reprezentând numărul ouălor avute de fiecare proprietar la sfârşitul zilei., reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 3 ≤ n ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi naturale nenule, mai mici decât 1.000.000.000

Exemplu 1

Intrare

ou.in

5

13 2 7 44 5

Ieșire

ou.out

Datele sunt introduse correct.

15 1 26 1 28

Exemplu 2

Intrare

ou.in

5

-13 2 72 44 -5

Ieșire

ou.out

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 3024 - ou

def citire():
    with open("ou.in") as f:
        n = int(f.readline())
        O = list(map(int, f.readline().split()))
    return O, n

def rezolvare(O, n):
    S = sum(O)
    S /= n
    stanga = [0] * n
    dreapta = [0] * n
    for i in range(1, n):
        stanga[i] = stanga[i - 1] + O[i - 1]
    for i in range(n - 2, -1, -1):
        dreapta[i] = dreapta[i + 1] + O[i + 1]
    sol = []
    for i in range(n):
        oua = (stanga[i] + dreapta[i]) // (2 * S)
        sol.append(oua)
    return sol

def validare(sol):
    with open("ou.in") as f:
        n = int(f.readline())
        O = list(map(int, f.readline().split()))
    for i in range(n):
        S = sum(O)
        S //= len(sol)
        for j in range(i - oua, i + oua + 1):
            if j >= 0 and j < n:
                S -= sol[j]
        if S != 0:
            return False
    return True

if __name__ == "__main__":
    O, n = citire()
    sol = rezolvare(O, n)
    with open("ou.out", "w") as f:
        f.write(" ".join(str(x) for x in sol))
    if validare(sol):
        print("Datele sunt introduse corect.")
    else:
        print("Datele nu corespund restricțiilor impuse.")
    print("\n".join(str(x) for x in sol))

Explicatie Rezolvare

Pentru a rezolva această problemă, vom urma următorii pași:

Vom scrie o funcție citire() pentru a citi datele din fișierul de intrare. Vom scrie o funcție rezolvare(O, n) care primește lista O cu numărul de ouă pentru fiecare casă și numărul de case n, și returnează lista cu numărul de ouă pe care îl va avea fiecare proprietar la sfârșitul zilei. Vom scrie o funcție validare(sol) pentru a valida soluția noastră, verificând dacă numărul total de ouă împărțit de fiecare proprietar corespunde cu numărul de ouă pe care îl are inițial. În funcția citire() se deschide fișierul "ou.in" și se citesc cele două linii. Prima linie conține numărul de case n, iar a doua linie conține numărul de ouă din fiecare casă. Funcția rezolvare(O, n) primește lista O și numărul de case n. Se calculează numărul total de ouă S, se calculează sumele pentru casele din stânga și din dreapta fie În funcția main vom apela cele trei funcții și vom scrie rezultatul în fișierul de ieșire.