Cod sursa(job #1335051)

Utilizator cautionPopescu Teodor caution Data 4 februarie 2015 21:36:23
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <algorithm>
using namespace std;
struct sum_of_3
{
    long sum, a, b, c;
};
bool comp(sum_of_3 s1, sum_of_3 s2)
{
    return s1.sum<s2.sum;
}
long n, s, v[100], n_sums=0, l_bound, u_bound, solved=0;
sum_of_3 sums[1000000];
int main()
{
    ifstream in("loto.in");
    ofstream out("loto.out");
    in>>n>>s;
    for(long i=0; i<n; ++i)
        in>>v[i];
    for(long i=0; i<n; ++i)
        for(long j=i; j<n; ++j)
            for(long k=j; k<n; ++k)
            {
                sums[n_sums].sum=v[i]+v[j]+v[k];
                sums[n_sums].a=v[i];
                sums[n_sums].b=v[j];
                sums[n_sums].c=v[k];
                ++n_sums;
            }
    sort(sums, sums+n_sums, comp);
    l_bound=0;
    u_bound=n_sums-1;
    while(l_bound<=u_bound)
    {
        if(sums[l_bound].sum+sums[u_bound].sum<s)
            ++l_bound;
        else if(sums[l_bound].sum+sums[u_bound].sum>s)
            --u_bound;
        else
        {
            solved=1;
            out<<sums[l_bound].a<<' '<<sums[l_bound].b<<' '<<sums[l_bound].c<<' '
                <<sums[u_bound].a<<' '<<sums[u_bound].b<<' '<<sums[u_bound].c;
            break;
        }
    }
    if(!solved) out<<"-1";
    in.close(); out.close();
    return 0;
}