Cod sursa(job #711770)

Utilizator venom4u31Manea Constantin venom4u31 Data 12 martie 2012 19:27:48
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <iostream>
#include <fstream>

using namespace std;

int v[101], sol[7], n, cont=0, a[7], suma;

void interclass(int* v, int d, int d2, int* c)
{
    int *s1, *s2, i, j, ind, b=0, k;
    s1=v; s2=v+d;
    while(s1<v+d&&s2<v+d+d2)
    {
        if(*s1>*s2)
        {
            *(c+b)=*s2;
            b++;
            s2++;
        }
        else
        {
            *(c+b)=*s1;
            b++;
            s1++;
        }
    }
    if(s1<v+d)
        while(s1<v+d)
        {
            *(c+b)=*s1;
            b++;
            s1++;
        }
    else
        while(s2<v+d+d2)
        {
            *(c+b)=*s2;
            b++;
            s2++;
        }
    for(k=0;k<2*d;k++)
        *(v+k)=*(c+k);
}

/*
int solve(int k, int x, int s)
{
    int i;
    a[k]=x;
    for(i=1;i<=k;i++)
    cout<<a[i]<<' ';
    cout<<" --> "<<suma-s+a[k]<<endl;
    //if(k==1&&cont==1) return 1;
    if(k==6)
        {

            if(s==x)
            {
                sol[k]=x;
                cont=1;
                return 1;
            }
            else return 0;
        }
    else
    {
        for(i=1;i<=n;i++)
        {
            if(solve(k+1, v[i], s-x))
            {
                sol[k]=x;
                return 1;
            }
            else
            if(v[i]*(6-k)>s)
            return 0;
        }
        return 0;
    }
}
*/
int main()
{
    ifstream f("loto.in");
    ofstream g("loto.out");
    int i, j, sum, b[101];
    f>>n>>sum;
    suma=sum;

    v[0]=0;
    for(i=0;i<n;i++)
        f>>v[i];
    /*for(i=1;i<=n;i++)
        if(6*v[i]>sum) break;
    if(solve(1, v[i-1], sum))
    for(i=1;i<=6;i++)
        g<<sol[i]<<" ";
    else g<<-1<<" ";*/

        for(i=1;i<n;i=i*2)
        for(j=0;j<n;j=j+2*i)
        {
            if(j+2*i<n)
                interclass(v+j, i, i, b+j);//adresa de inceput, dimensiune standard, dimensiune modificata pentru jumatatea 2, noul vector semisortat
            else
                interclass(v+j, i, n-j-i, b+j);

        }



    j=0;
    a[6]=0;
    while(j<=5)
    {
        for(i=1;i<=n;i++)
            if((6-j)*v[i]>suma)
                {
                    j++;
                    a[j]=v[i-1];
                    suma-=v[i-1];
                    break;
                }
            else if((6-j)*v[i]==suma)
            {
                j++;
                a[j]=v[i];
                suma-=v[i];
                break;
            }
            if(i>n) break;
    }
    if(a[6]==0||a[1]==0||suma!=0)
    g<<-1;
    else for(i=1;i<=6;i++)
    g<<a[i]<<' ';
    return 0;
}