Cod sursa(job #1842605)

Utilizator maria15Maria Dinca maria15 Data 7 ianuarie 2017 12:15:23
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

int n, i, j, k, suma, v[102], nr, st, dr, mid, t;
char ok;

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

sum x[1000001];

int main(){
    fin>>n>>suma;
    for(i=1;i<=n;i++)
        fin>>v[i];
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++){
                x[++nr].s = v[i]+v[j]+v[k];
                x[nr].a=v[i];
                x[nr].b=v[j];
                x[nr].c=v[k];
                for(t=nr-1;t>0;t--)
                    if(x[t+1].s<x[t].s){
                        swap(x[t+1].s, x[t].s);
                        swap(x[t+1].a, x[t].a);
                        swap(x[t+1].b, x[t].b);
                        swap(x[t+1].c, x[t].c);
                    }
                    else
                        break;
            }

    for(i=1;i<=nr;i++){
        st=i;
        dr=nr;
        while(st<=dr){
            mid=(st+dr)/2;
            if(x[mid].s+x[i].s == suma){
                fout<<x[mid].a<<" "<<x[mid].b<<" "<<x[mid].c<<" "<<x[i].a<<" "<<x[i].b<<" "<<x[i].c;
                return 0;
            }
            else{
                if(x[mid].s+x[i].s<suma)
                    st=mid+1;
                else
                    dr=mid-1;
            }
        }
    }
    fout<<"-1";

    return 0;
}