Cod sursa(job #1827269)

Utilizator AlleeexCristina.Gn Alleeex Data 11 decembrie 2016 18:05:26
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct suma
{
    suma(int tx, int ty, int tz)
    {
        x = tx;
        y = ty;
        z = tz;
        s = tx + ty + tz;
    }
    suma()
    {

    }
    int x, y, z;
    int s;
};

ifstream in("loto.in");
ofstream out("loto.out");
int n, s;
int v[105];
suma sum[105 * 105 * 105];

void citire()
{
    in >> n >> s;
    for(int i = 1; i <= n; ++i)
        in >> v[i];
}

bool comp(suma x, int val)
{
    if(x.s < val) return true;
    return false;
}

bool cmp(suma x, suma y)
{
    if(x.s < y.s)
        return true;
    return false;
}

int cautbin(int st, int dr, int rest)
{
    int mid;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(sum[mid].s == rest)
            return mid;
        else if(sum[mid].s > rest)
            dr = mid - 1;
        else
            st = mid + 1;
    }
    return -1;
}

void rezolvare()
{
    int pos = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = i; j <= n; ++j)
            for(int k = j; k <= n; ++k)
            {
                sum[pos] = suma(v[i], v[j], v[k]);
                pos++;

            }
    sort(sum, sum + pos, cmp);
    pair<int, int> rasp = make_pair(-1, -1);
    for(int i = 0; i < pos; ++i)
    {
        rasp.first = cautbin(0, pos - 1, s - sum[i].s);
        if(rasp.first!= -1)
        {
            rasp.second = i;
            break;
        }

    }
    if(rasp.first != -1)
    {
        out << sum[rasp.first].x << " " << sum[rasp.first].y << " " << sum[rasp.first].z << " " << sum[rasp.second].x << " " << sum[rasp.second].y << " " << sum[rasp.second].z;
    }
    else
        out << -1;
}

int main()
{
    citire();
    rezolvare();
    return 0;
}