Cod sursa(job #1090001)

Utilizator Mitsa3Neamt Mihai Mitsa3 Data 22 ianuarie 2014 10:40:51
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstdlib>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
#define MAX 103
int a[MAX],v[MAX*MAX*MAX];
int n, s, k;
bool caut_bin(int x) {
    int st,dr,mid;
    st=1;dr=k;
    while(st<=dr) {

        mid=(st+dr)/2;
        if(v[mid]==s-x)
            return 1;
        else if(v[mid]<s-x)
            st=mid+1;
        else dr=mid-1;
    }
    return 0;
}

int main()
{

    fin >> n >> s;
    int m, m2;
    for(int i = 1; i<=n; i++)
        fin >> a[i];
    for(int i = 1; i<=n; i++)
        for(int j = i; j<=n; j++)
            for(int z = j; z<=n; z++)
                v[k] = a[i] + a[j] + a[z],k++;
    sort(v+1,v+k+1);
    bool ok = 0;
    for(int i = 1; i<=k; i++) {
        if(caut_bin(v[i])) {
            m = v[i];
            m2 = s - v[i];
            ok = 1;
            break;
        }
    }
    if(ok) {
        for(int i = 1; i<=n; i++)
            for(int j = i; j<=n; j++)
                for(int z = j; z<=n; z++)
                    if(m == (a[i] + a[j] + a[z])){
                        fout << a[i] << " " << a[j] << " " << a[z] << " ";
                        goto mihai;
                    }
        mihai:
        for(int i = 1; i<=n; i++)
            for(int j = i; j<=n; j++)
                for(int z = j; z<=n; z++)
                    if(m2 == a[i] + a[j] + a[z]){
                        fout << a[i] << " " << a[j] << " " << a[z] << " ";
                        return 0;
                    }

    }
    else fout << -1 << "\n";
    return 0;
}