Cod sursa(job #335115)

Utilizator mlazariLazari Mihai mlazari Data 28 iulie 2009 18:33:27
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include<stdio.h>

#define NMAX 100

int n,s,i,j,k,l=1,posibil,N,s1,s2,g1,g2,left,right,mid,loto[NMAX],*s3,*ps3,answer[6];

int main() {
  // Deschide fisierele
  freopen("loto.in","r",stdin);
  freopen("loto.out","w",stdout);

  // Citeste datele de intrare
  scanf("%d %d",&n,&s);
  for(i=0;i<n;i++) scanf("%d",loto+i);

  // Calculeaza toate sumele posibile de 3 numere
  s3=new int[NMAX*NMAX*NMAX+1];
  ps3=s3;
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    for(k=0;k<n;k++) {
      ps3++;
      *ps3=loto[i]+loto[j]+loto[k];
    }

  // Sorteaza crescator sumele obtinute cu HeapSort
  N=n*n*n;
  for(i=1;i<=N;i++) {
    j=i;
    while((j>1)&&(s3[j>>1]<s3[j])) {
      k=s3[j];
      s3[j]=s3[j>>1];
      s3[j>>1]=k;
      j=j>>1;
    }
  }
  l=N;
  ps3=s3+N;
  while(l>1) {
    k=s3[1];
    s3[1]=*ps3;
    *ps3=k;
    ps3--;
    l--;
    j=1;
    while((j<<1)<=l) {
      i=j;
      if(s3[j<<1]>s3[i]) i=j<<1;
      if(((j<<1)<l)&&(s3[(j<<1)+1]>s3[i])) i=(j<<1)+1;
      if(i!=j) {
        k=s3[i];
        s3[i]=s3[j];
        s3[j]=k;
        j=i;
      }
      else j=l;
    }
  }

  // Pentru fiecare suma s1 se cauta binar o suma s2, astfel incat s1+s2=s
  ps3=s3;
  for(i=1;i<=N;i++) {
    ps3++;
    s1=*ps3;
    s2=s-s1;
    for(j=1;j<N;j<<=1);
    for(k=0;j;j>>=1)
     if((k+j<=N)&&(s3[k+j]<=s2)) k+=j;
    if(s3[k]==s2) {
      posibil=1;
      break;
    }
  }

  // Daca suma e posibila, atunci se gasesc numerele a caror suma este s1, respectiv s2
  if(posibil) {
    for(i=0;i<n;i++) {
      for(j=0;j<n;j++) {
        for(k=0;k<n;k++) {
          s=loto[i]+loto[j]+loto[k];
          if(s==s1) {
            g1=1;
            answer[0]=loto[i];
            answer[1]=loto[j];
            answer[2]=loto[k];
          }
          if(s==s2) {
            g2=1;
            answer[3]=loto[i];
            answer[4]=loto[j];
            answer[5]=loto[k];
          }
          if(g1&&g2) break;
        }
        if(g1&&g2) break;
      }
      if(g1&&g2) break;
    }
  }

  // Scrie raspunsul
  if(posibil)
   for(i=0;i<6;i++) printf("%d ",answer[i]);
  else printf("-1");

  return 0;
}