Cod sursa(job #170879)

Utilizator TociToxAnonim Anonim TociTox Data 3 aprilie 2008 13:27:21
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include<stdio.h>   
#include<stdlib.h>   
#define NMAX 101   
  
int n;   
int S, v[NMAX], trei[NMAX * NMAX * NMAX];   
int i,j,k,st=1,dr;   
  
void pivot(int s,int d,int &m)   
{   
 int ps=0,pd=1,aux;   
 while(s<d)   
 {if(trei[s]>=trei[d]) {aux=trei[s]; trei[s]=trei[d]; trei[d]=aux;   
               aux=ps; ps=pd; pd=aux;} s+=ps; d-=pd;}   
m=s;}   
  
  
  
int Q_Sort(int s,int d)   
{ int m;   
  if(s<d) {pivot(s,d,m);   
      Q_Sort(s,m-1);   
      Q_Sort(m+1,d);} }   
  
  
int scout(int val)   
{   
  for(i=1; i<=n; i++)   
  for(j=1; j<=n; j++)   
  for(k=1; k<=n; k++)   
  
  if(v[i] + v[j] + v[k] == val)   
              { printf("%d %d %d ",v[i],v[j],v[k]);   
            return 0; }   
  
return -1;}   
  
  
int main()   
{   
  freopen("loto.in","r",stdin);   
  freopen("loto.out","w",stdout);   
  
  scanf("%d %d",&n,&S);   
  
  for(i=1; i<=n; i++) scanf("%d",&v[i]);   
  
  for(i=1; i<=n; i++)   
  for(j=1; j<=n; j++)   
  for(k=1; k<=n; k++) trei[++dr] = v[i] + v[j]+ v[k];   
  
  Q_Sort(1,dr);   
  
  while(n)   
  {   
  
  for(; trei[st] + trei[dr] > S && st<dr; dr--);   
  
  
     if( trei[st] + trei[dr] == S)   
     { scout(trei[st]); scout(trei[dr]); printf("\n"); return 0;}   
  
     if(st==dr) break;   
  
  for(; trei[st] + trei[dr] < S && st<dr; st++);   
  
  }   
  
  printf("-1\n");   
  
  return 0; }  
#include<stdio.h>
#include<stdlib.h>
#define NMAX 101

int n;
int S, v[NMAX], trei[NMAX * NMAX * NMAX];
int i,j,k,st=1,dr;

void pivot(int s,int d,int &m)
{
 int ps=0,pd=1,aux;
 while(s<d)
 {if(trei[s]>=trei[d]) {aux=trei[s]; trei[s]=trei[d]; trei[d]=aux;
		       aux=ps; ps=pd; pd=aux;} s+=ps; d-=pd;}
m=s;}



int Q_Sort(int s,int d)
{ int m;
  if(s<d) {pivot(s,d,m);
	  Q_Sort(s,m-1);
	  Q_Sort(m+1,d);} }


int scout(int val)
{
  for(i=1; i<=n; i++)
  for(j=1; j<=n; j++)
  for(k=1; k<=n; k++)

  if(v[i] + v[j] + v[k] == val)
		      { printf("%d %d %d ",v[i],v[j],v[k]);
			return 0; }

return -1;}


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

  scanf("%d %d",&n,&S);

  for(i=1; i<=n; i++) scanf("%d",&v[i]);

  for(i=1; i<=n; i++)
  for(j=1; j<=n; j++)
  for(k=1; k<=n; k++) trei[++dr] = v[i] + v[j]+ v[k];

  Q_Sort(1,dr);

  while(n)
  {

  for(; trei[st] + trei[dr] > S && st<dr; dr--);


     if( trei[st] + trei[dr] == S)
     { scout(trei[st]); scout(trei[dr]); printf("\n"); return 0;}

     if(st==dr) break;

  for(; trei[st] + trei[dr] < S && st<dr; st++);

  }

  printf("-1\n");

  return 0; }