Cod sursa(job #1370166)

Utilizator allexx2200Atanasiu Alexandru-Marian allexx2200 Data 3 martie 2015 13:17:16
Problema Loto Scor 65
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.36 kb
#include <stdio.h>
#include <map>

#include <vector>
#include <algorithm>

#define VECTOR_SIZE 100
#define FIN "loto.in"
#define FOUT "loto.out"

using namespace std;

struct vector3{
  int i,j,k;
};

struct celula{
  vector3 vect;
  int sum;
};

int N,S;
int v[VECTOR_SIZE];
int sume[VECTOR_SIZE*VECTOR_SIZE*VECTOR_SIZE];
FILE *in,*out;

int sol[6];

void loto(){
  std::map<int,vector3> hashTable;
  for(int i=0,s=0; i < N; i++){
    for(int j=0; j < N; j++){
      for(int k=0; k < N; k++,s++){
	vector3 aux {v[i],v[j],v[k]};
	hashTable[v[i]+v[j]+v[k]] = aux;
      }
    }
  }
    
  bool found = false;
  vector3 first,second;
  for(std::map<int,vector3>::iterator it = hashTable.begin(); it != hashTable.end(); ++it){
    int aux = it->first;
    first = it->second;
    try{
      second = hashTable.at(S-aux);
      found = true;
      break;
    }catch(std::out_of_range o){}
  }
  
  if(!found){
    sol[0] = -1;
  } else {
    sol[0] = first.i;
    sol[1] = first.j;
    sol[2] = first.k;
    sol[3] = second.i;
    sol[4] = second.j;
    sol[5] = second.k;
  } 
}


bool compare(celula c1, celula c2) { return (c1.sum<c2.sum); }

/*
void loto2(){
  std::vector<celula> hashTable;
  for(int i=0; i < N; i++){
    for(int j=0; j < N; j++){
      for(int k=0; k < N; k++){
	vector3 vec_aux {v[i], v[j], v[k]};
	celula aux {vec_aux, v[i]+v[j]+v[k]};
	hashTable.push_back(aux);
      }
    }
  }
    
  sort(hashTable.begin(), hashTable.end(), compare);
  
  for(std::vector<celula>::iterator it = hashTable.begin(); it != hashTable.end(); ++it){
    printf("%d:(%d,%d,%d)\n", it->sum, (it->vect).i, (it->vect).j, (it->vect).k);
  }
  
  vector3 first{0,0,0}, second{0,0,0};
  bool found = false;
  for(int i=0; i < N && !found; i++){
    for(int j=0; j < N && !found; j++){
      for(int k=0; k < N && !found; k++){
	if(v[i] + v[j] + v[k] >= S) continue;
	
	first.i = v[i];
	first.j = v[j];
	first.k = v[k];
	
	int sumAux = S - (v[i] + v[j] + v[k]);
	
	int lower = 0;
	int upper = hashTable.size() - 1;
	
	//cautare binara
	while(lower < upper){
	  if(lower == upper || lower == upper - 1){
	    if(hashTable[lower].sum == sumAux){
	      found = true;
	      second.i = hashTable[lower].vect.i;
	      second.j = hashTable[lower].vect.j;
	      second.k = hashTable[lower].vect.k;
	    } else if(hashTable[upper].sum == sumAux){
	      found = true;
	      second.i = hashTable[upper].vect.i;
	      second.j = hashTable[upper].vect.j;
	      second.k = hashTable[upper].vect.k;
	    } 
	    break;
	  }
	  int mid = lower + (upper - lower) / 2;
	  if(hashTable[mid].sum == sumAux){
	    found = true;
	    second.i = hashTable[mid].vect.i;
	    second.j = hashTable[mid].vect.j;
	    second.k = hashTable[mid].vect.k;
	    break;
	  }
	  if(hashTable[mid].sum < sumAux){
	    lower = mid+1;
	  } else {
	    upper = mid-1;
	  } 
	}
      }
    }
  }
  
  if(!found){
    sol[0] = -1;
  } else {
    sol[0] = first.i;
    sol[1] = first.j;
    sol[2] = first.k;
    sol[3] = second.i;
    sol[4] = second.j;
    sol[5] = second.k;
  } 
}
*/


int main(){
  in = fopen(FIN, "rt");
  out = fopen(FOUT, "wt");
  
  int res;
  
  res = fscanf(in, "%d%d", &N, &S);
  for(int i=0; i < N; i++){
    res = fscanf(in, "%d", &v[i]);
  }
  res++;
  
  loto();
  
  if(sol[0] == -1){
    fprintf(out, "-1");
  } else {
    for(int i=0; i < 6; i++){
      fprintf(out, "%d ", sol[i]);
    }
  }
  
  fclose(in);
  fclose(out);
  return 0;
}