Cod sursa(job #2670258)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 9 noiembrie 2020 15:38:23
Problema Loto Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;
int n,s,ok,a[101],rasp[8];
void cautbin(int sum)
{
    int pos = -1, step = 1;
    while (step * 2 <= n) step *= 2;
    while (step > 0)
    {
        if(a[pos + step] +sum== s)
        {
            pos=pos+step;
            break;
        }
        if (pos + step < n && a[pos + step] +sum< s) pos += step;

        step /= 2;
    }
    if (pos != -1 && a[pos] +sum==s)
    {rasp[6]=a[pos];
    sort(rasp+1,rasp+7);
        for(int i=1; i<=6; i++)printf("%d ",rasp[i]);
        ok=1;
    }

}
void backtr(int k,int sum)
{
    if (ok) return;
    if(k==6)
    {
        cautbin(sum);
    }
    else
    {
        for(int i=1; i<=n; i++)
        {
            if(sum+a[i]<=s)
            {
                rasp[k]=a[i];
                backtr(k+1,sum+a[i]);
            }
        }
    }
    return;
}
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    backtr(1,0);
    if(ok==0)printf("-1");
    return 0;
}