Cod sursa(job #316066)

Utilizator raica_cristiraica dumitru cristian raica_cristi Data 18 mai 2009 11:02:13
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include<stdio.h>
#define dim 110
#define dim2 (dim*dim*dim)
int a[dim],b[dim2],n,i,k,p=1;
struct elemente { int e1,e2,e3;} el[dim2];
long long unsigned sum;
void read()
{
     scanf("%d%d",&n,&sum);
     for(i=1;i<=n;i++)
     scanf("%d",&a[i]);
}
void sw(int &i,int &k)
{
     int aux=b[i];
    b[i]=b[k];
     b[k]=aux;
     i++;
     k--;
}
void sort(int st,int dr)
{
     int i=st,j=dr,p=b[(st+dr)/2];
     do
     {
		 while(b[i]<p)
		 i++;
		 while(p<b[j])
		 j--;
		 if(i<=j)
			sw(i,j);
				}
				while(i<=j);
		 if(st<j)
				 sort(st,j);
		 if(i<dr)
				 sort(i,dr);
     return ;
     
}
void afis(int a[dim*dim*dim],int n)
{
     int i;
     for(i=1;i<=n;i++)
     printf("%d ",a[i]);
}
void gen()
{
     int k,j,i;
     for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
     for(k=1;k<=n;k++,p++)
     {
                          b[p]=a[i]+a[j]+a[k];
                          el[p].e1=i;
                          el[p].e2=j;
                          el[p].e3=k;
                          }
     sort(1,p-1);
    // afis(b,p-1);
}
int find2(int st,int dr,int el)

{
    while(st<=dr)
    {
                 if(sum-el>b[(st+dr)/2])
                 st=(st+dr)/2+1;
                 else
                 if(sum-el<b[(st+dr)/2])
                 dr=(st+dr)/2-1;
                 else
                 return (st+dr)/2;
}
return 0;}
void write(int i,int k)
{
     int c[6],aux;
     c[1]=el[i].e1;
     c[2]=el[i].e2;
     c[3]=el[i].e3;
     c[4]=el[k].e1;
     c[5]=el[k].e2;
     c[6]=el[k].e3;
     for(i=1;i<=6;i++)
     for(k=i+1;k<=6;k++)
     if(c[i]>c[k])
     {
                  aux=c[i];
                  c[i]=c[k];
                  c[k]=aux;
                  }
     for(i=1;i<=6;i++)
     printf("%d ",c[i]);
     printf("\n");
}
void find()
{
     int poz;
     for(i=1;i<=p;i++)
     {
                      poz=find2(1,n,b[i]);
                      if(poz)
                      {write(i,poz);
                      return;
                      }
}}
int main ()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    read();
    gen();
    find();
   // afis2(int x1,x2);
return 0;
}