Pagini recente » Cod sursa (job #1009940) | Cod sursa (job #1293868) | Profil Dobricean_Ioan | Cod sursa (job #1529944) | Cod sursa (job #2014114)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
class Element{
public:
int a;
int b;
int c;
int s;
Element() {};
};
// ordering function
bool elemComp (Element x,Element y) {return (x.s<y.s);}
// binary search
int bin_search(int val, int left0, int right0);
int get_idx_max(int x, int left0, int right0);
//globals
Element* vsum;
int n;
int main(void) {
int s = 0, sp;
int nmax;
int nsum;
int numbers[101];
int i,j,k;
int min = 0;
int max = 600000001;
fstream infile("loto.in", ios::in);
fstream outfile("loto.out", ios::out);
// read n, s
infile>>n>>s;
// read numbers
for(i=0;i<n; ++i) {
infile>>numbers[i];
if (numbers[i]<min)
min = numbers[i];
else if (numbers[i]>max)
max = numbers[i];
}
vsum = new Element[n*n*n];
// compute sums
nsum = 0;
for(i=0;i<n;++i)
for(j=0;j<n;++j)
for(k=0;k<n;++k) {
sp = numbers[i]+numbers[j]+numbers[k];
if ((sp+3*max>=s) && (sp+3*min<=s)) {
vsum[nsum].a = numbers[i];vsum[nsum].b = numbers[j];vsum[nsum].c = numbers[k];
vsum[nsum].s = sp;
nsum++;
}
}
// sort
sort(vsum, vsum+nsum, elemComp);
nmax = get_idx_max(s/2+1,0,nsum);
for(i=0;i<nmax+1;++i) {
if((i>0) && (vsum[i-1].s==vsum[i].s))
continue;
j = bin_search(s-vsum[i].s, i, nsum);
if (j!=-1) {
outfile<<int(vsum[i].a)<<" "<<int(vsum[i].b)<<" "<<int(vsum[i].c)<<" "
<<int(vsum[j].a)<<" "<<int(vsum[j].b)<<" "<<int(vsum[j].c);
infile.close();
outfile.close();
return 0;
}
}
// not found
outfile<<"-1";
infile.close();
outfile.close();
return 0;
}
int bin_search(int x, int left0, int right0) {
int left = left0;
int right = right0-1;
int middle;
while(left <= right) {
middle = (left+right)/2;
if (vsum[middle].s==x)
return middle;
else if (x<vsum[middle].s)
right = middle-1;
else
left = middle+1;
}
return -1;
}
int get_idx_max(int x, int left0, int right0) {
int left = left0;
int right = right0-1;
int middle = left0;
while(left <= right) {
middle = (left+right)/2;
if (vsum[middle].s==x)
return middle;
else if (x<vsum[middle].s)
right = middle-1;
else
left = middle+1;
}
return middle+1;
}