Cod sursa(job #862466)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 22 ianuarie 2013 18:34:41
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int n,sum,a[101],p=0,s[1000001],el1[1000001],el2[1000001],el3[1000001],sol=0;
void Read()
{int i;
f>>n>>sum;
for(i=1;i<=n;i++) f>>a[i];
}
void Build()
{int i,j,k,sm; p=0;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
for(k=j;k<=n;k++)
{sm=a[i]+a[j]+a[k];
if (sm<sum) {p++;s[p]=sum-sm;el1[p]=a[i];el2[p]=a[j];el3[p]=a[k];}
}
}
void Sorting(int l,int r)
{int i=l,j=r,piv=s[(l+r)/2];
while (i<j)
{while (s[i]<piv) i++;
while (s[j]>piv) j--;
swap(s[i],s[j]);swap(el1[i],el1[j]);
swap(el2[i],el2[j]);swap(el3[i],el3[j]);
i++;j--;
}
if (i<r) Sorting(i,r);
if (j>l) Sorting(l,j);
}
void Search()
{int i,j,k,sm=0,x=0;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
for(k=j;k<=n;k++)
{sm=a[i]+a[j]+a[k];
x=upper_bound(s+1,s+p+1,sm)-s-1;
if (x>=1 && x<=p && s[x]==sm) {g<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<el1[x]<<" "<<el2[x]<<" "<<el3[x];sol=1;return;}
}

}
int main()
{Read();
Build();
Sorting(1,p);
Search();
if (!sol) g<<"-1";
return 0;
}