Cod sursa(job #1534641)

Utilizator diana97Diana Ghinea diana97 Data 23 noiembrie 2015 20:58:39
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <map>

using namespace std;

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

const int NMAX = 100 + 1;

struct Suma {
    int a, b, c, s;
};

int n, s, nr_sume;
int v[NMAX];
Suma suma[NMAX * NMAX * NMAX];

void citeste() {
    f >> n >> s;
    for (int i = 1; i <= n; i++)
        f >> v[i];
}

void init() {
    int aux;
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int k = j; k <= n; k++) {
                aux = v[i] + v[j] + v[k];
                if (aux > s) continue;

                ++nr_sume;

                suma[nr_sume].s = aux;
                suma[nr_sume].a = i;
                suma[nr_sume].b = j;
                suma[nr_sume].c = k;
            }
}

inline bool comp(Suma x, Suma y) {
    return x.s < y.s;
}

inline bool sume_diferite(Suma x, Suma y) {
    if (x.a == y.a || x.a == y.b || x.a == y.c) return false;
    if (x.b == y.b || x.b == y.b || x.b == y.c) return false;
    if (x.c == y.c || x.c == y.b || x.c == y.c) return false;

    return true;
}

void scrie(Suma x, Suma y) {
    g << v[x.a] << ' ' << v[x.b] << ' ' << v[x.c] << ' ';
    g << v[y.a] << ' ' << v[y.b] << ' ' << v[y.c] << '\n';
}

void rezolva() {
    int s1, s2;
    int i, j, k;

    bool done;

    i = 1; j = nr_sume;

    while(i <= j) {
        s1 = suma[i].s;
        s2 = s - suma[i].s;

        while (j >= i && suma[j].s > s2) j--;

        if (i > j) {
            g << -1;
            break;
        }

        if (suma[j].s != s2) {
            i++;
            continue;
        }

        scrie(suma[i], suma[j]);
        break;
    }

    if (i > j) g << -1;
}

int main() {
    citeste();
    init();
    sort(suma + 1, suma + nr_sume + 1, comp);
    rezolva();
    return 0;
}