Pagini recente » Cod sursa (job #279145) | Monitorul de evaluare | Cod sursa (job #971383) | Cod sursa (job #359690) | Cod sursa (job #854775)
Cod sursa(job #854775)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
unsigned int n,numere[100];
long long s;
struct set
{
long long suma;
unsigned int primul_numar,doilea_numar;
};
vector <set> sume;
inline void citire()
{
ifstream f("loto.in");
f>>n>>s;
for(unsigned int i=0;i<n;++i)
f>>numere[i];
f.close();
}
void qsort(int start,int sfarsit)
{
int i=start,j=sfarsit,pivot=(sfarsit-start)/2;
if(start>=sfarsit || sfarsit-start==1)
return;
while(i<=j)
{
if(numere[i]<numere[pivot])
{++i;continue;}
while(j>pivot && numere[j]>numere[pivot])
{--j;continue;}
swap(numere[i],numere[j]);
++i;--j;
}
qsort(start,j);
qsort(i,sfarsit);
}
inline void cautare()
{
int start=0,sfarsit=sume.size()-1,cauta;
while(start<=sfarsit)
{
cout<<start<<" "<<sfarsit<<endl;
if(sume[start].suma + sume[sfarsit].suma == s)
{
ofstream g("loto.out");
g<<sume[start].primul_numar<<" "<<sume[start].doilea_numar<<" "<<sume[start].suma-sume[start].primul_numar-sume[start].doilea_numar<<" "<<sume[sfarsit].primul_numar<<" "<<sume[sfarsit].doilea_numar<<" "<<sume[sfarsit].suma-sume[sfarsit].primul_numar-sume[sfarsit].doilea_numar;
g.close();
return;
}
if(sfarsit == 0)
break;
if(sume[start].suma + sume[sfarsit].suma < s)
{
cauta = start<<1;
if(sume[cauta].suma + sume[cauta].suma <= s && start!=0)
start = cauta;
else
++start;
continue;
}
cauta = sfarsit>>1;
if(sume[start].suma + sume[cauta].suma >= s)
sfarsit = cauta;
else
--sfarsit;
}
ofstream g("loto.out");
g<<"-1";
g.close();
}
int main()
{
citire();
qsort(0,n-1);
set inserare;
unsigned int i,j,k;
for(i=0;i<n;++i)
for(j=i;j<n;++j)
for(k=j;k<n;++k)
{
inserare.primul_numar=numere[i];
inserare.doilea_numar=numere[j];
inserare.suma=numere[i]+numere[j]+numere[k];
sume.push_back(inserare);
}
cautare();
return 0;
}