Cod sursa(job #1075874)

Utilizator andreeadeacAndreea Ioana Deac andreeadeac Data 9 ianuarie 2014 17:59:26
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <fstream>
using namespace std;

ifstream f("loto.in");
ofstream g("loto.out");
const int N=1000000;
int v[101],a[N+1],n;
int pozdiv(int li, int lf){
    int i,j,piv,aux;
    i=li-1;
    j=lf+1;
    piv=a[li];
    do{
        do{i++;} while(a[i]<piv);
        do{j--;} while(a[j]>piv);
        if(i<j){
            aux=a[i];
            a[i]=a[j];
            a[j]=aux;
        }
    }while(i<j);
    return j;
}

void qs(int li, int lf,int a[N+1], int n){
    int m;
    if(li==lf)
        return;
    m=pozdiv(li,lf);
    qs(li,m,a,n);
    qs(m+1,lf,a,n);
}
bool cb(int x,  int a[N+1], int nr){
    int i=0,pas=1<<29;
    while(pas!=0){
        if(i+pas<=nr && a[i+pas]<=x)
            i+=pas;
        pas/=2;
    }
    if(a[i]==x)
        return true;
    else
        return false;
}
void scrie(int su){
    int i,j,k;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
                if(v[i]+v[j]+v[k]==su){
                    g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
                    return;
                }
}
int main()
{
    int nr=0,j,k,i,su,s;
    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++;
                a[nr]=v[i]+v[j]+v[k];
            }
    qs(1,nr,a,nr);
    //for(i=1;i<=nr;i++)
    //    g<<a[i]<<" ";
    //g<<"\n";
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++){
                su=s-v[i]-v[j]-v[k];
                if(cb(su,a,nr)){
                    g << v[i] << " " << v[j] << " " << v[k] << " ";
                    scrie(su);
                    return 0;
                }
            }
    g<<"-1";
    return 0;
}