Cerinţa

La magazinul din colț au fost aduse n cutii, numerotate de la 1 la n, fiecare conținând un anumit număr de bomboane. Administratorul magazinului hotărăște, pentru bunul mers al afacerilor, că bomboanele trebuie rearanjate în cutii, astfel încât fiecare cutie să conțină același număr de bomboane. Pentru aceasta, administratorul magazinului realizează în mod repetat următoarea operație: mută un număr oarecare de bomboane din cutia cu număr maxim de bomboane în cea cu număr minim de bomboane.

Determinați un șir cu număr minim de operații prin care toate cutiile conțin același număr de bomboane.

Date de intrare

Fişierul de intrare bomboane.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 de bomboane din fiecare cutie.

Date de ieşire

Fişierul de ieşire bomboane.out va conţine pe prima linie numărul M, reprezentând numărul total de mutări. Următoarele M linii descriu mutările. Fiecare linie va conține câte trei numere S D B, separate prin câte un spațiu, cu semnificația: din cutia S s-au mutat în cutia D un număr de B bomboane.

Restricţii şi precizări

1 ≤ n ≤ 1000
în fiecare cutie se află cel puțin una și cel mult 1000 de bomboane
după efectuarea mutărilor numărul total de bomboane din cutii este același cu numărul total de bomboane de la început
dacă nu este posibilă redistribuirea bomboanelor în condițiile date se va afișa pe prima linie a fișierului valoarea -1
administratorul magazinului bănuiește că aceasta nu este cea mai eficientă metodă de lucru, dar se mulțumește cu aceasta.

Exemplu

bomboane.in

5
4 2 1 7 1

bomboane.out

Explicație

Se fac 3 operații:

se mută 2 bomboane din cutia 4 în cutia 3. Conținutul cutiilor va fi: 4 2 3 5 1
se mută 2 bomboane din cutia 4 în cutia 5. Conținutul cutiilor va fi: 4 2 3 3 3
se mută o bomboană din cutia 1 în cutia 2. Conținutul cutiilor va fi: 3 3 3 3 3

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 Bomboane:

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("bomboane.in");
ofstream fout("bomboane.out");

int n , x[1005], I[1005], S[1005], D[1005], B[1005], nrM=0;

bool MaiMic(int i, int j)
{
    return x[i]<x[j];
}

int main(){
    fin >> n;
    int s = 0;
    for(int i=1 ; i<=n ; ++i)
        fin >> x[i], I[i] = i, s += x[i];
    if(s % n !=0)
        fout << -1;
    else{
        int q = s / n;
        sort(I+1, I+n+1, MaiMic);
        int i=1,j=n;
        while(i<j)
        {
            int necesar = q-x[I[i]], surplus = x[I[j]] - q;
            if(necesar==0)
                i++;
            else
                if(surplus==0)
                    j--;
                else
                    if(necesar <= surplus)
                    {
                        x[I[i]] += necesar;
                        x[I[j]] -= necesar;
                        nrM++;
                        S[nrM] = I[j], D[nrM] = I[i], B[nrM] = necesar;
                        int p = I[j], k = j;
                        while(x[I[k-1]]> x[p])
                            I[k] = I[k-1], k--;
                        I[k] = p;
                        p = I[i];
                        k = i;
                        while(x[I[k+1]]<x[p])
                            I[k] = I[k+1], k++;
                        I[k] = p;
                    }
                    else
                    {
                        x[I[i]] += surplus;
                        x[I[j]] -= surplus;
                        nrM++;
                        S[nrM] = I[j], D[nrM] = I[i], B[nrM] = surplus;
                        int p = I[j] , k = j;
                        while(x[I[k-1]]> x[p])
                            I[k] = I[k-1], k--;
                        I[k] = p;
                        p = I[i];
                        k = i;
                        while(x[I[k+1]]<x[p])
                            I[k] = I[k+1], k++;
                        I[k] = p;
                    }
        }
        fout << nrM << "
";
        for(int i=1 ; i<=nrM ; ++i)
            fout << S[i] << " " << D[i] << " " << B[i] << "
";
    }
    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 #341 Bomboane

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #341 Bomboane 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 #341 Bomboane