Cod sursa(job #1020161)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 noiembrie 2013 19:10:26
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

const int N = 101, MEM = 101 * 101 * 101;
int num[MEM], n, s, L[MEM], R[MEM];
int SOL[6];
set <pair <int, int> > ord;

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

int main() {
    fin >> n >> s;
    int MAX = -1, MIN = 2e9;
    for (int i = 0; i < n; ++i) {
        fin >> num[i];
        MIN = min (MIN, num[i]);
        MAX = max (MAX, num[i]);
    }
    if (MAX * 6 < s || MIN * 6 > s) {
        fout << -1;
        return 0;
    }
    fin.close();
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            int nod = n * (i + 1) + j;
            num[nod] = num[i] + num[j];
            L[nod] = i;
            R[nod] = j;
        }
    for (int i = 0; i < n; ++i)
        for (int j = n; j < n * (n + 1); ++j) {
            int nod = n * (n + 1) + i * n * n + (j - n);
            num[nod] = num[i] + num[j];
            L[nod] = i;
            R[nod] = j;
            ord.insert (make_pair (num[nod], nod));
        }
    for (int i = n * (n + 1); i < n * n * n + n * n + n; ++i ) {
        set <pair <int, int> > :: iterator it = ord.lower_bound (make_pair (s - num[i], 0));
        if (it != ord.end()) {
            int sol = (*it).second;
            SOL[0] = num[L[i]], SOL[1] = num[L[R[i]]], SOL[2] = num[R[R[i]]];
            SOL[3] = num[L[sol]], SOL[4] = num[L[R[sol]]], SOL[5] = num[R[R[sol]]];
            sort (SOL, SOL + 6);
            int sum = 0;
            for (int i = 0; i < 6; ++i)
                sum += SOL[i];
            assert(sum == s);
            for (int i = 0; i < 6; ++i)
                fout << SOL[i] << " ";
            return 0;
                }
            }
    fout << -1;
}