Cod sursa(job #1510398)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 24 octombrie 2015 22:07:46
Problema Loto Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 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--)
    {
    for(int j = n;j>=1;j--)
    {
    for(int k = n;k>=1;k--)
    {
    for(int l = n;l>=1;l--)
    {
    for(int m = n;m>=1;m--)
    {
        sum = p[i] + p[j] + p[k] + p[l] + 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;
        }
        }
    if(!ok)
        break;
    }
    if(!ok)
        break;
    }
    if(!ok)
        break;
    }
    if(!ok)
        break;
    }
    if(!ok)
        break;
    }
    if(ok)
        out<<-1<<'\n';
   //
    in.close();
    out.close();
    delete[] p;
    return 0;
}