Cod sursa(job #812426)

Utilizator krissu93FMI Tiugan Cristiana Elena krissu93 Data 13 noiembrie 2012 21:00:05
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

int n;
int nr=0;
long long  s;
long a[110];
long long b[1000010];

int cauta(long long  sp,int n)
{
	int i,pas;
	for (pas=1;pas<n;pas<<=1);
	for (i=0;pas;pas>>=1)
	{
		if (i+pas<n && (b[i+pas]<=sp))
			i+=pas;}
	
	if (b[i]==sp) return i;
		else return -1;
}

int main()
{
	int i,j,k;
	int i2,j2,k2;
	long long su;
	int ok=0;
	in>>n>>s;
	for (i=1;i<=n;i++)
		in>>a[i];
	nr++;
	for(i=1;i<=n;i++)
		for (j=i;j<=n;j++)
			for(k=j;k<=n;k++)
				b[++nr]=a[i]+a[j]+a[k];
	sort(b+1,b+nr+1);
	for (i=1;i<=nr;i++)
	{
		su=s-b[i];
		if (cauta(su,nr)!=-1)
		{
			ok=0;
			for (i2=1;i2<=n && ok==0;i2++)
				for(j2=i2;j2<=n && ok==0; j2++)
					for(k2=j2;k2<=n && ok==0;k2++)
						if (a[i2]+a[j2]+a[k2]==b[i])
						{
							out<<a[i2]<<' '<<a[j2]<<' '<<a[k2]<<' ';
							ok=1;
						}
			
			for(i2=1;i2<=n;i2++)
				for(j2=i2;j2<=n ;j2++)
					for(k2=j2;k2<=n;k2++)
						if (a[i2]+a[j2]+a[k2]==su)
						{
							out<<a[i2]<<' '<<a[j2]<<' '<<a[k2]<<' ';
							return 0;
						}
		}
	}
	out<<-1;
	return 0;
}