Cod sursa(job #857755)

Utilizator mvcl3Marian Iacob mvcl3 Data 18 ianuarie 2013 12:35:24
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
//Solutie 1
#include<fstream>
#include<algorithm>
using namespace std;

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

const int NMAX = 1000009;
int n, s, nr, c[NMAX];

struct nod
{
    int s;
    int x;
    int y;
    int z;
} v[NMAX];

inline bool cmp(const nod &a, const nod &b)
{
    if(a.s > b.s) return 1;

    return 0;
}

int main()
{
    f>>n>>s;
    for(int i = 1; i <= n; ++i) f>>c[i];

    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            for(int k = j; k <= n; ++k)
                if(c[i] + c[j] + c[k] <= s)
                {
                    v[++nr].s = c[i] + c[j] + c[k];
                    v[nr].x = c[i], v[nr].y = c[j], v[nr].z = c[k];
                }
    sort(v + 1, v + nr + 1, cmp);

    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            for(int k = j; k <= n; ++k)
            {
                int s1 = s - c[i] - c[j] - c[k];
                int st = 1, dr = nr, mij;
                while(st <= dr)
                {
                    mij = (st + dr) >> 1;
                    if(v[mij].s == s1)
                    {
                        g<<c[i]<<' '<<c[j]<<' '<<c[k]<<' '<<v[mij].x<<' '<<v[mij].y<<' '<<v[mij].z<<'\n';
                        g.close();
                        return 0;
                    }
                    if(s1 > v[mij].s) dr = mij - 1; else st = mij + 1;
                }
            }
    g<<-1<<'\n';
    g.close();
    return 0;
}