Question

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.

Answer 1

#include <fstream>

using namespace std;

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

int n,M,S,D,B,a[1001],b[1001],i,k,j;
double J,s;

int maxim(int * a, int n)
{
    int  maxa=a[1];
    for(int i=1;i<=n;i++)
        if(a[i]>maxa) maxa=a[i];
    return maxa;
}

int minim(int * a, int n)
{
    int  mina=a[1];
    for(int i=1;i<=n;i++)
        if(a[i]<mina) mina=a[i];
    return mina;
}

int f(int * a,int n,int N)
{
    int k=0;
    for(int i=1;i<=n;i++)
        if(a[i]!=N) k++;

    return k;

}

int imax (int *a, int n)
{
    for (int i=1;i<=n;i++)
        if(a[i]==maxim(a,n))
         return i;
}

int imin (int *a, int n)
{
    for (int i=1;i<=n;i++)
        if(a[i]==minim(a,n))
         return i;
}

int main()
{
    fin >> n;

    for(i=1;i<=n;i++)
    {
        fin >>a[i];
        b[i]=a[i];
        s+=a[i];
    }

    J=s/n;
    j=s/n;

    if (j!=J) fout << "-1";
    else
    {
        while(f(a,n,J)!=0)
        {
            M++;
            k=J-minim(a,n);
            a[imin(a,n)]+=k;
            a[imax(a,n)]-=k;
        }

        fout << M << endl;

        while(f(b,n,J)!=0)
        {
            S=imax(b,n);
            D=imin(b,n);

            M++;
            k=J-minim(b,n);
            fout << S << " " << D << " "<< k <<endl;
            b[D]+=k;
            b[S]-=k;
        }
    }


    return 0;
}