Pagini recente » Cod sursa (job #134134) | Cod sursa (job #1160747) | Cod sursa (job #1992699) | Cod sursa (job #1712241) | Cod sursa (job #338121)
Cod sursa(job #338121)
#include <fstream>
#define Max 101
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
int n,s,l,v[Max],sum[600000];
void citire ()
{
f>>n>>s;
for (int i=1; i<=n; i++)
f>>v[i];
f.close ();
}
void partial_sums () //fac toate sumele posibile fara sa repet vreo suma (din cauza asta am scris
{ //j=i,k=j) cu numerele date de "loterie"
for (int i=1; i<=n; i++)
for (int j=i; j<=n; j++)
for (int k=j; k<=n; k++)
sum[++l]=v[i]+v[j]+v[k];
}
void quicksort (int v[],int stanga, int dreapta)
{
int i=stanga,j=dreapta;
int pivot=v[(stanga+dreapta)>>1];
while (v[i]<pivot) i++;
while (v[j]>pivot) j--;
if (i<j)
{
v[i]^=v[j]^=v[i]^=v[j];
i++;
j--;
}
else if (i==j) i++,j--; //cand i=j rezulta ca &v[i]==&v[j] deci swap cu XOR nu merge
if (stanga<j) quicksort (v,stanga,j);
if (dreapta>i) quicksort (v,i,dreapta);
}
int bin_search (int x,int i,int j)
{
int mid;
while (i<=j)
{
mid=i+((j-i)>>1); //((j-i)>>1) >> are prioritate mare si daca lasam fara paranteze considera ca
if (x<sum[mid]) j=mid-1; //expresie (i+(j-i))>>1
else if (x>sum[mid]) i=mid+1;
else return 1;
}
return 0;
}
void write_s2( int aux)
{
for (int p=1; p<=n; p++)
for (int q=p; q<=n; q++)
for (int r=q; r<=n; r++)
if (aux==v[p]+v[q]+v[r])
g<<v[p]<<" "<<v[q]<<" "<<v[r];
}
bool write_numbers () //caut 2 sume care satisfac conditia s1+s2=s;
{
for (int i=1; i<=n; i++)
for (int j=i; j<=n; j++)
for (int k=j; k<=n; k++)
if (bin_search (s-v[i]-v[j]-v[k],1,l)) //caut prima suma (si implicit numerele ce compun suma)
{
g<<v[i]<<" "<<v[j]<<" "<<v[k]<<" ";
writes2(s-v[i]-v[j]-v[k]); //cauta a doua suma (si implicit numerele ce compun suma)
return 1;
}
return 0;
}
int main ()
{
citire ();
partial_sums ();
quicksort (sum,1,l);
if (!write_numbers ())
g<<-1;
g.close ();
return 0;
}