Cod sursa(job #1510431)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 24 octombrie 2015 22:57:28
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int s;
int *p;
int ok = 1;
int v[7];

struct sums{
int x,y,z,sum;
};
sums su[1000003];
sums aux;
int nr = 0;

bool compare(sums A,sums B)
{
    if(A.sum>B.sum)
        return true;
    return false;
}

int binary(int x,int y,int val)
{
    if(x<=y)
    {
        int m = (x+y)/2;
        if(su[m].sum == val)
            return m;
        else
        {
            if(su[m].sum>val)
                return binary(x,m-1,val);
            else
                return binary(m+1,y,val);
        }
    }
    return -1;
}

int main()
{
    in>>n>>s;
    p = new int[n+1];
    for(int i=1;i<=n;i++)
        in>>p[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
            {
                ++nr;
                su[nr].x = p[i];
                su[nr].y = p[j];
                su[nr].z = p[k];
                su[nr].sum = p[i] + p[j] + p[k];
            }
    sort(su+1,su+nr,compare);
    int s2;
    int poz1 = 0;
    int poz2 = 0;
    int ok = 0;
    for(int i=1;i<=nr;i++)
      {
          s2 = s-su[i].sum;
          poz1 = i;
          poz2 = binary(1,nr,s2);
          if(poz2!=-1)
           {
               ok = 1;
               break;
           }
      }
    if(!ok)
        out<<-1<<'\n';
    else
    {
        v[1] = su[poz1].x;
        v[2] = su[poz1].y;
        v[3] = su[poz1].z;
        v[4] = su[poz2].x;
        v[5] = su[poz2].y;
        v[6] = su[poz2].z;
        sort(v+1,v+6);
        for(int i=1;i<=6;i++)
            out<<v[i]<<" ";
        out<<'\n';
    }
    in.close();
    out.close();
    delete[] p;
    return 0;
}