Cod sursa(job #880084)

Utilizator avramavram andrei marius avram Data 16 februarie 2013 11:39:46
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n,i,i1,i2,i3,sum,S,v[1000],p,u,aux,m,k;
struct qq
{
    int a;
    int b;
    int c;
    int s;
};
qq elem[1000001];
int cmp(const qq &x,const qq &y)
{
    if(x.s<y.s)
        return 1;
    else
        return 0;
}
 
int main()
{
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>sum;
    for(i=1;i<=n;i++)
        f>>v[i];
    for(i=1;i<=n;i++)
        for(i1=i;i1<=n;i1++)
            for(i2=i1;i2<=n;i2++)
            {
                if(v[i]+v[i1]+v[i2]<=sum)
                {
                elem[++k].s=v[i]+v[i1]+v[i2];
                elem[k].a=i;
                elem[k].b=i1;
                elem[k].c=i2;
                }
            }
    sort(elem+1,elem+k+1,cmp);
    for(i=1;i<=n;i++)
        for(i1=i;i1<=n;i1++)
            for(i2=i1;i2<=n;i2++)
            {
                S=v[i]+v[i1]+v[i2];
                if(S<=sum)
                {
                aux=sum-S;
                p=1;
                u=k;
                while(p<=u)
                {
                    m=(p+u)/2;
                    if(aux<elem[m].s)
                        u=m-1;
                    else
                        if(aux>elem[m].s)
                            p=m+1;
                        else
                        {
                            g<<v[i]<<" "<<v[i1]<<" "<<v[i2]<<" "<<v[elem[m].a]<<" "<<v[elem[m].b]<<" "<<v[elem[m].c];
                            return 0;
                        }
                }
                }
                 
            }
            g<<-1;
            return 0;
}