Cod sursa(job #179449)

Utilizator lamez0rBogdan Bondor lamez0r Data 15 aprilie 2008 22:18:08
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>

#define Nmax 200000
#define N 101
using namespace std;

ofstream fout("loto.out");

struct suma {
	     int s, x, y, z;
	     } S[200000],aux;


void schimba(int p, int q)
       {
	aux=S[p];
	S[p]=S[q];
	S[q]=aux;
       }


int pivot(int p, int q)
	{
	while(p<q)
	    {
	    while(S[p].s<=S[q].s && p!=q)
		 p++;
	    if(p<q) schimba(p,q);
	    while(S[p].s<=S[q].s && p!=q)
		 q--;
	    if(p<q)  schimba(p, q);
	    }
	return p;
	}

void qsort(int p, int q)
	{
	if(q>p)
		{
		int k=pivot(p, q);
		qsort(p, k-1);
		qsort(k+1, q);
		}
	}

int main(void)
     {
      int v[N], n, s;
      ifstream fin("loto.in");
      fin>>n>>s;
      int i, val, a, b, c;
      for(i=1;i<=n;++i)
	 fin>>v[i];
      fin.close();
      int j, k, t=0;
      for(i=1; i<= n;++i)
	   for(j=i; j<=n; j++)
	       for(k=j; k<=n; k++)
		  {
		    S[++t].s=v[i]+v[j]+v[k];
		    S[t].x=v[i];
		    S[t].y=v[j];
		    S[t].z=v[k];
		  }
      qsort(1, t);
      for(i=1;i<=t;i++)
	  {
	   val=s-S[i].s;
	   a=i; b=t;
	   while(a<=b)
	      {
	      c=(a+b)/2;
	      if(S[c].s==val)
		{
		fout<<S[i].x<<" "<<S[i].y<<" "<<S[i].z<<" "<<S[c].x<<" "<<S[c].y<<" "<<S[c].z<<'\n';
		fout.close();
		return 0;
		}
	      else
		if(S[c].s>val)
			b=c-1;
		else
			a=c+1;
	      }
	  }
      fout<<"-1\n";
      fout.close();
      return 0;
     }