Cod sursa(job #1592794)

Utilizator valentin50517Vozian Valentin valentin50517 Data 7 februarie 2016 22:44:43
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <climits>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");

int N,S,A[110],R[7],rs,maxi,mini;

int cautbin(int l, int r, int val){
	if(l >= r){
		if(val < A[r]) return 0;
		return r;
	}
	int mid = (l+r)/2;
	if(val > A[mid]) return cautbin(mid+1,r,val);
	return cautbin(l,mid,val);
}
int main(){
	fin >> N >> S;
	mini = INT_MAX;
	maxi = INT_MIN;
	for(int i = 1;i<=N;i++){
			fin >> A[i];
			if(maxi < A[i]) maxi = A[i];
			if(mini > A[i]) mini = A[i];
	}
	if((S/6 + bool(S%6) > maxi) || (mini*6 > S)){
			fout << -1;
			return 0;
	}
	
	int s,j,i = cautbin(1,N,S/6 + bool(S%6));
	
	while(i <= N && A[i] <= S-5){
		s = S;
		j = i;
		rs = 6;
		R[rs] = A[j];
		rs--;
		s-=A[j];
		while(j && rs){
			j = cautbin(1,j,s/rs);
			s -= A[j];
			R[rs--] = A[j];
			if(s == 0 && rs == 0){
					for(int l = 1;l<=6;l++) fout << R[l] << ' ';
					return 0;
			};
		}
		i++;
	}
	fout << -1;
	
	return 0;
}