Cod sursa(job #1294888)

Utilizator mariusn01Marius Nicoli mariusn01 Data 18 decembrie 2014 13:48:14
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");

struct str{
    int a;
    int b;
    int c;
    int s;
};

int cmp(str a, str b) {
    return a.s < b.s;
}

str x[1000002];
int n,S[10],u,st,dr,mid,i,j,k,sum, L;
int v[101];
int main(){
    fin>>n>>L;
    for(i=1;i<=n;i++)
        fin>>v[i];

    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++) {
                u++;
                x[u].a = v[i];
                x[u].b = v[j];
                x[u].c = v[k];
                x[u].s = v[i]+v[j]+v[k];
            }

    sort(x+1, x+u+1, cmp);

    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++)
            for (k=j;k<=n;k++) {
                sum = L-(v[i]+v[j]+v[k]);
                st = 1;
                dr = u;
                while (st <= dr) {
                    mid = (st + dr)/2;
                    if (sum == x[mid].s) {
                        S[1] = x[mid].a;
                        S[2] = x[mid].b;
                        S[3] = x[mid].c;
                        S[4] = v[i];
                        S[5] = v[j];
                        S[6] = v[k];
                        sort(S+1, S+7);
                        for (i=1;i<=6;i++)
                            fout<<S[i]<<" ";
                        return 0;
                    }
                    if (sum < x[mid].s)
                        dr = mid-1;
                    else
                        st = mid+1;
                }
            }
    fout<<-1;
    return 0;
}