Cod sursa(job #1787488)

Utilizator TudorFinaruTudor Cristian Finaru TudorFinaru Data 24 octombrie 2016 19:05:36
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include<algorithm>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int n,s,a[103],nr;
struct rf {int x;int y;int z;int s;}v[1000004];

bool comp(rf x, rf y)
{
    return x.s<y.s;
}

int main()
{
    int i,j,k;
    //citire
    f>>n>>s;
    for(i=1;i<=n;i++) f>>a[i];
    //formare structura cu sumele a cate 3 numere
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                v[++nr].s=a[i]+a[j]+a[k];
                v[nr].x=a[i]; v[nr].y=a[j]; v[nr].z=a[k];
            }
    //sortare
    sort(v+1,v+n+1,comp);
    //cautarea binara a sumelor compatibile
    int mij,st,dr,suma;
    for(k=1;k<=nr;k++)
    {
        st=1;dr=nr; suma = s-v[k].s;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(suma==v[mij].s) //am gasit solutia
            {
                g<<v[k].x<<' '<<v[k].y<<' '<<v[k].z<<' '<<v[mij].x<<' '<<v[mij].y<<' '<<v[mij].z<<'\n';
                f.close(); g.close();
                return 0;
            }
            else if(suma>v[mij].s) st=mij+1;
                 else dr=mij-1;
        }
    }
    g<<-1<<'\n';
    f.close();
    g.close();
    return 0;
}