Pagini recente » Cod sursa (job #2769484) | Cod sursa (job #2865711) | Cod sursa (job #2408061) | Cod sursa (job #112588) | Cod sursa (job #878347)
Cod sursa(job #878347)
#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;
}