Cod sursa(job #1089995)

Utilizator Mitsa3Neamt Mihai Mitsa3 Data 22 ianuarie 2014 10:31:16
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 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 top,bot,mid;
    top=1;bot=k;
    while(top<=bot) {

        mid=(bot+top)/2;
        if(v[mid]==s-x)
            return 1;
        else if(v[mid]<s-x)
            top=mid+1;
        else bot=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+n+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;
}