Cod sursa(job #1222015)

Utilizator g3ppyStoian Vlad g3ppy Data 21 august 2014 21:59:45
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <algorithm>
#include <set>
#include <vector>
#include <stdio.h>

#define NMAX 101
#define llong long long

using namespace std;

struct three {
    three(int zero, int one, int two) {
        this->zero = zero;
        this->one = one;
        this->two = two;
        this->sum = zero + one + two;
    }

    llong sum;
    int zero, one, two;
};

int numbers[NMAX];

set<llong> visited;
vector<three> threes;

bool compare_threes(three t1, three t2) {
    return t1.sum < t2.sum;
}

int main() {
    freopen("loto.in", "rt", stdin);
    freopen("loto.out", "wt", stdout);

    llong n, s;
    scanf("%lld %lld\n", &n, &s);


    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }

    threes.reserve(n * n * n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                three element(numbers[i], numbers[j], numbers[k]);

                if (visited.find(element.sum) == visited.end()) {
                    threes.push_back(element);
                    visited.insert(element.sum);
                }
            }
        }
    }

    sort(threes.begin(), threes.end(), compare_threes);

    vector<three>::iterator front_iterator = threes.begin();
    vector<three>::iterator end_iterator = threes.end() - 1;

    while (end_iterator->sum >= front_iterator->sum) {
        llong current_sum = front_iterator->sum + end_iterator->sum;

        if (current_sum == s) {
            printf("%d %d %d %d %d %d\n", front_iterator->zero, front_iterator->one, front_iterator->two, end_iterator->zero, end_iterator->one, end_iterator->two);
            return 0;
        }

        if (current_sum > s) {
            end_iterator--;
        }
        if (current_sum < s) {
            front_iterator++;
        }

    }


    //    for (it = threes.rbegin(); it != threes.rend(); it++) {
    //        llong first_sum = it->first;
    //        llong second_sum = s - first_sum;

    //        sit = threes.find(second_sum);

    //        if (sit != threes.end()) {
    //           printf("%d %d %d %d %d %d\n", it->second.zero, it->second.one, it->second.two, sit->second.zero, sit->second.one, sit->second.two);
    //           return 0;
    //        }
    //    }


    printf("%d\n", -1);

    return 0;
}