Cod sursa(job #1412312)

Utilizator ilinoiuflaviusIlinoiu Flavius ilinoiuflavius Data 1 aprilie 2015 11:20:41
Problema Loto Scor 45
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>;
#define nmax 101
using namespace std;

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

struct sume
{
    int sum;
    int x,y,z;
} sum[nmax*nmax*nmax];

int v[nmax];
int n,s,nr,jj;

void read()   /// OK
{
    f>>n>>s;
    for(int i=1;i<=n;++i)f>>v[i];
}
bool comp(sume a, sume b)  /// OK
{
    if(a.sum < b.sum)return true;
    return false;
}
int bs(int _s)
{
    int st=1, dr=nr, mij;

    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(sum[mij].sum == _s)
        {
            jj = mij;
            return sum[mij].sum;
        }
        else if(sum[mij].sum < _s){st = mij+1;}
        else {dr = mij-1;}
    }
    return 0;
}
void solve()
{
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    for(int k=1;k<=n;++k)
        if(v[i]+v[j]+v[k] < s)
            {
                if((v[i]+v[j]+v[k])<<1 == s)
                {
                    g<<v[i]<<" "<<v[i]<<" "
                     <<v[j]<<" "<<v[j]<<" "
                     <<v[k]<<" "<<v[k]<<" ";
                    return;
                }
                sum[++nr].sum = v[i]+v[j]+v[k];
                sum[nr].x=i;
                sum[nr].y=j;
                sum[nr].z=k;
            }
    sort(sum+1,sum+nr+1,comp);
    //for(int i=1;i<=nr;i++)cout<<sum[i].sum<<" ";
    for(int i=nr;i>=1;i--)
    {
        if( sum[i].sum + bs(s-sum[i].sum) == s)
        {
            g<<v[sum[i].x]<<" "<<v[sum[i].y]<<" "<<v[sum[i].z]<<" "
                <<v[sum[jj].x]<<" "<<v[sum[jj].y]<<" "<<v[sum[jj].z];
            return;
        }
    }
}
int main()
{
    read();
    solve();
    if(jj)return 0;
    g<<-1;
    return 0;
}