Cod sursa(job #1740074)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 10 august 2016 19:40:57
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<bits/stdc++.h>
#define INF 1000005
#define maxN 105
using namespace std;
typedef struct tip
{
  int suma;
  int x1;
  int x2;
  int x3;
};
tip v[INF];
bool f(tip a,tip b)
{
    if (a.suma<b.suma) return 1;
    return 0;
}
int a[maxN],b[15];
int n,s,ls,ld,mid,sol;
int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    scanf("%d%d",&n,&s);
    //v=new tip[n*n*n+5];
   // a=new int[n+5];
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
   // sort(a+1,a+n+1);
    int dv=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            for(int k=j;k<=n;k++)
            {
                dv++;
                v[dv].suma=a[i]+a[j]+a[k];
                v[dv].x1=i;
                v[dv].x2=j;
                v[dv].x3=k;
            }
        }
    }
    sort(v+1,v+dv+1,f);
    for(int i=1;i<=dv;i++)
    {
       if (v[i].suma<=s)
       {

        int x=s-v[i].suma;
        ls=1;
        ld=dv;
        mid=0;
        sol=0;
        while (ls<=ld)
        {
            mid=ls+(ld-ls)/2;
            if (v[mid].suma==x)
            {
                sol=mid;
                ls=ld+1;
            }
                else
            if (v[mid].suma<x) ls=mid+1;
                else ld=mid-1;

        }
        if (sol)
        {
            b[1]=v[i].x1;
            b[2]=v[i].x2;
            b[3]=v[i].x3;
            b[4]=v[sol].x1;
            b[5]=v[sol].x2;
            b[6]=v[sol].x3;
            sort(b+1,b+7);
           for(int k=1;k<=6;k++) printf("%d ",a[b[k]]);
            printf("\n");
           // printf("%d %d %d %d %d %d\n",a[v[i].x1],a[v[i].x2],a[v[i].x3],a[v[sol].x1],a[v[sol].x2],a[v[sol].x3]);
     //       ok=1;
       //     break;
            return 0;
        }
       }
    }
    printf("-1\n");
  //  sort(v+1,v+dv+1,f);
    return 0;
}