Cod sursa(job #1514687)

Utilizator ancabdBadiu Anca ancabd Data 31 octombrie 2015 14:05:09
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int a[101],v[1000012];
int n, s, ab, x;

int cbin(int a, int st, int dr)
{
    int mij;
    while(st <= dr)
    {
        mij = (st + dr) /2;
        if(v[mij] == a) return mij;
        if(a < v[mij])dr = mij-1;
        else st = mij + 1;
    }
    return -1;
}
int main()
{
    fin >> n >> s;

    for(int i = 1; i <= n; i++) fin >> a[i];

    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j++)
            for(int z = j; z <= n; z++)
                v[ ++x ] = a[i] + a[j]+a[z];

    sort(v+1,v+x+1);

    for(int i =1; i<=x; i++)
        if(cbin(s - v[i] ,1 ,x)!= -1)
        {
            ab = v[i];
            i = x+1;
        }
    if(!ab) fout << -1;
    else
    {
        for(int i = 1; i <= n; i++)
            for(int j = i; j <=n; j++)
                for(int z = j; z <= n; z++)
                    if(ab == a[i] + a[j] + a[z])
                    {
                        fout << a[i] << ' ' << a[j] << ' ' << a[z] << ' ';
                        i = j = z = n + 1;
                    }
        for(int i= 1; i <=n; i++)
            for(int j =i; j <= n; j++)
                for(int z = j; z <= n; z++)
                    if(s - ab == a[i] + a[j] + a[z])
                    {
                        fout << a[i] << ' ' << a[j] << ' ' << a[z] << ' ';
                        i = j = z = n + 1;
                    }
    }
    return 0;
}