Cod sursa(job #2508102)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 11 decembrie 2019 15:53:25
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;

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

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

//true daca a < b
//false altfel
bool cmp(suma a, suma b)
{
    return a.sum < b.sum;
}

int main()
{
    int n,S,s,ki=0,val;
    fin>>n>>S;
    int v[101];

    suma sume[1000001];

    for(int i=1;i<=n;i++)
        fin>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int k=j;k<=n;k++)
            {
                sume[ki].sum = v[i]+v[j]+v[k];
                sume[ki].x = v[i];
                sume[ki].y = v[j];
                sume[ki].z = v[k];
                ki++;
            }

    sort(sume,sume+ki,cmp);

    bool ok = 0;
    for(int i=0;i<ki;i++)
    {
        val=S-sume[i].sum;
        int l=0,r=ki-1,m,sol=-1;
        while(l<=r)
        {
            m=(l+r)/2;
            if(sume[m].sum==val){sol=m;break;}
            else if(sume[m].sum<val)l=m+1;
            else if(sume[m].sum>val)r=m-1;
        }
        if(sol>=0)
        {
            ok = 1;
            fout << sume[i].x << " " << sume[i].y << " " << sume[i].z << " ";
            fout << sume[sol].x << " " << sume[sol].y << " " << sume[sol].z;
            break;
        }
    }
    if(!ok)
        fout << -1;
    return 0;
}