Cod sursa(job #1833657)

Utilizator Gigel-FroneGigel Fronel Gigel-Frone Data 22 decembrie 2016 21:12:40
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <cstdio>
#define prim 103
#define mod 666013

using namespace std;

int n, s, h[mod+1], v[101];

void add(int x)
{
    int k=(1LL*x*prim)%mod;
    while(h[k] && h[k]!=x)
    {
        k++;
        if(k == mod) k=0;
    }
    h[k]=x;
}

bool find(int x)
{
    int k=(1LL*x*prim)%mod;
    while(h[k])
    {
        if(h[k] == x) return 1;
        k++;
        if(k == mod) k=0;
    }
    return 0;
}

void print(int s)
{
    for(int i1=1; i1<=n; i1++)
        for(int i2=1; i2<=n; i2++)
            for(int i3=1; i3<=n; i3++)
            {
                if(v[i1]+v[i2]+v[i3] == s)
                {
                    printf(" %d %d %d", v[i1], v[i2], v[i3]);
                    return;
                }
            }
}

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

    scanf("%d%d", &n, &s);
    for(int i=1; i<=n; i++) scanf("%d", &v[i]);

    for(int i1=1; i1<=n; i1++)
        for(int i2=1; i2<=n; i2++)
            for(int i3=1; i3<=n; i3++) add(v[i1]+v[i2]+v[i3]);

    for(int i1=1; i1<=n; i1++)
        for(int i2=1; i2<=n; i2++)
            for(int i3=1; i3<=n; i3++)
            {
                int x=v[i1]+v[i2]+v[i3];
                if(s >= x && find(s-x))
                {
                    printf("%d %d %d", v[i1], v[i2], v[i3]);
                    print(s-x);
                    return 0;
                }
            }
    printf("-1");
    return 0;
}