Cod sursa(job #473656)

Utilizator dicu_dariaDaria Dicu dicu_daria Data 30 iulie 2010 22:34:56
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <algorithm>
using namespace std;
typedef struct{
  int nr1,nr2,suma;
}element;
bool cmp(element a,element b)
{
  return(a.suma<b.suma);
}
element r[1000000];
int a[101],n,okk,m;
int binary(int val)
{
  int i,step;
  for(step=1;step<m;step<<=1);
  for(i=0;step;step>>=1)
  if ((r[i+step].suma<=val)&&(i+step<=m)) i+=step;
  if(r[i].suma==val)
  return i; else return 0;
}
int main()
{
    int i,s,j,k,x;
    ifstream fi("loto.in");
    ofstream fo("loto.out");
    fi>>n>>s;
    for(i=1;i<=n;i++) fi>>a[i];
    for(i=1;i<=n;i++)
      for(j=i;j<=n;j++)
        for(k=j;k<=n;k++)
        {
          r[++m].suma=a[i]+a[j]+a[k];
          r[m].nr1=a[i];
          r[m].nr2=a[j];
        }
    sort(r+1,r+m+1,cmp);
    okk=0;
    for(i=1;i<=n and okk==0;i++)
      for(j=i;j<=n and okk==0;j++)
        for(k=j;k<=n;k++)
        {
          x=binary(s-a[i]-a[j]-a[k]);
          if(x) {
                    okk=1;
                    fo<<r[x].nr1<<" "<<r[x].nr2<<" "<<r[x].suma-r[x].nr1-r[x].nr2<<" "<<a[i]<<" "<<a[j]<<" "<<a[k]<<"\n";
                    break;
                  }
        }
    if(okk==0) fo<<"-1\n";
    return 0;
}