Cod sursa(job #1217796)

Utilizator MaarcellKurt Godel Maarcell Data 8 august 2014 11:01:48
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

struct suma{
    int x, y, z;
    int sum;
};

int N,S,K, a[100000]; suma sume[2000000]; bool g;

inline bool cmp(suma a, suma b){
    return a.sum<b.sum;
}
int main(){
    ifstream in("loto.in");
    ofstream out("loto.out");
    in >> N >> S;

    int i,j,k,l,r,aux,mid;
    for (i=1; i<=N; i++)
        in >> a[i];

    for (i=1; i<=N; i++)
        for (j=i; j<=N; j++)
            for (k=j; k<=N; k++){
                sume[++K].sum=a[i]+a[j]+a[k];
                sume[K].x=a[i];
                sume[K].y=a[j];
                sume[K].z=a[k];
            }

    sort(sume+1,sume+K+1,cmp);

    g=0;
    for (i=1; i<=N && !g; i++)
        for (j=i; j<=N && !g; j++)
            for (k=j; k<=N && !g; k++){
                aux=S-(a[i]+a[j]+a[k]);
                l=1; r=K;
                while (l<r && !g){

                    mid=(l+r)/2;
                    if (sume[mid].sum>aux)
                        r=mid-1;
                    else if (sume[mid].sum<aux)
                        l=mid+1;
                    else{
                        g=1;
                        out << sume[mid].x << " " << sume[mid].y << " " << sume[mid].z << " " << a[i] << " " << a[j] <<  " " << a[k];
                    }
                }
            }


    if (!g)
        out << -1;

    return 0;
}