Pagini recente » Cod sursa (job #398634) | Cod sursa (job #3193760) | Cod sursa (job #1899475) | Cod sursa (job #847255) | Cod sursa (job #157646)
Cod sursa(job #157646)
//(c) Marina
//loto - infoarena
//Complexitate: O(N^3)
//Memorie: O(N^3)
using namespace std;
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define MAXN 101
#define MAX 1000001
int N, S;
int v[MAXN];
struct suma
{
int s, na, nb, nc;
}sum[MAX];
int nr;
struct cmp{
bool operator()(const suma &a, const suma &b)const
{
if(a.s<b.s)return 1;
return 0;
}
};
int caut(int val)
{
int i,cnt;
int a=0, b=nr;
for(i=1, cnt=(1<<20); cnt ; cnt>>=1)
if(i+cnt<=b)
if(sum[i+cnt].s<=val) i+=cnt;
if(sum[i].s==val) return i;
return 0;
while(a <= b)
{
int mij = (a+b)/2;
if(sum[mij].s == val) return mij;
else if(sum[mij].s > val) b = mij-1;
else a = mij+1;
}
return 0;
}
int main()
{
freopen(INPUT, "r", stdin);
freopen(OUTPUT, "w", stdout);
scanf("%d %d", &N, &S);
int i;
for(i = 1; i <= N; ++i) scanf("%d", &v[i]);
int j, k;
for(i = 1; i <= N; ++i)
for(j = 1; j <= N; ++j)
for(k = 1; k <= N; ++k)
sum[++nr].s = v[i] + v[j] + v[k],
sum[nr].na = v[i],
sum[nr].nb = v[j],
sum[nr].nc = v[k];
//qsort(sum+1, nr, sizeof(sum[0]), comp);
sort(sum+1, sum+nr+1,cmp());
int ok = 0;
for(i = 1; i <= nr && sum[i].s<=S && !ok; ++i)
{
int j;
if(j = caut(S-sum[i].s))
{
ok = 1;
printf("%d %d %d %d %d %d\n", sum[i].na, sum[i].nb, sum[i].nc, sum[j].na, sum[j].nb, sum[j].nc);
}
}
if(!ok) printf("-1\n");
return 0;
}