Cod sursa(job #878347)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 14 februarie 2013 13:07:12
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <algorithm>

using namespace std;

//In acest vector vom pune toate sumele care pot fi obtinute folosind doar 3 numere
int sume[1000005];

int main()
{
	//Deschiderea fisierelor de intrare si iesire
	ifstream fin("loto.in");
	ofstream fout("loto.out");
	
	//n-ul si s-ul din enunt, i,j - contoare si v - vectorul ce va contine cele n numere citite
	int n,s,i,j,k,v[101];
	
	//Se citesc n si s
	fin>>n;
	fin>>s;
	
	//Se citesc cele n numere
	for(i=0;i<n;i++)
		fin>>v[i];
	
	//Lungimea vectorului cu sume
	int poz=0; 
	
	//Se pun toate sumele ce pot fi obtinute in vectorul cu sume
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
			for(k=j;k<n;k++)
				sume[poz++]=v[i]+v[j]+v[k];
	
	//Se sorteaza crescator vectorul cu sume
	sort(sume,sume+poz);
	
	//Numarul pe care il va cauta cautarea binara
	int cautat;
	
	//Variabilele caracteristice cautarii binare
	int cap,coada,mijl;
	
	//Variabila retine true numai daca s-a gasit o solutie
	bool gasit=false;
	
	//Solutia gasita va fi retinuta in aceste variabile
	int x1=0,x2=0,x3=0,x4=0,x5=0,x6=0;
	
	//Cautam binar solutia, penru oricare trei numere x1, x2 si x3, in complexitate O(n^3*logn)
	for(i=0;i<n && !gasit;i++)
		for(j=i;j<n && !gasit;j++)
			for(k=j;k<n && !gasit;k++)
			{
				//Initializam numarul care va fi cautat
				cautat=s-(v[i]+v[j]+v[k]);
				
				//Initializam cautarea binara
				cap=0;
				coada=poz-1;
				mijl=(poz-1)/2;
				
				//Cautarea binara propriu-zisa
				while(cap<=coada)
				{
					//Daca am gasit o solutie
					if(sume[mijl]==cautat)
					{
						gasit=true;
						
						x1=v[i];
						x2=v[j];
						x3=v[k];
						
						//Am terminat cautarea
						break;
					}
					else if(sume[mijl]<cautat)
					{	
						cap=mijl+1;
					}
					else
					{
						coada=mijl-1;
					}
					
					//Updatam mijlocul
					mijl=(cap+coada)/2;
				}
				
			}
	
	//Daca nu a fost gasita nicio solutie
	if(!gasit)
	{
		fout<<"-1\n";
	}
	else //Daca a fost gasita o solutie
	{
		fout<<x1<<' '<<x2<<' '<<x3<<' '; //Afisam primele trei componente al solutiei 
		
		cautat=s-(x1+x2+x3);
		
		//Le cautam in O(n^3) pe celelalte trei
		gasit=false;
		
		for(i=0;i<n && !gasit;i++)
			for(j=i;j<n && !gasit;j++)
				for(k=j;k<n && !gasit;k++)
				{
					if((v[i]+v[j]+v[k])==cautat)
					{
						x4=v[i];
						x5=v[j];
						x6=v[k];
						gasit=true;
						break;
					}
				}
			
		//Afisam cealalta jumatate a solutiei gasite
		fout<<x4<<' '<<x5<<' '<<x6<<'\n';
	}
	
	//Inchiderea fisierelor de intrare si iesire
	fin.close();
	fout.close();
	return 0;
}