Microbuz ONI VII 2022

/**Aici ai solutia pentru problema microbuz de la ONI VII 2022.
Este o problema simpla cu generarea combinatiilor posibile. Trecand prin toate
combinatiile salvezi solutiile optime. Pentru cerintele 1 si 2
salvezi in combinatii numarul de ori in care ai folosit statia
iar pentru cerinta 3 salvezi setul in care este folosita statia.
Folosind un sistem de numeratie in baza k (numarul de alegeri. k=4 pentru cerintele 1 si 2 , k = 3 pt cerinta 3)
cu n cifre (numarul de statii in cazul nostru, n = 10) putem reprezenta fiecare combinatie posibila.
Este o metoda folositoare cand numarul de combinatii este mic. Avem k^n combinatii. */
#include <fstream>
using namespace std;
ifstream cin("microbuz.in");
ofstream cout("microbuz.out");
int v[12];
int comb[12];
int main()
{
    int cerinta,n ;
    cin>>cerinta;
    for(int i = 1;i<=10;i++)
            cin>>v[i];
    cin>>n;
    if(cerinta==1||cerinta==2)
    {
        /** Vectorul comb ne va spune de cate ori utilizam o statie:
            0 - nu utilizam deloc statia
            1 - o utilizam odata
            2 - o utilizam de 2 ori
            3 - o utilizam de 3 ori.

        Fiecare statie afecteaza distanta in felul urmator :
            d+=comb[i]*i ;
        deoarece i reprezinta cati kilometri sunt parcursi printr-o singura utilizare
        iar comb[i] este numarul de utilizari.

        Costul traseului il putem calcula prin urmatorul fel:
            cost+=comb[i]*v[i]; (de cate ori platim valoarea statiei)

        Daca distanta este egala cu n si costul minimul
        de pana atunci avem o noua solutie.

        Ideea este sa generam toate combinatiile posibile.
        Sunt 4^10 = 2^20 = ~1.05 mil. de combinatii.

        Putem reprezenta fiecare combinatie intr-un sistem de numeratie in baza 4
        folosind 10 cifre. Trecand prin fiecare numar
        de la  0 0 0 0 0 0 0 0 0 0 pana la 3 3 3 3 3 3 3 3 3 3
        vom fi incercat toate combinatiile posibile.

        Trecem prin numere crescator :
        0 0 0 0 0 0 0 0 0 0
        1 0 0 0 0 0 0 0 0 0
        2 0 0 0 0 0 0 0 0 0
        3 0 0 0 0 0 0 0 0 0
        0 1 0 0 0 0 0 0 0 0
        ..............
        3 3 3 3 0 0 0 0 0 0
        0 0 0 0 1 0 0 0 0 0
        ..............
        3 3 3 3 3 3 3 3 3 3
        0 0 0 0 0 0 0 0 0 0 1 (aici ne oprim.)   */

        int d,val,mini=20000,sol[11];
        ///Generam toate combinatiile posibile.
        while(comb[11]!=1) ///cand comb[11] = 1 avem  0 0 0 0 0 0 0 0 0 0 1 ,conditia de oprire.
        {
           comb[1]++;
           if(comb[1]==4)
           {
               /** Aici ne ocupam de situatiile precum :
                3 3 3 3 0 0 0 0 0 0 (adunam 1)
                0 0 0 0 1 0 0 0 0 0
                Modificam toate pozitiile afectate.*/
               int poz = 1;
               while(comb[poz]==4)
               {
                   comb[poz] = 0;
                   comb[poz+1]++;
                   poz++;
               }
           }
           ///Aici ne folosim de combinatia generata.
           d = 0 , val = 0;
           for(int i = 1;i<=10;i++)
           {
              d+=comb[i]*i; ///Calculam distanta
              val+=v[i]*comb[i];///si costul traseului
           }
           ///Daca distanta este egala cu n si costul e minim pastram raspunsul.
           if(d==n&&val<mini)
           {
               mini = val;
               ///In sol[i] pastram de cate ori apare o statie in solutia optima.
               for(int i = 1;i<=10;i++)
                sol[i] = comb[i];
           }
        }
         ///Afisari de raspuns.
        if(cerinta==1)
            cout<<mini;
        if(cerinta==2)
        {
           for(int i = 1;i<=10;i++)
                for(int j = 1;j<=sol[i];j++)
                    cout<<i<<' '<<v[i]<<'\n';
        }

    }
    if(cerinta==3)
    {
        /** Abordare: vom genera toate combinatiile posibile.
        Avem 3 posibilitati pe care le vom codifica astfel in vectorul comb:
        0 - nu face parte din nicio multime
        1 - face parte din multimea 1
        2 - face parte din multimea 2

        EX :
        1 2 3 4 5 6 7 8 9 10 Pozitii
        0 1 2 2 1 2 1 0 0  1 Valoare din vector

        Elementele 1 , 8 , 9  nu fac parte din nicio multime
        Elementele 2, 5, 7, 10 fac parte din multimea 1.
        Elementele 3, 4 , 6 fac parte din multimea 2.

        suma1 = v[2]+v[5]+v[7]+v[10]
        suma2 = v[3]+v[4]+v[6]
        Daca suma1==suma2 si acestea sunt mai mari decat maximul de pana atunci
        avem o noua solutie pe care o salvam.

        Avem 3^10  combinatii posibile (59049)
        Asadar putem genera toate combinatiile.
        Luam combinatiile astfel :
        0 0 0 0 0 0 0 0 0 0
        1 0 0 0 0 0 0 0 0 0
        2 0 0 0 0 0 0 0 0 0
        0 1 0 0 0 0 0 0 0 0
        1 1 0 0 0 0 0 0 0 0
        0 2 0 0 0 0 0 0 0 0
        ...................

        2 2 2 2 2 2 2 2 2 2
        0 0 0 0 0 0 0 0 0 0 1 (aici ne oprim)   */

        ///Suma setului 1 si suma setului 2 pentru o combinatie.
        int sum1 , sum2,maxi=-1;
        ///Pozitiile seturilor din solutia finala.
        int sol1[11] , sol2[11];
        ///marimea setului 1,2.
        int s1cnt = -1 , s2cnt = -1;
        ///Acest while trece prin toate combinatiile posibile.
        while(comb[11]!=1) ///Aici ne oprim.
        {
           comb[1]++;
           if(comb[1]==3)
           {
                /**Aici avem grija de cazurile precum :
                2 2 2 2 2 2 2 2 0 0  (adunam 1)
                0 0 0 0 0 0 0 0 1 0
                modificam toate pozitiile din comb afectate. */
               int poz  = 1;
               while(comb[poz]==3)
               {
                   comb[poz] = 0;
                   comb[poz+1]++;
                   poz++;
               }
           }
           ///Aici ne folosim de combinatia generata.
           sum1 = 0 , sum2 = 0;
           for(int i = 1; i<=10;i++)
           {
               if(comb[i]==1)
                sum1+=v[i];
               if(comb[i]==2)
                sum2+=v[i];
           }
           ///Aici verificam daca avem o noua solutie.
           if(sum1==sum2&&sum1>maxi)
           {
               maxi = sum1;
               s1cnt=0, s2cnt = 0;
               for(int i = 1;i<=10;i++)
               {
                   if(comb[i]==1)
                    sol1[++s1cnt] = i;
                   if(comb[i]==2)
                    sol2[++s2cnt] = i;
               }
           }
        }

        ///Afisarea raspunsurilor.
        cout<<maxi<<'\n';
        for(int i = 1;i<=s1cnt;i++)
            cout<<sol1[i]<<' ';
        cout<<'\n';
        for(int i = 1;i<=s2cnt;i++)
            cout<<sol2[i]<<' ';
    }
    return 0;
}