Cod sursa(job #744289)

Utilizator harababurelPuscas Sergiu harababurel Data 8 mai 2012 11:33:27
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	ifstream f("loto.in");
	ofstream g("loto.out");
	int n, s, i, j, k, l, begin, end, mid;
	vector <int> v;
	
	//toate combinatiile de 6 numere de la 1 la N
	
	
	f>>n>>s;
	
	//am a,b,c,d,e,f numere
	//fac vector predefinit pentru a,b,c
	//3 foruri pentru d,e,f
	//si cautare binara in vectorul de valori
	
	for(i=1; i<=n; i++) {
		for(j=i; j<=n; j++) {
			for(k=j; k<=n; k++) {
				v.push_back(i+j+k);
			}
		}
	}
	
	sort(v.begin(), v.end());	//ca sa pot cauta binar
	
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++) {
			for(k=1; k<=n; k++) {
				
				begin = 0;
				end = v.size();
				while(end-begin > 1) {
					mid = begin+(end-begin)/2;
					if(v[mid]+i+j+k > s) end = mid;
					else begin = mid;
				}
				
				if(v[mid]+i+j+k == s) end=mid;
				if(v[begin]+i+j+k==s) end=begin;
				
				 if(v[end] + i + j + k == s) {	//am gasit o solutie buna
						g<<v[end]/3<<" "<<v[end]/3<<" "<<v[end] - 2*(v[end]/3)<<" "<<i<<" "<<j<<" "<<k<<"\n";
						i=n+1; j=n+1; k=n+1;
						break;
				 }
				
			}
		}
	}
	
	if(i==n+1) { g<<"-1\n"; }
	
	
	f.close();
	g.close();
	return 0;
}