Cod sursa(job #753956)

Utilizator mihai96alexOprea Mihai Alexandru mihai96alex Data 30 mai 2012 21:10:43
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
using namespace std;
int v[1000005][4];


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


int main()
{
    int N,S,a[105],i,j,k,p=0;
    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][0]=a[i]+a[j]+a[k];
		v[p][1]=a[i];
		v[p][2]=a[j];
		v[p][3]=a[k];
	}
    qsort(1,p);
    for(i=1;i<=p;i++)
    {
		if(v[i][0]>S) break;
		int min=1,max=p,mij;
		while(min<=max)
		{
			mij=min+(max-min)/2;
			if(v[mij][0]==S-v[i][0])
			{

				fout<<v[mij][1]<<" "<<v[mij][2]<<" "<<v[mij][3]<<" "<<v[i][1]<<" "<<v[i][2]<<" "<<v[i][3];
				return 0;
			}
			else if(v[mij][0]>S-v[i][0])
				min=mij+1;
			else max=mij-1;
		}
    }
    fout<<-1;
    return 0;    
}