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.

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.

Exemplu

pachete2.in

5
20 15 18 12 13

6
18 9 5 14 63 2

pachete2.out

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Pachete2:

#include <fstream>

using namespace std;
int n;
int c[100000],m[100000];
int cmmdc(int a, int b)
{
    int r=a%b;
    while(r!=0)
    {
        a=b;b=r;
        r=a%b;
    }
    return b;
}
int main()
{
    int i,x,y;
    ifstream f("pachete2.in");
    ofstream g("pachete2.out");
    f>>n;
    f>>x;
    for(i=1;i<n;i++)
    {
        f>>y;
        c[i]=cmmdc(x,y);
        x=y;
    }
    f.close();
    m[1]=0;
    m[2]=c[1];
    for(i=3;i<=n;i++)
        m[i]=max(m[i-1],m[i-2]+c[i-1]);
    g<<m[n];
    g.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1763 Pachete2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1763 Pachete2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1763 Pachete2