Cod sursa(job #335126)

Utilizator mlazariLazari Mihai mlazari Data 28 iulie 2009 18:59:57
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 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[NMAX*NMAX*NMAX+1],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
  for(i=0;i<n;i++)
   for(j=i;j<n;j++)
    for(k=j;k<n;k++) s3[++N]=loto[i]+loto[j]+loto[k];

  // Sorteaza crescator sumele obtinute cu HeapSort
  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;
  while(l>1) {
    k=s3[1];
    s3[1]=s3[l];
    s3[l--]=k;
    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
  for(i=1;i<=N;i++) {
    s1=s3[i];
    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;
}