Cod sursa(job #2746843)

Utilizator cosmin1812Nedelcu Adrian Cosmin cosmin1812 Data 28 aprilie 2021 16:38:08
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("loto.in");
ofstream out("loto.out");

int i, j, k, n, s, a[200], suma[200000], r, suma_part, verif;

int cautare_elem(int x, int r, int suma[])
{
    int st = 1, dr = r, mij;
    while(st != dr)
    {
        mij = (st + dr) / 2;
        if(x > suma[mij])
            st = mij + 1;
        else
            dr  = mij;
    }
    if(x == suma[st])
        return 1;
    return 0;
}

void dif(int x, int n, int a[])
{
    int i,j,k;
    for(i = 1; i<=n ;i++)
        for(j = i;j<=n;j++)
            for(k=j;k<=n;k++)
                if(a[i] + a[j] + a[k] == x)
                out<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
}



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

    for(i = 1; i<=n ;i++)
        for(j = i;j<=n;j++)
            for(k=j;k<=n;k++)
                suma[++r] = a[i] + a[j] + a[k];

    sort(suma +1, suma +r + 1);
    for(i = 1; i<=n ;i++)
    {
        if(verif == 1)
            break;

        for(j = i;j<=n;j++)
        {
            if(verif == 1)
                break;

            for(k=j;k<=n;k++)
            {
                suma_part = a[i] + a[j] + a[k];
                if(cautare_elem(s - suma_part,r,suma))
                {
                    out<<a[i]<<" "<<a[j]<<" "<<a[k]<<" ";
                    dif(s - suma_part, n,a);
                    verif = 1;
                    break;
                }
            }
        }
    }
    if(verif == 0)
        out<<"-1";

    return 0;
}