Cod sursa(job #1081166)

Utilizator Aleks10FMI - Petrache Alex Aleks10 Data 13 ianuarie 2014 11:54:29
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

struct sum{
int a,b,c;
int s;
};

bool cmp(sum x,sum y){
    if(x.s<y.s)
        return 1;
    return 0;
}

sum loto[1000001];
int main()
{
    int i,n,j,k,nr=0;
    long long s,v[101],sp;
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>s;
    for(i=1;i<=n;i++){
        f>>v[i];
    }

    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++){
                nr++;
                loto[nr].s=v[i]+v[j]+v[k];
                loto[nr].a=v[i];
                loto[nr].b=v[j];
                loto[nr].c=v[k];
               // cout<<nr<<" "<<loto[nr].s<<endl;
            }
    sort(loto+1,loto+nr+1,cmp);
    int cauta=0,st,dr,m;
    for(i=1;i<=nr;i++){
        cauta=s-loto[i].s;
        st=1;
        dr=nr;
        while(st<=dr){
            m=(st+dr)/2;
            if(loto[m].s==cauta){
                g<<loto[i].a<<" "<<loto[i].b<<" "<<loto[i].c<<" "<<loto[m].a<<" "<<loto[m].b<<" "<<loto[m].c;
                i=nr+2;
                break;
            }
            else{
                if(loto[m].s<cauta)
                    st=m+1;
                else
                    dr=m-1;
            }
        }
    }
    if(i==nr+1){
        g<<-1;
    }
    return 0;
}

/*#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int i,n;
    long long s,v[101],sp;
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>s;
    for(i=0;i<n;i++){
        f>>v[i];
    }

    //ordonez
    int q;
    int aux=0;
    /*for(i=0;i<n-1;i++){
        for(q=i+1;q<n;q++){
            if(v[i]>v[q]){
                aux=v[i];
                v[i]=v[q];
                v[q]=aux;
            }
        }
    }*/
    /*sort(v+0,v+n);
    //done
    sp=s;
    int j,k,l,m,o,ok=0;
    for(i=0;i<n;i++)
    {
        s=s-v[i];
        for(j=0;j<n;j++)
        {
            s=s-v[j];
            for(k=0;k<n;k++)
            {
                s=s-v[k];
                for(l=0;l<n;l++)
                {
                    s=s-v[l];
                    for(m=0;m<n;m++)
                    {
                        s=s-v[m];
                        for(o=0;o<n;o++)
                        {
                            s=s-v[o];
                            //cout<<s<<'\n';
                            if(s==0)
                            {
                                g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" "<<v[l]<<" "<<v[m]<<" "<<v[o];
                                n=0;
                                ok=1;
                                break;
                            }
                            else
                                s=s+v[o];
                        }
                        s=s+v[m];
                    }
                    s=s+v[l];
                }
                s=s+v[k];
            }
            s=s+v[j];
        }
        s=s+v[i];
    }
    if(ok==0)
        g<<-1;
    return 0;
}
*/