Cod sursa(job #1456313)

Utilizator xraven78Eduard Mihes xraven78 Data 30 iunie 2015 12:15:06
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <math.h>
#include <bits/stdc++.h>
using namespace std;

int cautare (long *v, long x, int l, int r) {
    if(l <= r) {
        int m = (l+r)>>1;
        if(v[m] < x)
            return cautare(v, x, m+1, r);
        if(v[m] > x)
            return cautare(v, x, l, m-1);
        if(v[m] == x)
            return m;
    }
    return -1;
}

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

    int n;
    long S;
    f>>n>>S;

    long *v = (long *) malloc (n * sizeof(long));
    int i, j, k;
    for(i = 0;i < n;i++)
       f>>v[i];

    long *sume3 = (long *) malloc (pow(n, 3)*sizeof(long));
    int z = 0;

    for(i = 0;i < n;i++)
        for(j = i;j < n;j++)
            for(k = j;k < n;k++) {
                sume3[z++] = v[i] + v[j] + v[k];
            }

    k = z-1;
    sort(sume3, sume3 + k + 1);

    int s;
    z = -1;
    for(i = 0;i <= k;i++) {
        s = S-sume3[i];
        if(sume3[k] < s)
            continue;
        if(sume3[i] > s) {
            break;
        }
        z = cautare(sume3, s, i, k);
        if(z != -1)
            break;
    }
    if(z == -1) {
       g<<"-1\n";
    }
    else {
        long i1, i2, j1, j2, k1, k2, s1, s2, s;
        int adi1 = 0, adi2 = 0;
        s1 = sume3[i];
        s2 = sume3[z];
        for(i = 0;i < n;i++)
            for(j = i;j < n;j++)
                for(k = j;k < n;k++) {
                    s = v[i] + v[j] + v[k];
                    if(s == s1 && adi1 == 0) {
                        adi1 = 1;
                        i1 = v[i];
                        j1 = v[j];
                        k1 = v[k];
                        if(adi2) {
                            i = n;
                            j = n;
                            k = n;
                        }
                    }
                    if(s == s2 && adi2 == 0) {
                        adi2 = 1;
                        i2 = v[i];
                        j2 = v[j];
                        k2 = v[k];
                        if(adi1) {
                            i = n;
                            j = n;
                            k = n;
                        }
                    }
                }
       g<<i1<<" "<<j1<<" "<<k1<<" "<<i2<<" "<<j2<<" "<<k2;
    }

    f.close();
    g.close();
    return 0;
}