Cod sursa(job #542945)

Utilizator feelshiftFeelshift feelshift Data 27 februarie 2011 11:59:10
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

struct stuff {
    int sum;
	int first; int second; int third;
};

stuff sum[1000000];

bool comp(stuff first,stuff second);

int main ()
{
    int number, dreamedSum, i, j, k, length, input[101];
	in >> number >> dreamedSum;
    for (i=1; i<=number; i++)
        in >> input[i];

    length=1;
    for (i=1; i<=number; i++)
        for (j=i; j<=number; j++)
            for (k=j; k<=number; k++) {
                sum[length].sum=input[i]+input[j]+input[k];
                sum[length].first=input[i];
                sum[length].second=input[j];
                sum[length].third=input[k];
                length++;
            }

    sort(sum+1, sum+length, comp);

    int left, right, toBeFound, middle;
    for (i=1; i<=length; i++) {
        left=1;
        right=length;
        toBeFound=dreamedSum-sum[i].sum;
        while (left<=right) {
            middle=(left+right)/2;
            if (toBeFound==sum[middle].sum) {
                //printf ("%d %d %d %d %d %d", sum[i].first, sum[i].second, sum[i].third, sum[middle].first, sum[middle].second, sum[middle].third);
				out << sum[i].first << " " << sum[i].second << " " << sum[i].third << " ";
				out << sum[middle].first << " " << sum[middle].second << " " << sum[middle].third << "\n";
                return 0;
            } else {
                if (toBeFound<sum[middle].sum)
                    right=middle-1;
                else
                    left=middle+1;
            }
        }
    }

    out << "-1";
    return 0;
}

bool comp(stuff first,stuff second) {
	return (first.sum < second.sum);
}