Cod sursa(job #732156)

Utilizator gramatovici_paulGramatovici Paul gramatovici_paul Data 9 aprilie 2012 19:52:36
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n,a[111],b[1111111],s;

bool exista(int x)
{
    int i,pas=1<<19;
    for(i=0;pas;pas>>=1)
    {
        if(i+pas<=n && b[i+pas]<=x)
            i+=pas;
    }
    if(b[i]==x)
        return true;
    return false;
}


void termina(int x,int y)
{
    int i,j,ii;
    bool gasit;
    gasit=false;
    for(i=1;i<=n;++i)
    {
        for(j=i;j<=n;++j)
        {
            for(ii=j;ii<=n;++ii)
            {
                if(x==a[i]+a[j]+a[ii])
                {
                    out<<a[i]<<" "<<a[j]<<" "<<a[ii]<<" ";

                    gasit=true;
                    break;
                }
            }
            if(gasit)
                break;
        }
        if(gasit)
            break;
    }
    gasit=false;
    for(i=1;i<=n;++i)
    {
        for(j=i;j<=n;++j)
        {
            for(ii=j;ii<=n;++ii)
            {
                if(y==a[i]+a[j]+a[ii])
                {
                    out<<a[i]<<" "<<a[j]<<" "<<a[ii]<<" ";
                    return;
                }
            }
        }
    }
    return;
}

int main()
{
    int i,j,ii,nr=0;
    in>>n>>s;
    for(i=1;i<=n;++i)
        in>>a[i];
    for(i=1;i<=n;++i)
        for(j=i;j<=n;++j)
            for(ii=j;ii<=n;++ii)
            {
                b[++nr]=a[i]+a[j]+a[ii];
            }
    sort(b+1,b+nr+1);
    for(i=1;i<=nr;++i)
    {
        if(exista(s-b[i]))
        {
            termina(b[i],s-b[i]);
            return 0;
        }
    }
    return 0;
}