Cod sursa(job #886395)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 22 februarie 2013 20:31:19
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include "fstream"
#include "algorithm"
using namespace std;
int ok=1;
struct suma
{
    int va,e1,e2,e3;
}s[1000005];
ifstream f("loto.in");
ofstream g("loto.out");
int cautare_binara(int nr,int suma1,int p)
{
    if(nr==1 && suma1==s[0].va)
        return 0;
    int pr=0,u=nr-1,m;
    if(s[u].va<suma1)
        return -1;
    while(pr<=u)
    {
        m=(pr+u)/2;
        if(s[m].va==suma1)
            return m;
        if(s[m].va<suma1)
            pr=m+1;
        else
            u=m-1;
    }
    return -1;
}
int cmp(suma p1,suma p2)
{
    return p1.va<p2.va;
}
int main()
{
    int nr,suma,sir[105],sume;
    f>>nr>>suma;
    int i;
    for(i=0;i<nr;i++)
        f>>sir[i];
    int j,k,nrs=0;
    for(j=0;j<nr;j++)
        for(k=j;k<nr;k++)
            for(i=k;i<nr;i++)
            {
                s[nrs].e1=sir[j];
                s[nrs].e2=sir[k];
                s[nrs].e3=sir[i];
                s[nrs].va=sir[j]+sir[k]+sir[i];
                nrs++;
            }
    sort(s,s+nrs,cmp);
    for(i=0;i<nrs;i++)
    {
        int rez;
        rez=cautare_binara(nrs,suma-s[i].va,i);
        if(rez!=-1)
        {
            g<<s[i].e1<<" "<<s[i].e2<<" "<<s[i].e3<<" "<<s[rez].e1<<" "<<s[rez].e2<<" "<<s[rez].e3;
            break;
            return 0;
        }
    }
    g<<"-1";
    return 0;
}