Cod sursa(job #1317934)

Utilizator andrettiAndretti Naiden andretti Data 15 ianuarie 2015 13:30:58
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<stdio.h>
#include<algorithm>
#include<set>
#define mp make_pair
#define maxn 105
#define iter set< pair<int,int> >::iterator
using namespace std;

int n,S,ok;
int a[maxn];
set< pair<int,int> > arb;
iter sol;

void read()
{
    scanf("%d%d",&n,&S);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
}

void solve()
{
    iter it,cnt;

    arb.insert(mp(0,0));
    for(int i=1;i<=n;i++)
     for(int j=1;j<=6;j++)
     {
        for(it=arb.begin();it!=arb.end();it++)
         if(it->first+j*a[i]<=S && it->second+j<=6)
         {
             cnt=arb.find( mp(it->first+j*a[i],it->second+j) );

             if(cnt==arb.end())
             {
                 arb.insert( mp(it->first+j*a[i],it->second+j) );
                 if(it->first+j*a[i]==S && it->second+j==6)
                 {
                     sol=arb.find( mp(it->first+j*a[i],it->second+j) );
                     ok=1; return;
                 }
             }
         }
     }
}

void print(iter it)
{
    iter cnt;
    for(int i=1;i<=n;i++)
    {
        cnt=arb.find( mp(it->first-a[i],it->second-1) );
        if(cnt!=arb.end())
        {
            printf("%d ",a[i]);
            print(cnt); break;
        }
    }
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    read();
    solve();
    if(!ok) printf("-1");
    else print(sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}