Cod sursa(job #2605318)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 24 aprilie 2020 19:03:10
Problema Loto Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int NMAX = 100;
struct loto
{
    int viz[7] , p[7];
};
map <int , loto> m;
int v[NMAX + 5] , sol[7];
void get_sol(int S)
{
    for(int i = 6 , s = S ; i >= 1 ; s = s - m[s].p[i] , i --)
        sol[i] = m[s].p[i];
    sort(sol + 1 , sol + 7);
    for(int i = 1 ; i <= 6 ; i ++)
        printf("%d " , sol[i]);
}
loto constructor(int poz , int val)
{
    loto temp;
    memset(temp.viz , 0 , sizeof(temp.viz));
    memset(temp.p , 0 , sizeof(temp.p));
    temp.viz[poz] = 1;
    temp.p[poz] = val;
    return temp;
}
int main()
{
    freopen("loto.in" , "r" , stdin);
    freopen("loto.out" , "w" , stdout);
    int n , S , i , j , new_key;
    scanf("%d%d" , &n , &S);
    for(i = 1 ; i <= n ; i ++)
        scanf("%d" , &v[i]);
    map <int , loto>::iterator it;
    m.insert({0 , constructor(0 , 0)});
    for(it = m.begin() ; it != m.end() && (*it).first < S ; it ++)
        for(i = 1 ; i <= n ; i ++)
            for(j = 0 ; j <= 5 ; j ++)
                if((*it).second.viz[j] == 1)
                {
                    int new_key = (*it).first + v[i];
                    if(m.find(new_key) == m.end())
                        m.insert({new_key , constructor(j + 1 , v[i])});
                    else
                    {
                        if(m[new_key].viz[j + 1] == 0)
                        {
                            m[new_key].viz[j + 1] = 1;
                            m[new_key].p[j + 1] = v[i];
                        }
                    }
                }
    if(m.find(S) == m.end())
        printf("-1\n");
    else
    {
        if(m[S].viz[6] == 0)
            printf("-1\n");
        else
            get_sol(S);
    }
    return 0;
}