1763 - Pachete2

Enunt

Se consideră un șir de N numere ce reprezintă cantitățile disponibile de produse de sezon de N tipuri, în ordinea în care acestea sunt aduse de la magazie. Un automat poate realiza pachete cu două dintre tipurile de produse venite una imediat după cealaltă de la magazie. El este programat să pună în fiecare pachet un același număr A de produse de un tip și un același număr B de produse de celălalt tip, astfel încât să nu rămână produse necuprinse în pachete.

De exemplu, dacă există 20 de prăjiturele COCO și 15 cutii de suc JUMBO, atunci automatul va fi programat să pună 4 prăjiturele și 3 sucuri în fiecare pachet, epuizând simultan stocul de prăjiturele și cutii de suc și obținând astfel 5 pachete. Pentru alte două tipuri de produse consecutive se va proceda la fel, schimbându-se doar parametrii A și B ale programului de împachetare.

La unele produse din șir se poate renunța în totalitate, nefiind incluse în niciun pachet.

Cerința

Cunoscându-se numărul N de tipuri de produse și cantitățile din fiecare produs, în ordinea în care sosesc de la magazie, să se stabilească numărul maxim de pachete care se pot obține prin alegerea convenabilă a perechilor de produse consecutive și programarea corespunzătoare a automatului, pentru fiecare pereche aleasă.

Date de intrare

Din fișierul pachete2.in se citesc, de pe prima linie numărul N de tipuri de produse, iar de pe linia a doua, N numere naturale reprezentând stocurile de produse de fiecare tip, în ordinea în care vin acestea de la magazie. Numerele sunt despărțite între ele prin spații.

Date de ieșire

În fișierul pachete2.out se afișează valoarea P reprezentând numărul maxim de pachete care se pot forma. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1≤N≤100000
• Numărul de produse disponibile din fiecare tip este un număr natural nenul cu cel mult 6 cifre.
• Din orice produs din șir, mașina de împachetat poate fi programată să pună în fiecare pachet cel puțin unul și cel mult toate produsele disponibile.
• Numărul maxim de pachete obținut este cel mult 2000000000.
• După ultimul număr din fișier se pot afla unul sau mai multe spații.

Exemplul 1:

pachete2IN.txt

5
20 15 18 12 13

6
18 9 5 14 63 2

pachete2OUT.txt

11

16

Explicație

Se fac 5 pachete cu primele două tipuri de produse (punând 4 și respectiv 3 din fiecare) și se fac 6 pachete cu următoarele două tipuri de produse (punând 3 și respectiv 2 din fiecare). Ultimul produs rămâne nefolosit.

Se fac 9 pachete cu primele două produse (punând 2 și respectiv 1 din fiecare), nu se folosește produsul al treilea, se fac 7 pachete cu al patrulea și al cincilea produs (punând 2 și respectiv 9 din fiecare). Ultimul produs rămâne nefolosit.

Exemplul 2:

pachete2IN.txt

1000001
20 15 18 12 13

6
18 9 5 14 63 2

pachete2OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

def cmmdc(a, b):
    while b:
        a, b = b, a % b
    return a

def check_constraints(num_sets, x_values):
    # Constraint 1: 1 ≤ N ≤ 100000
    if not (1 <= num_sets <= 100000):
        return False

    # Constraint 2: Numărul de produse disponibile din fiecare tip este un număr natural nenul cu cel mult 6 cifre.
    for x_list in x_values:
        for x in x_list:
            if not (1 <= x <= 999999):
                return False

    return True

def handle_constraints_error(g):
    g.write("Datele nu corespund restrictiilor impuse\n")

def main():
    try:
        with open("pachete2IN.txt", "r") as f, open("pachete2OUT.txt", "w") as g:
            num_sets = int(f.readline())
            x_values_list = []
            for _ in range(num_sets):
                x_values = list(map(int, f.readline().split()))
                x_values_list.append(x_values)

            if not check_constraints(len(x_values_list), x_values_list):
                handle_constraints_error(g)
                return  # Exit program if constraints are violated

            for x_values in x_values_list:
                n = len(x_values)
                c = [0] * (n + 1)
                m = [0] * (n + 1)
                if n >= 2:
                    x = x_values[0]
                    for i in range(1, n):
                        y = x_values[i]
                        c[i] = cmmdc(x, y)
                        x = y

                    m[1] = 0
                    m[2] = c[1]

                    for i in range(3, n + 1):
                        m[i] = max(m[i - 1], m[i - 2] + c[i - 1])

                    result = str(m[n]) if m[n] != 0 else ""
                    g.write(result + '\n')
    except FileNotFoundError:
        print("Input file 'pachete2IN.txt' not found.")
    except Exception as e:
        print("An error occurred:", e)

if __name__ == "__main__":
    main()