Cod sursa(job #1510404)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 24 octombrie 2015 22:16:53
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("loto.in");
ofstream out("loto.out");

int n;
int s;
int *p;
int ok = 1;

void quicksort(int x,int y,int *&p)
{
    if(x<y)
    {
        int i=x,j=y,pivot = p[i];
        while(i<j)
        {
            if(p[i]>p[j])
            {
                int h = p[i];
                p[i] = p[j];
                p[j] = h;
            }
            if(p[i]==pivot)
                j--;
            else
                i++;
        }
        int m = i;
        quicksort(x,m-1,p);
        quicksort(m+1,y,p);
    }
}

int binary(int x,int y,int *p,int val)
{
    if(x<=y)
    {
        int m = (x+y)/2;
        if(p[m] == val)
            return m;
        else
        {
            if(p[m]>val)
                return binary(x,m-1,p,val);
            else
                return binary(m+1,y,p,val);
        }
    }
    return -1;
}

int main()
{
    in>>n>>s;
    p = new int[n+1];
    for(int i=1;i<=n;i++)
        in>>p[i];
    quicksort(1,n,p);
   //
   int sum = 0;
    for(int i = n;i>=1;i--)
    {
         sum=p[i];
        if(sum<s)
        {
    for(int j = n;j>=1;j--)
    {
         sum+=p[j];
        if(sum<s)
        {
    for(int k = n;k>=1;k--)
    {
         sum+=p[k];
        if(sum<s)
        {
    for(int l = n;l>=1;l--)
    {
         sum+=p[l];
        if(sum<s)
        {
    for(int m = n;m>=1;m--)
    {
        sum+= p[m];
        if(sum<s)
        {
        int z = binary(1,n,p,s-sum);
        if(z!=-1)
        {
            out<<p[i]<<" "<<p[j]<<" "<<p[k]<<" "<<p[l]<<" "<<p[m]<<" "<<p[z]<<'\n';
            ok = 0;
        }
        }
        else
            sum -=p[m];
    if(!ok)
        break;
    }
    }
        else
            sum -=p[l];
    if(!ok)
        break;
    }
    }
        else
            sum -=p[k];
    if(!ok)
        break;
    }
    }
        else
            sum -=p[j];
    if(!ok)
        break;
    }
        }
        else
            sum = 0;
    if(!ok)
        break;
    }
    if(ok)
        out<<-1<<'\n';
   //
    in.close();
    out.close();
    delete[] p;
    return 0;
}