Cod sursa(job #2200414)

Utilizator IustinPetrariuIustinian Petrariu IustinPetrariu Data 1 mai 2018 12:27:31
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 101
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
struct loto
{
    int val,a,b,c;
}sume[1000001];
int N,M,sol,S,a[NMAX],nr;
int cmp(loto x, loto y)
{
    return x.val < y.val;
}
void read()
{
    fin>>N>>S;
    for(int i = 1; i <= N; i++)
        fin>>a[i];

}
void cauta(int x, int st, int dr)
{
    int mij;
    while(st <= dr)
    {
        mij=(st+dr)/2;
        if(sume[mij].val==x)
        {
            sol=mij;
            break;
        }
        if(sume[mij].val < x)
            st=mij+1;
        else dr=mij-1;
    }
}
int solve()
{
    sol=-1;
    for(int i =1 ; i <= nr && sume[i].val <= S/2; i++)
        {cauta(S-sume[i].val,i,nr);
         if(sol!=-1)
         {
             fout<<sume[i].a<<" "<<sume[i].b<<" "<<sume[i].c<<" "<<sume[sol].a<<" "<<sume[sol].b<<" "<<sume[sol].c<<'\n';
             return 0;
         }

        }
}
void order()
{
    for(int i =1 ; i <= N; i ++)
        for(int j =i ; j <= N; j ++)
         for(int k = j ; k <= N; k++)
    {
        nr++;
        sume[nr].val=a[i]+a[j]+a[k];
        sume[nr].a=a[i];
        sume[nr].b=a[j];
        sume[nr].c=a[k];
    }
    sort(sume+1,sume+nr+1,cmp);
    solve();
}
int main()
{
    read();
    order();
    return 0;
}