Cod sursa(job #753942)

Utilizator mihai96alexOprea Mihai Alexandru mihai96alex Data 30 mai 2012 20:53:55
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include<fstream>
using namespace std;
int v[1000005],ci[1000005],cj[1000005],ck[1000005];


void qsort(int st, int dr)
{
    int min,max,mij,aux;
    min=st;
    max=dr;
    mij=v[st+(dr-st)/2];
    do
    {
    while(v[min]<mij) min++;
    while(v[max]>mij) max--;
    if(min<=max)
    {
                aux=v[min];
                v[min++]=v[max];
                v[max--]=aux;
                min--;max++;
                aux=ci[min];
                ci[min++]=ci[max];
                ci[max--]=aux;
                min--;max++;
                aux=cj[min];
                cj[min++]=cj[max];
                cj[max--]=aux;
                min--;max++;
                aux=ck[min];
                ck[min++]=ck[max];
                ck[max--]=aux;
    }
    }while(min<=max);
    if(st<max) qsort(st,max);
    if(min<dr) qsort(min,dr);
}

int cautbin(int st,int dr,int x)
{
     if(st>dr) return -1;
     int mij;
     mij=st+(dr-st)/2;
     if(st<=dr)
     {if(v[mij]==x) return mij;
     else if(v[mij]>x) cautbin(st,mij-1,x);
     else if(v[mij]<x) cautbin(mij+1,dr,x);}
}
     

int main()
{
    int N,S,a[105],i,j,k,p=0,x;
    ifstream fin("loto.in");
    ofstream fout("loto.out");
    fin>>N>>S;
    for(i=1;i<=N;i++)
    fin>>a[i];
    for(i=1;i<=N;i++)
    for(j=1;j<=N;j++)
    for(k=1;k<=N;k++)
    {v[++p]=a[i]+a[j]+a[k];
    ci[p]=a[i];cj[p]=a[j];ck[p]=a[k];}
    qsort(1,p);
    for(i=1;i<=p;i++)
    {
    x=cautbin(1,p,S-v[i]);
    if(x>0 && v[i]+v[x]==S)
        {fout<<ci[i]<<" "<<cj[i]<<" "<<ck[i]<<" "<<ci[x]<<" "<<cj[x]<<" "<<ck[x];
        return 0;}
    }
    fout<<-1;
    return 0;    
}