Cod sursa(job #49129)

Utilizator the_dragon_of_rockTzogorean Alex the_dragon_of_rock Data 5 aprilie 2007 13:13:46
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<fstream>
using namespace std;
int a[200],n,s,suma[500],m,a1[500],a2[500],a3[500];

void qsort(int st, int dr)
{
    if (st<dr)
        {
            int i=st,j=dr,d=0,aux;
            while(i<j)
                {
                if (suma[i]>suma[j])
                    {
                        aux=suma[i];
                        suma[i]=suma[j];
                        suma[j]=aux;
                        aux=a1[i];
                        a1[i]=a1[j];
                        a1[j]=aux;
                        aux=a2[i];
                        a2[i]=a2[j];
                        a2[j]=aux;
                        aux=a3[i];
                        a3[i]=a3[j];
                        a3[j]=aux;
                        d=1-d;
                    }
                i+=d;
                j-=1-d;
                }
            qsort(st,i-1);
            qsort(i+1,dr);
        }
}

int poz(int st, int dr, int t)
{
    int m=(st+dr)/2;
    if (suma[m]+suma[t]==s && m!=t)   return m;
    if (st>dr)   return -1000;
    if (suma[m]+suma[t]>s)
        return poz(st,m-1,t);
    else
        return poz(m+1,dr,t);
}

int main()
{
    ifstream in("loto.in");
    in>>n>>s;
    int i,gata=0,k;
    for (i=1;i<=n;i++)
        in>>a[i];
    in.close();
    
    int j;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            for (k=1;k<=n;k++)
                {
                    suma[++m]=a[i]+a[j]+a[j];
                    a1[m]=a[i];
                    a2[m]=a[j];
                    a3[m]=a[k];
                }
    qsort(1,m);
    
    ofstream out("loto.out");
    for (i=1;i<m && !gata;i++)
        {
            k=poz(i+1,m,suma[i]);
            if (k>0)
                {
                    out<<a1[i]<<" "<<a2[i]<<" "<<a3[i]<<" ";
                    out<<a1[k]<<" "<<a2[k]<<" "<<a3[k];
                    gata=1;
                }
        }
    if (gata==0)
        out<<-1;
        
    return 0;
}