Cod sursa(job #2557236)

Utilizator Codrut112Codrut Copas Codrut112 Data 25 februarie 2020 17:40:49
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int n,s,i,j,l,w[105],nr,u[7],poz1,poz2;
bool ok;
struct loto
{
    int suma;
    int i,j,l;
};
bool comp(loto a,loto b)
{
    return (a.suma<b.suma);

}
loto v[1000001];
int caut(int st,int dr,int sumabuna)
{

  while(st<=dr)
    {
        int mid;
        mid=(st+dr)/2;
        if(v[mid].suma<sumabuna)st=mid+1;
            else if(v[mid].suma>sumabuna) dr=mid-1;
            else return mid;
    }

return 0;

}

int main()
{
    f>>n;
    f>>s;
    for(i=1; i<=n; i++)f>>w[i];
    for(i=1; i<=n; i++)
        for(j=i; j<=n; j++)
            for(l=j; l<=n; l++)
            {
                if(w[i]+w[j]+w[l]<s)
                {
                    nr++;
                    v[nr].suma=w[i]+w[j]+w[l];
                    v[nr].i=w[i];
                    v[nr].j=w[j];
                    v[nr].l=w[l];
                }
            }
    sort(v+1,v+nr+1,comp);

    poz1=1;ok=0;
    while(poz1<=nr and ok==0)
    {
        poz2=caut(poz1,nr,s-v[poz1].suma);
        if(v[poz1].suma+v[poz2].suma==s)ok=1;
        else poz1++;
    }
    if(ok==0)g<<-1;
    else
    {
                u[1]=v[poz1].i;
                u[2]=v[poz1].j;
                u[3]=v[poz1].l;
                u[4]=v[poz2].i;
                u[5]=v[poz2].j;
                u[6]=v[poz2].l;
        sort(u+1,u+7);
        for(i=1; i<=6; i++)g<<u[i]<<' ';
    }
}