Cod sursa(job #1510424)

Utilizator SlevySlevoaca Stefan-Gabriel Slevy Data 24 octombrie 2015 22:48:34
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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;

struct sums{
int x,y,z,sum;
};
vector<sums> su;
sums aux;

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];
    su.push_back(aux);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
            {
                aux.x = p[i];
                aux.y = p[j];
                aux.z = p[k];
                aux.sum = p[i] + p[j] + p[k];
                su.push_back(aux);
            }
    sort(su.begin()+1,su.end(),compare);
    int s2;
    int poz1 = 0;
    int poz2 = 0;
    for(unsigned int i=1;i<su.size();i++)
      {
          s2 = s-su[i].sum;
          poz1 = i;
          poz2 = binary(1,su.size(),s2);
          if(poz2!=-1)
            break;
      }
    out<<su[poz1].x<<" "<<su[poz1].y<<" "<<su[poz1].z<<" "<<su[poz2].x<<" "<<su[poz2].y<<" "<<su[poz2].z<<'\n';
    //
    in.close();
    out.close();
    delete[] p;
    return 0;
}