Cod sursa(job #855779)

Utilizator marialivia16Chiorean Maria Livia marialivia16 Data 15 ianuarie 2013 16:55:53
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include<cstdio>
#include <vector>
#define MAXN 10900
#define mod 666013
using namespace std;
vector <long long> h[mod];
long long S,sum,sum2,a[MAXN];
int find(long long x)
{
	long long index=x%mod;
   int i;
	for(i=1;i<h[index].size();++i)
		if(h[index][i]==x) return 1;
	return 0;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    int N,sem;
    long long i,j,k;
    scanf("%d %lld",&N,&S);
    for(i=1;i<=N;i++)
                    scanf("%lld",&a[i]);
    
    for(i=1;i<=N;i++)
    {
                     for(j=1;j<=N;j++)
                     {
                                      for(k=1;k<=N;k++)
                                      {
                                                       sum=a[i]+a[j]+a[k];
                                                       if(sum<S && !find(sum))
                                                                h[sum%mod].push_back(sum);
                                      }
                     }
    }
    
    sem=1;
    for(i=1;i<=N&&sem;i++)
    {
                     for(j=1;j<=N&&sem;j++)
                     {
                                      for(k=1;k<=N&&sem;k++)
                                      {
                                                       sum2=a[i]+a[j]+a[k];
                                                       if(find(S-sum2))
                                                       {
                                                                  sem=0;
                                                                  printf("%lld %lld %lld ",a[i],a[j],a[k]);
                                                                  S=S-sum2;
                                                       }
                                      }
                     }
     }

    
    if(sem==0)
    {
              for(i=1;i<=N;i++)
              {
                     for(j=1;j<=N;j++)
                     {
                                      for(k=1;k<=N;k++)
                                      {
                                                       sum2=a[i]+a[j]+a[k];
                                                       if ((S==sum2)&&find(sum2)) 
                                                       {
                                                          printf("%lld %lld %lld ",a[i],a[j],a[k]);
                                                          i=j=k=N;
                                                       }
                                     }      
                     }
              }
    }
    else printf("-1");     

    return 0;
}