Cod sursa(job #14062)

Utilizator floringh06Florin Ghesu floringh06 Data 8 februarie 2007 09:41:40
Problema Loto Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
using namespace std;
#include<stdio.h>

int a[105];

void sort(int li,int lf)
{
if(li<lf)
 {
 int m=(li+lf)/2;
 sort(li,m);
 sort(m+1,lf);
 //interclasare
 int k,q,nr=0;
 int b[105];
 k=li,q=m+1;
 while(k<=m&&q<=lf)
   if(a[k]>=a[q])
      b[++nr]=a[k++];
   else b[++nr]=a[q++];
 while(k<=m) b[++nr]=a[k++];
 while(q<=lf) b[++nr]=a[q++];
 for(k=li;k<=lf;k++) a[k]=b[k-li+1];
 }
}

int main()
{
FILE *f,*g;
f=fopen("loto.in","r");
int s;
int n,i;

fscanf (f,"%d %d",&n,&s);
g=fopen("loto.out","w");

for(i=1;i<=n;i++)
  fscanf(f,"%d",&a[i]);
  
fclose(f);
//sortare descrescatoare
sort(1,n);

//cautare
int j,k,q,p,m,sc=0;

for(i=1;i<=n;i++)
  {
  sc+=a[i];
  if(sc<s)
  for(j=i;j<=n;j++)
    {
    sc+=a[j];
    if(sc<s)
      for(k=j;k<=n;k++)
         {
         sc+=a[k];
         if(sc<s)
            for(q=k;q<=n;q++)
              {
              sc+=a[q];
              if(sc<s)
                 for(p=q;p<=n;p++)
                    {
                    sc+=a[p];
                    if(sc<s&&s-sc>=a[n]&&s-sc<=a[1])
                      {
                      //cautarea binara
                        int left=p,right=n;
                        int m=(left+right)/2;
                        int suma=s-sc;
                        while(a[m]!=suma&&left<=right)
                          {
                          if(suma<a[m])
                             //merg in dreapta
                             left=m+1;
                          else right=m-1;
                          m=(left+right)/2;
                          }
                        if(a[m]==suma)
                          {
                          fprintf(g,"%d %d %d %d %d %d",a[i],a[j],a[k],a[q],a[p],a[m]);
                          fclose(g);
                          return 0;
                          }
                      }
                    sc-=a[p];
                    }
              sc-=a[q];
              }
         sc-=a[k];
         }
    sc-=a[j];
    }
  sc-=a[i];
  }
fprintf(g,"%d",-1);

fclose(g);
return 0;
}