Cod sursa(job #2787586)

Utilizator db_123Balaban David db_123 Data 23 octombrie 2021 18:37:23
Problema Loto Scor 75
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <fstream>
#include <algorithm>
#include <map>

using namespace std;

ifstream cin("loto.in");
ofstream cout("loto.out");

int   n,sum;
int   v[101];
int   frecv[101]={0};
bool  visited[101]={0};
bool  gata = false;

const int   TOTAL = 6;
int currentSum=0;
int currentCount=0;

bool isOK(int i)
{
    if (currentCount < TOTAL && (currentSum + v[i] <= sum))
        return true;
    return false;
}
bool isDone()
{
    if(currentCount == TOTAL && currentSum == sum)
        return true;
    return false;
}
void display()
{
    for(int i = 0 ; i < n ; i++)
    {
        while(frecv[i]>0)
        {
            cout << v[i] <<" ";
            frecv[i]--;
        }
    }
}
void back()
{
    /// base condition
    if(isDone() && !gata)
    {
        gata = true;
        display();
        return;
    }


    /// recursive function
    for(int i = 0 ; i < n ; i++)
    {
        if ( isOK(i))
        {
            frecv[i]++;
            currentCount++;
            currentSum+=v[i];
            back();
            frecv[i]--;
            currentCount--;
            currentSum-=v[i];
        }
    }
}

struct grup3
{
    int sum;
    int nr1;
    int nr2;
    int nr3;
};

multimap<int,grup3> grupuri;
multimap<int,grup3>::iterator it,itSearch;

int main()
{
    cin>>n>>sum;
    for(int i =0 ; i < n ; i++)
        cin>>v[i];

    sort(v,v+n);

    /// generate all 3 number combinations
    grup3 gr;
    for(int i = 0 ; i < n;++i)
    {
        for(int j = i-1 ; j < n ; ++j  )
        {
            for(int k = j-1; k < n ;k++)
            {
                gr.nr1 = v[i];
                gr.nr2 = v[j];
                gr.nr3 = v[k];
                gr.sum = gr.nr1 + gr.nr2 + gr.nr3;
                grupuri.insert({gr.sum,gr});
            }
        }
    }

    for(it = grupuri.begin(); it != grupuri.end();it++)
    {
        int sumaGrup = it->first;
        itSearch     = grupuri.find(sum-sumaGrup);

        if(itSearch != grupuri.end())
        {
            cout << it->second.nr1 << " "<< it->second.nr2 << " "<< it->second.nr3 << " ";
            cout << itSearch->second.nr1 << " "<< itSearch->second.nr2 << " "<< itSearch->second.nr3 ;

            return 0;
        }
    }

    cout << "-1";
    return 0 ;

    //back();

    ///take first element six times
    frecv[0] = 6;
    currentCount = 6;
    currentSum = v[0]*frecv[0];
    int i = 1;
    int smallest = 0,bigger =0;

    while(currentSum != sum && currentCount == TOTAL )
    {
        /// increase sum
        ///     remove smallest element
        for(int j = 0 ; j < n-1 ; j ++)
        {
            if(frecv[j]>0)
            {
                smallest = j;
                frecv[j]--;
                currentSum -=v[j];
                currentCount--;
                break;
            }
        }

        ///     add a bigger element
        for(int j = smallest+1 ; j < n ; j ++)
        {
            bigger = j;
            frecv[j]++;
            currentSum +=v[j];
            currentCount++;
            break;
        }
    }

    if(currentSum != sum)
        cout<<"-1";
    else
    {
        display();
    }

    return 0;
}