612 - DNA Sorting - UVA

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<utility>
using namespace std;
bool cmp(const pair<int, string>& a,const pair<int, string>& b) {
 return a.first < b.first;
}
int val(const string& a) {
 int len = a.size(), cont = 0;
 for (int i = 0; i < len; i++)
  for (int j = i + 1; j < len; j++)
   if(a[i] > a[j]) cont++;
 return cont;
}
int main() {
 /*freopen("in.in", "r", stdin);
 freopen("out.out", "w", stdin);*/
 string linea;
 int test, n, m;
 bool first = true;
 getline(cin, linea);
 test = atoi(linea.c_str());
 getline(cin, linea);
 while (test--) {
  getline(cin, linea);
  sscanf(linea.c_str(), "%d %d", &n, &m);
  vector<pair <int, string> > lista(m);
  for (int i = 0; i < m; i++) {
   getline(cin, linea);
   lista[i] = make_pair(val(linea), linea);
  }
  getline(cin, linea);
  stable_sort(lista.begin(), lista.end(), cmp);
  if(!first) printf("\n");
  first = false;
  for (int i = 0; i < m; i++) {
   printf("%s\n", lista[i].second.c_str());
  }
 }
 return 0;
}

154 - Recycling, uva solution

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<algorithm>
#define inf 1 << 30
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
typedef long long ll;
char ciudades[100][5], linea[100], color[5], material[5];
int n;
void procesar() {
 int res = inf;
 int id = 0;
 for (int i = 0; i < n; i++) {
  int cont = 0;
  for (int j = 0; j < n; j++) {
   if (i == j) continue;
   for (int k = 0; k < 5; k++) {
    if (ciudades[i][k] != ciudades[j][k])
     cont++;
   }
  }
  if (cont < res)
   res = cont, id = i + 1;
 }
 printf("%d\n", id);
}
int main() {
 while(gets(linea)) {
  if (linea[0] == 'e') {
   procesar();
   n = 0;
  }
  else {
   if (linea[0] == '#') break;
   sscanf(linea, "%c/%c,%c/%c,%c/%c,%c/%c,%c/%c", &color[0], &material[0], &color[1], &material[1], &color[2], &material[2], &color[3], &material[3], &color[4], &material[4]); 
   for (int i = 0; i < 5; i++) {
    switch(color[i]) {
     case 'r': ciudades[n][0] = material[i]; break;
     case 'o': ciudades[n][1] = material[i]; break;
     case 'y': ciudades[n][2] = material[i]; break;
     case 'g': ciudades[n][3] = material[i]; break;
     case 'b': ciudades[n][4] = material[i]; break;
    }
   }
   n++;
  }
 }
 return 0;
}

624 - CD, uva

I didn't use recursion here I just used binary numbers which generate all possible combinations

lets say you have 5 objects we'll denote a combination by a binary number

so for a set {A,B,C,D,E} and binary number N where the ith bit says if the ith element has been taken or not

so {A,B,C,D,E}

00000 = {} the null set

10000 = {A}

01000 = {B}

11000 = {A,B}

etc...

If we keep counting from zero to 2^n (Excluding 2^n) we'll generate all possible combinations (power set)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define db(a) cout << #a << " = " << a << endl
#define foreach(it, l) for ( typeof(l.begin()) it = l.begin(); it != l.end(); it++) 
#define dbl(i, a) cout << "[" << i << "]" << " = "<< a << ", "; 
#define listar(lista) for(int i = 0; i < lista.size(); i++) { dbl(i, lista[i]);} cout << endl;
using namespace std;
int main() {
 int sum, cur, max, arreglo[20], index, n, tracks;
 while (scanf("%d", &n) != EOF) {
  scanf("%d", &tracks);
  sum = cur = index = 0;
  max = 1 << tracks;
  for (int i = 0; i < tracks; i++) 
   scanf("%d", arreglo + i);
   
  for (int i = 0; i < max; i++) {
   cur = 0;
   for (int j = 0; j < tracks; j++) {
    if ((1 << j) & i) {
     cur += arreglo[j];
    }
   }
   if (cur >= sum && cur <= n) 
    sum = cur, index = i;
  }
  for (int i = 0;i < tracks; i++) {
   if (1 << i & index) {
    printf("%d ", arreglo[i]);
   }
  }
  printf("sum:%d\n", sum);
 }
 return 0;
}