417 - Word Index, uva, solution

simple BFS using a queue.

#include <iostream> 
#include <sstream> 
#include <cstring> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <ctime> 
#include <cctype> 
#include <cmath> 
#include <vector> 
#include <map> 
#include <set> 
#include <queue>
#include<bitset>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
 #endif
 string s;
 map<string, int> mapa;
 queue<string> q;
 q.push("");
 int cont = 0;
 while (!q.empty()) {
  string val = q.front();
  q.pop();
  mapa[val] = cont++;
  if (val.size() == 5) continue;
  for (char i = (val == "") ? 'a' : val[val.size() - 1] + 1; i < 'z' + 1; i++) {
   q.push(val + i);
  }
 }
 char linea[6];
 while (gets(linea)) { 
  printf("%d\n", mapa[linea]); 
 }
 return 0;
}

11520 - Fill the Square, uva, solution

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define listar(lista) for (int i = 0; i < lista.size(); i++) db(lista[i])
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
using namespace std;
int dirx[] = {0, 0, -1, 1};
int diry[] = {-1, 1, 0, 0};
vector<string> matriz;
int n;
void llenar (int x, int y) {
 if (x < 0 || x >= n || y < 0 || y >= n || matriz[x][y] != '.') return;
 for (char i = 'A'; i < 'Z' + 1; i++) {
  bool can = true;
  for (int k = 0; k < 4; k++) {
   if (x + dirx[k] >= 0 && 
    x + dirx[k] < n &&
    y + diry[k] >= 0 &&
    y + diry[k] < n && matriz[x + dirx[k]][y + diry[k]] == i)
    can = false;
  }
  if (can)  {
   matriz[x][y] = i;
   break;
  }
 } 
}
int main() {
 int t, caso;
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 scanf("%d", &t);
 caso = t;
 while (t--) {
  scanf("%d", &n);
  matriz.resize(n);
  for (int i = 0; i < n; i++) {
   cin >> matriz[i];
  }
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
    llenar(i, j);
   }
  }
  
  printf("Case %d:\n", caso - t);
  
  for (int i = 0; i < n; i++) {
   cout << matriz[i] << endl;
  }
  
 }
 return 0;
}

10336 - Rank the Languages, uva, solution

This can be done with both DFS or BSF graph traversal.

#include <iostream> 
#include <sstream> 
#include <cstring> 
#include <cstdio> 
#include <cstdlib> 
#include <algorithm> 
#include <ctime> 
#include <cctype> 
#include <cmath> 
#include <vector> 
#include <map> 
#include <set> 
#include <queue>
#include<bitset>
#define foreach(it, l) for (typeof(l.begin()) it = l.begin(); it != l.end(); it++)
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
using namespace std;
vector<string> lista;
int h, w;
void dfs(int i, int j, char cur) {
 if (i >= 0 && i < h && j >= 0 && j < w && lista[i][j] == cur) {
  lista[i][j] = '-';
  dfs(i + 1, j, cur);
  dfs(i - 1, j, cur);
  dfs(i, j - 1, cur);
  dfs(i, j + 1, cur);
 }
}
bool def(int i, int j, char cur) {
 if (i > 0 && lista[i - 1][j] == cur) return true;
 if (i < h - 1 && lista[i + 1][j] == cur) return true;
 if (j > 0 && lista[i][j - 1] == cur) return true;
 if (j < w - 1 && lista[i][j + 1] == cur) return true;
 return false;
}
bool cmp(const pair<char, int>& a, const pair<char, int>& b) {
 if (a.second > b.second) return true;
 return a.first < b.first;
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int t;
 string s;
 set<char> sc;
 cin >> t;
 int start = t;
 while (t--) {
  cin >> h >> w;
  lista.resize(h);
  for (int i = 0; i < h; i++) {
   cin >> lista[i];
  }
  map<char, int> mapa;
  sc.clear();
  for (int i = 0; i < h; i++) {
   for (int j = 0; j < w; j++) {
    if (lista[i][j] != '-' && def(i, j, lista[i][j])) {
     char cur = lista[i][j];
     mapa[cur]++;
     sc.insert(cur);
     dfs(i, j, cur);
    }
   }
  }
  printf("World #%d\n", start - t);
  vector< pair<char,int> > res;
  foreach(it, mapa) {
   res.push_back(make_pair(it->first, it->second));
  }
  sort(res.begin(), res.end(), cmp);
  for (int i = 0; i < res.size(); i++) {
   cout << res[i].first << ": " << res[i].second << endl;
  }
 }
 return 0;
}

305 - Joseph, uva, solution

Just a simple simulation be aware that it would take so much time,
so as they are just 13 cases then, we calculate them so just will have
to output the memorized values.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class Main {

 public static int solve(int k) {
  for (int m = 1; ; m++) {
   ArrayList<integer> lista = new ArrayList<integer>();
   for (int i = 1; i <= 2 * k; i++) {
    lista.add(i);
   }
   int idx = (m - 1) % lista.size();
   boolean exito = true;
   while (lista.size() > k && exito) {
    if (lista.get(idx) > k) {
     lista.remove(idx);
    }
    else exito = false;
    idx += m - 1;
    idx %= lista.size();
   }
   if (exito) return m;
  }
 }
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int res[] = new int[14];
  for (int i = 1; i < 14; i++) {
   res[i] = solve(i);
  }
  int k = sc.nextInt();
  while (k != 0) {
   System.out.println(res[k]); 
   k = sc.nextInt();
  }
 }

}

10340 - All in All, uva, solution

#include<iostream>
#include<cstdio>
#include<utility>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
using namespace std;

int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 string s, t;
 while (cin >> s >> t) {
  int ss = s.size();
  int tt = t.size();
  if (ss > tt) {
   puts("No");
   continue;
  }
  int start = 0;
  bool success = true;
  for (int i = 0; i < ss && success; i++) {
   while (start < tt && s[i] != t[start++]) ;
   if (s[i] != t[start - 1]) success = false;
  }
  if (success) puts("Yes");
  else puts("No");
 }
 return 0;
}

410 - Station Balance, uva, solution

#include<iostream>
#include<cstdio>
#include<utility>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
using namespace std;
bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
 return a.first <= b.first;
}
bool cmp_list(const vector< pair<int, int> >& a, const vector< pair<int, int> >& b) {
 int min_a = 20, min_b = 20;
 for (int i = 0; i < a.size(); i++) {
  if (a[i].second < min_a) min_a = a[i].second;
 }
 for (int i = 0; i < b.size(); i++) {
  if (b[i].second < min_b) min_b = b[i].second;
 }
 return min_a <= min_b;
}
int main() {
 int c, s, cont = 0;
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 while (scanf("%d %d", &c, &s) !=EOF) {
  vector< pair<int, int> > lista(2 * c);
  double A = 0;
  for (int i = 0; i < s; i++) {
   scanf("%d", &lista[i].first);   
   A += lista[i].first;
   lista[i].second = i;
  }
  for (int i = s; i < 2 * c; i++) {
   lista[i].second  = i;
  }
  A /= c;
  
  sort(lista.begin(), lista.end(), cmp);
  
  double res = 0;
  vector< vector< pair<int, int> > > elementos(c);
  for (int i = 0; i < c; i++) {
   res += fabs(lista[i].first + lista[2 * c - i - 1].first - A); 
   if (lista[i].second < lista[2 * c - i - 1].second) {
    elementos[i].push_back(lista[i]);
    elementos[i].push_back(lista[2 * c - i - 1]);
   }
   else {
    elementos[i].push_back(lista[2 * c - i - 1]);
    elementos[i].push_back(lista[i]);
   }
  }
  printf("Set #%d\n", ++cont);
  int n = elementos.size();
  
  sort(elementos.begin(), elementos.end(), cmp_list);
  for (int i = 0; i  < c; i++) {
    printf("% d:", i);
    for (int j = 0; j < elementos[i].size(); j++) {
     if (elementos[i][j].first != 0)
     printf(" %d", elementos[i][j].first);
    }
    puts("");
  }
  printf("IMBALANCE = %.5f\n\n", res);
 }
 return 0;
}

10189 - Minesweeper, uva

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
int n, m;
int dx[] = {-1, -1, -1,  0, 0, 1, 1, 1};
int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1};
vector<string> grid;
char tonum(int x, int y) {
 int cont = 0;
 for (int i = 0; i < 8; i++)
  if (x + dx[i] >= 0 && x + dx[i] < n && y + dy[i] >= 0 && y + dy[i] < m)
   if (grid[x + dx[i]][y + dy[i]] == '*') cont++;
 return cont + '0';
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 string linea;
 int field = 1;
 cin >> n >> m;
 while (1) {
  for (int i = 0; i < n; i++) {
   cin >> linea;
   grid.push_back(linea);
  }
  for (int i = 0; i < n; i++) 
   for (int j = 0; j < m; j++) 
    if (grid[i][j] != '*')
     grid[i][j] = tonum(i, j);
  
  cout << "Field #" << field++ << ":"<< endl;
  for (int i = 0; i < n; i++)
   cout << grid[i] << endl;
  cin >> n >> m;
  if (n == 0 && m == 0) break;
  cout << endl;
  grid.clear();
 }
 return 0;
}

11734 - Big Number of Teams will Solve This, uva

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int t;
 scanf("%d\n", &t) ;
 char *team, *judge;
 char line[30], line2[30];
 bool wa , pe;
 for (int i = 1; i <= t; i++) {
  gets(line);gets(line2);
  team = line; judge = line2;
  wa = pe = false;
  for ( ; *team && !wa; team++) {
   if (*team == *judge) {
    judge++;
    continue;
   }
   if(*team == ' ') {
    pe = true;
    continue;
   }
   if(*team != *judge) wa = true;
  }
  if (*team != *judge) wa = true;
  
  if (!pe && !wa)
    printf("Case %d: Yes\n", i); 
  else if (wa)
    printf("Case %d: Wrong Answer\n", i); 
   else
    printf("Case %d: Output Format Error\n", i);     
 }
 return 0;
}

148 - Anagram checker, uva

#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(m, it) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
struct word {
 string str; char trait[26];
 bool operator >= (const word& other) {
  int i = 0;
  for (; i < 26 && trait[i] >= other.trait[i]; i++);
  return i == 26;
 }
 word& operator -= (const word& other) {
  for (int i = -1; ++i < 26; trait[i] -= other.trait[i]);
  return *this;
 }
 word& operator += (const word& other) {
  for (int i = -1; ++i < 26; trait[i] += other.trait[i]);
  return *this;
 }
};
void genTrait(const char *str, char * trait) {
 for (fill(&trait[0], &trait[26], 0); *str != 0; ++trait[*str++ - 'A']);
}
typedef vector<word>::iterator iterpal;
void searchAnagram(iterpal ini, iterpal fin, word& frase) {
 int i = 0;
 string &str = frase.str;
 for (; i < 26 && frase.trait[i] == 0; i++);
 if (i == 26) {
  istringstream ss(str);
  vector<string> original, generado;
  for (string word; ss >> word && word != "="; original.push_back(word));
  for (string word; ss >> word ; generado.push_back(word));
  sort(original.begin(), original.end());
  if (original != generado) {
   printf("%s\n", str.c_str());
  }
  return;
 }
 for (iterpal it = ini; it != fin; it++) {
  if (frase >= *it) {
   frase -= *it;
   str.push_back(' ');
   str.append(it->str);
   searchAnagram(it + 1, fin, frase);
   str.erase(str.length() - it->str.length() - 1);
   frase += *it;
  }
 }
 
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 vector<word> dict, subset;
 char line[30];
 for (word palabra; gets(line) != NULL && line[0] != '#'; ) {
  palabra.str = line;
  genTrait(line, palabra.trait);
  dict.push_back(palabra);
 }
 for (string linea; getline(cin, linea) && linea != "#"; subset.clear()) {
  word frase = {linea};
  linea.erase(remove(linea.begin(), linea.end(), ' '), linea.end());
  if (linea.empty()) continue;
  
  genTrait(linea.c_str(), frase.trait);
  for (iterpal it = dict.begin(); it != dict.end(); it++) {
   if (frase >= *it) {
    subset.push_back(*it);
   }
  }
  frase.str.append(" =");
  searchAnagram(subset.begin(), subset.end(), frase);
 }
    return 0;
}

263 - Number Chains, uva

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(m, it) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
int n;
bool espali(string linea) {
 int n = linea.size();
 for (int i = 0; i < n / 2; i++) {
  if (linea[i] != linea[n - i - 1])
   return false;
 }
 return true;
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 string s;
 char buf[10];
 int mayor, menor, prev, len;
 set<int> nums;
 while (cin >> s) {
  if (s == "0") break;
  prev = -1;
  len = 0;
  nums.clear();
  printf("Original number was %s\n", s.c_str());
  while (true) {
   sort(s.rbegin(), s.rend());
   mayor = atoi(s.c_str());
   reverse(s.begin(), s.end());
   menor = atoi(s.c_str());
   printf("%d - %d = %d\n", mayor, menor, mayor - menor);
   len++;
   prev = mayor - menor;
   if (!nums.count(prev))
    nums.insert(prev);
   else break;
   sprintf(buf, "%d", prev);
   s = buf;
  }
  printf("Chain length %d\n\n", len);
 }
 return 0;
}

Here is the Statement

353 - Pesky Palindromes, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(m, it) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
int n;
bool espali(string linea) {
 int n = linea.size();
 for (int i = 0; i < n / 2; i++) {
  if (linea[i] != linea[n - i - 1])
   return false;
 }
 return true;
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 char linea[100];
 set<string> s;
 while (gets(linea) != NULL) {
  int n = strlen(linea);
  s.clear();
  for (int i = 0; i < n; i++) {
   for (int j = i; j < n; j++) {
    string aux = string(linea).substr(i, j - i + 1);
    if (espali(aux))
     s.insert(aux);
   }
  }
  printf("The string '%s' contains %d palindromes.\n", linea , s.size());
 }
 return 0;
}

Here is the Statement

409 - Excuses, Excuses, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(m, it) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
string limpiar(string s) {
 int n = s.size();
 for (int i = 0; i < n; i++) {
  if (!isalpha(s[i])) s[i] = ' ';
  else s[i] = tolower(s[i]);
 }
 return s;
}
bool contain(vector<string> & lista, string keyword) {
 int n = lista.size();
 for (int i = 0; i < n; i++) {
  if (lista[i] == keyword)
   return true;
 }
 return false;
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int k, x;
 vector<string> keywords;
 map<string, int> excuses;
 char keyword[40], excuse[100];
 int cont = 1;
 while (scanf("%d %d\n", &k, &x) != EOF) {
  keywords.clear();
  excuses.clear();
  for (int i = 0; i < k; i++) {
   gets(keyword);
   keywords.push_back(keyword);
  }
  for (int i = 0; i < x; i++) {
   gets(excuse);
   excuses[(string)excuse];
  }
  int best = 0;
  foreach(excuses, it) {
   string cad = limpiar(it->first);
   char *st, *buf, sep[] = " ";
   buf = strdup(cad.c_str());
   st = strtok(buf, sep);
   while (st) {
    if (contain(keywords, st))
     it->second++;
    st = strtok(0, sep);
   }
   best = max(it->second, best);
  }
  printf("Excuse Set #%d\n", cont++);
  foreach(excuses, it) {
   if (it->second == best)
    printf("%s\n", it->first.c_str());
  }
  puts("");
 }
 return 0;
}

Here is the Statement

401 - Palindromes, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(it, m) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
map<char, char> m;
bool espali(string s) {
 int n = s.size();
 for (int i = 0; i < n / 2; i++) {
  if (s[i] != s[n - i - 1])
   return false;
 }
 return true;
}
bool esmirror(string s) {
 int n = s.size();
 for (int i = 0; i <= n / 2; i++)
  if (s[i] != m[s[n - i - 1]])
   return false;
 return true;
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 char s[30];
 m['A'] = 'A'; m['M'] = 'M'; m['Y'] = 'Y';
 m['B'] = '-'; m['N'] = '-'; m['Z'] = '5';
 m['C'] = '-'; m['O'] = 'O'; m['1'] = '1';
 m['D'] = '-'; m['P'] = '-'; m['2'] = 'S';
 m['E'] = '3'; m['Q'] = '-'; m['3'] = 'E';
 m['F'] = '-'; m['R'] = '-'; m['4'] = '-';
 m['G'] = '-'; m['S'] = '2'; m['5'] = 'Z';
 m['H'] = 'H'; m['T'] = 'T'; m['6'] = '-';
 m['I'] = 'I'; m['U'] = 'U'; m['7'] = '-';
 m['J'] = 'L'; m['V'] = 'V'; m['8'] = '8';
 m['K'] = '-'; m['W'] = 'W'; m['9'] = '-';
 m['L'] = 'J'; m['X'] = 'X'; 
 bool pali, mirror;
 while(gets(s) != NULL) {
  pali = espali(s);
  mirror = esmirror(s);
  if (pali && mirror)
   printf("%s -- is a mirrored palindrome.\n", s);
  else 
   if (pali) 
    printf("%s -- is a regular palindrome.\n", s);
   else
    if (mirror)
     printf("%s -- is a mirrored string.\n", s);
    else
     printf("%s -- is not a palindrome.\n", s);
  puts("");
 }
 return 0;
}

here is the statement

10878 - Decode the tape, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(it, m) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 char s[20];
 while (gets(s) != NULL) {
  if (s[0] == '_') continue;
  int mask = 0;
  for (int i = 8; i >= 4; i--) {
   if (s[9 - i] == 'o') mask |= 1 << (i - 1);
  }
  for (int i = 2; i >= 0; i--) {
   if (s[9 - i] == 'o') mask |= 1 << i;
  }
  printf("%c", (char)mask);
 }
 return 0;
}

here is the statement

471 - Magic Numbers, uva

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(it, m) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
bool has_repeated_digits(long long int s) {
 int mask = 0;
 while (s) {
  if (mask & (1 << (s % 10)))
   return true;
  mask |= 1 << (s % 10);
  s /= 10;
 }
 return false;
}

int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int t;
 long long int max_s1 = 9876543210, s1, s2, max_s2, N;
 scanf("%d", &t);
 for (; t--;) {
  scanf("%lld", &N);
  max_s2 = max_s1 / N;
  for (s2 = 1; s2 <= max_s2; s2++) {
   if (has_repeated_digits(s2)) continue;
   s1 = s2 * N;
   if (has_repeated_digits(s1)) continue;
   printf("%lld / %lld = %lld\n", s1, s2, N);
  }
  if (t)
   puts("");
 }
 return 0;
}

here is the statement

846 - Steps, UVA

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(it, m) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  //freopen("ou.out", "w", stdout);
 #endif
 int x, y;
 int t;
 scanf("%d", &t);
 //db(t);
 for (int i = 0; i < t; i++) {
  scanf("%d%d", &x , &y);
  //db2(x, y);
  if (x == y) {
   puts("0");
   continue;
  }
  int n = (int)sqrt(y - x);
  //db(n);
  if (n * n == y - x)
   n = 2 * n - 1;
  else
   if (n * (n + 1) < y - x) {
    n = 2 * n + 1;
   }
   else n = 2 * n;
  /*db2(x, y);
  db(n);*/
  printf("%d\n", n);
 }
 return 0;
}

a good explanation can be found here
Algorithmist

1406. The Sierpinski Fractal, tju online judge

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(it, m) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
#define MAX 2048
using namespace std;
char M[MAX][MAX];
void solve(int n, int v, int h) {
 if (n == 1) {
  M[v][h] = '/';
  M[v - 1][h + 1] = '/';
  M[v - 1][h + 2] = '\\';
  M[v][h + 1] = '_';
  M[v][h + 2] = '_';
  M[v][h + 3] = '\\';
 }
 else {
  solve(n - 1, v, h);
  solve(n - 1, v - pow(2., n - 1), h + pow(2., n - 1));
  solve(n - 1, v, h + pow(2., n));
 } 
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int n;
 for (int i = 0; i < MAX; i++) {
  for (int j = 0; j < MAX; j++) {
   M[i][j] = ' ';
  }
 }
 string linea = "";
 while (scanf("%d", &n) != EOF && n != 0) {
  for (int i = 0; i < pow(2., n + 1); i++) {
   for (int j = 0; j < pow(2., n + 1); j++) {
    M[i][j] = ' ';
   }
  }
  solve(n, pow(2., n) - 1, 0);
  for (int i = 0; i < pow(2., n) ; i++) {
   linea = "";
   for (int j = 0; j < pow(2., n + 1); j++) {
    if (M[i][j] != ' ') {
     printf("%s%c",linea.c_str(), M[i][j]);
     linea = "";
    }
    else linea += " ";
   }
   puts("");
  }
  puts("");
 }
 return 0;
}

1178. Fractal, tju online judge

#include<iostream>
#include<cstdio>
#include<cmath>
#include<map>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
#define foreach(it, m) \
for (typeof(m.begin()) it = m.begin(); it != m.end(); it++)
#define MAX 729
using namespace std;
char M[MAX][MAX];
void solve(int n, int v, int h) {
 if (n == 1) {
  M[v][h] = 'X';
 }
 else {
  solve(n - 1, v - pow(3., n - 2), h - pow(3., n - 2));
  solve(n - 1, v - pow(3., n - 2), h + pow(3., n - 2));
  solve(n - 1, v, h);
  solve(n - 1, v + pow(3., n - 2), h - pow(3., n - 2));
  solve(n - 1, v + pow(3., n - 2), h + pow(3., n - 2));
 } 
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int n = 7;
 for (int i = 0; i < MAX; i++) {
  for (int j = 0; j < MAX; j++) {
   M[i][j] = ' ';
  }
 }
 string linea;
 solve(n, (int)pow(3., n - 1) / 2, (int)pow(3., n - 1) / 2);
 while (scanf("%d", &n) != EOF) {
  if (n == -1) break;
  for (int i = 0; i < pow(3., n - 1) ; i++) {
   linea = "";
   for (int j = 0; j < pow(3., n - 1); j++) {
    if (M[i][j] != 'X')
     linea += " ";
    else {
     printf("%sX", linea.c_str());
     linea = "";
    }
   }
   puts("");
  }
  puts("-");
 }
 return 0;
}

10827 - Maximum sum on a torus, uva

#include<cstdio>
#include<cstring>
#include<iostream>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl
using namespace std;
int main() {
 #ifdef dennisbot
 freopen("in.in", "r", stdin);
 //freopen("ou.out", "w", stdout);
 #endif
 int m ,n;
 scanf("%d", &m);
 while (m --) {
  scanf("%d", &n);
  int matriz[n][n], fila[n];
  for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
    scanf("%d", &matriz[i][j]);
   }
  }
  /*for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
    if (j != 0) cout << " ";
    cout << matriz[i][j];
   }
   cout << endl;
  }*/
  int sum = 0, sum_min = 0,total = 0, var, max = -1000, min = 1000;
  for (int i = 0; i < n; i++) {
   memset(fila, 0, sizeof fila);
   for (int ii = i; ii < i + n; ii++) {
    sum = sum_min = total = 0;
    min = 1000;
    for (int j = 0; j < n; j++) {
     fila[j] += matriz[ii % n][j];
     total += fila[j];
     if (sum >= 0) {
      sum += fila[j];
     }
     else sum = fila[j];
     if (sum_min <= 0) {
      sum_min += fila[j];
     }
     else sum_min = fila[j];
     if (sum > max) max = sum;
     if (sum_min < min) min = sum_min;
    }
    max = std::max(max, total - min);
   }
   
  }
  printf("%d\n", max);
 }
 return 0;
}

11636 - Hello World, uva

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <vector>
#include <stdio.h>
#define db(a) \
cout << #a << " = " << a << endl
#define db2(a, b) \
cout << #a << " = " << a << " " << #b << " = " << b << endl
#define inf (1<<30)
using namespace std;
int lista[10001];
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
 #endif
 int seed = 1, cont = 0, t = 1;
 for (int i = 1; i < 10001; i++) {
  if (seed >= i) {
   lista[i] = cont;
  }
  else {
   while (seed *= 2, cont++, seed < i);
   lista[i] = cont;
  }
 }
 int n;
 while (scanf("%d", &n) != EOF && n > 0) {
  printf("Case %d: %d\n", t++, lista[n]); 
 }
    return 0;
}

679 - Dropping Balls, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<utility>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
int bin_to_entero(string binario) {
 int n = binario.size();
 int t = 1, res = 0;
 for (int i = n - 1; i >= 0; i--) {
  res += t * (binario[i] - 48);
  t *= 2;
 }
 return res;
}
int main() {
 vector< vector<string> > level;
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 vector<string> seed;
 seed.push_back("10");
 seed.push_back("11");
 level.push_back(seed);
 int t = 2;
 for (int k = 3; k < 21; k++) {
  vector<string> fila;
  for (int i = 0; i < t; i++) {
   fila.push_back(level[k - 3][i] + "0");
  }
  for (int i = 0; i < t; i++) {
   fila.push_back(level[k - 3][i] + "1");
  }
  level.push_back(fila);
  t *= 2;
 }
 int n, D, I;
 scanf("%d", &n);
 for (int i = 0; i < n; i++) {
  scanf("%d%d", &D, &I);
  printf("%d\n", bin_to_entero(level[D - 2][I - 1]));
 }
 scanf("%d", &n);
 return 0;
}

785 - Grid Colouring, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<utility>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
using namespace std;
vector<string> grilla;
vector< pair<int, int> > m;
void dfs(char marcar,int x, int y) {
 if (x >= 0 && x < grilla.size() 
 && y >= 0 && y < grilla[x].size() 
 && grilla[x][y] == 32) {
  grilla[x][y] = marcar;
  dfs(marcar, x - 1, y);
  dfs(marcar, x, y - 1);
  dfs(marcar, x + 1, y);
  dfs(marcar, x, y + 1); 
 }
}
int main() {
 
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int len = 0;
 char linea[100];
 while (gets(linea) != NULL) {
  if (linea[0] == '_') {
   int n = m.size();
   for (int i = 0; i < n; i++) {
    char marcar = grilla[m[i].first][m[i].second];
    grilla[m[i].first][m[i].second] = 32;
    dfs(marcar, m[i].first, m[i].second);
   }
   n = grilla.size();
   for (int i = 0; i < n; i++) {
    printf("%s\n", grilla[i].c_str());
   }
   puts(linea);
   grilla.clear();
   m.clear();
   continue;
  }
  len = strlen(linea);
  for (int i = 0; i < len; i++) {
   if (linea[i] != 32 && linea[i] != 'X')
    m.push_back(make_pair(grilla.size(), i));
  }
  grilla.push_back(linea);
 }
 return 0;
}

413 - Up and Down Sequences, UVA

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define listar(lista) for (int i = 0; i < lista.size(); i++) db(lista[i])
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
 #endif
 int aveup = 0, avedown = 0;
 double  sumup = 0, sumdown = 0;
 int creciente = 0, decreciente = 0;
 bool first = true, crece = true, decrece = true;
 int d, leido, cont = 0;
 while (scanf("%d", &d) != EOF) {
  if (d != 0) {
   cont++;
   if (first) {
    leido = d;
    first = false;
    continue;
   }
   if (leido == d) {
    if (crece)
     creciente++;
    if (decrece)
     decreciente++;
    leido = d;
    continue;
   }
   if (leido < d) {
    if (decrece) {
     if (creciente != decreciente) {
      sumdown += decreciente;
      avedown++;
     }
     decrece = false;
     decreciente = 0;
    }
    crece = true;
    creciente++;
    leido = d;
    continue;
   }
   if (leido > d) {
    if (crece) {
     if(creciente != decreciente) {
      sumup += creciente;
      aveup++;
     }
     crece = false;
     creciente = 0;
    }
    decrece = true;
    decreciente++;
    leido = d;
   }
  }
  else {
   if (cont == 0) break;
   if (creciente == decreciente)
    printf("Nr values = %d:  %.6f %.6f\n", cont, 0. , 0.);
   else {
    if (crece) sumup += creciente, aveup++;
    if (decrece) sumdown += decreciente, avedown++;
    printf("Nr values = %d:  %.6f %.6f\n",cont , (aveup != 0) ? sumup / aveup : 0, (avedown != 0) ? sumdown / avedown : 0);
   }
   creciente = decreciente = leido = cont = 0;
   first = crece = decrece = true;
   sumdown = sumup = aveup = avedown = 0;
  }
 }
 return 0;
}

567 - Risk, uva

 #include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<map>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " #b << " = " << b << endl
#define foreach(mapa, it) for (typeof(mapa.begin()) it = mapa.begin(); it != mapa.end(); it++)
using namespace std;
map<int, vector<int> > adyacencia;
map<int, int> dist;
void bfs(int a, int b) {
 queue<int> q;
 q.push(a);
 dist.clear();
 dist[a] = 0;
 while (!q.empty()) {
  int u = q.front(); q.pop();
  if (u == b) {
   printf("%2d to %2d: %d\n", a, b, dist[b]); 
   break;
  }
  for (int i = 0; i < adyacencia[u].size(); i++) {
   if (dist.count(adyacencia[u][i])) continue;
   dist[adyacencia[u][i]] = dist[u] + 1;
   q.push(adyacencia[u][i]);
  }
 }
}
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int n, var, ini, fin, cont = 1, ret;
 while (1) {
  adyacencia.clear();
  dist.clear();
  for (int i = 1; i < 20; i++) {
   ret = scanf("%d", &n);
   if (ret == EOF) return 0;
   for (int j = 0; j < n; j++) {
    scanf("%d", &var);
    adyacencia[i].push_back(var);
    adyacencia[var].push_back(i);
   }
  }
  scanf("%d", &n);
  printf("Test Set #%d\n", cont++);
  for (int i = 0; i < n; i++) {
   scanf("%d", &ini);
   scanf("%d", &fin);
   bfs(ini, fin);
  }
  puts("");
 }
}

2841. Bitwise Reverse, tju

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#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() {
 /*freopen("perm.in", "r", stdin);
 freopen("perm.out", "w", stdout);*/
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
 #endif 
 int n;
 while (scanf("%d", &n) != EOF) {
  if (n == 0) {
   break;
  }
  string num = "";
  for (int i = 0; i < 32; i++) {
   if (n >> i & 1) {
    num += "1";
   }
   else num += "0";
  }
  num = num.substr(0, num.find_last_of("1") + 1);
  int t = 1, res = 0;
  for (int i = num.size() - 1; i >= 0; i--) {
   res += (num[i] - 48) * t;
   t *= 2;
  }
  printf("%d\n", res);
 }
 return 0;
}

10667 - Largest Block, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  //freopen("ou.out", "w", stdout);
 #endif
 int p, s, b, r1, c1, r2, c2, matriz[101][101], fila[101], max, sum;
 scanf("%d", &p);
 for (;p; p--) {
  scanf("%d", &s);
  for (int i = 0; i < s; i++)
   for (int j = 0; j < s; j++)
    matriz[i][j] = 1;
  scanf("%d", &b);
  for (int k = 0; k < b; k++) {
   scanf("%d%d%d%d", &r1, &c1, &r2, &c2);
   r1--, c1--, r2--, c2--;
   for (int i = r1; i <= r2; i++) {
    for (int j = c1; j <= c2; j++) {
     matriz[i][j] = 0;
    }
   }
  }
  max = 0;
  for (int i = 0; i < s; i++) {
  
   for(int k = 0; k < s; k++) fila[k] = 0;
   
   for (int ii = i; ii < s; ii++) {
    sum = 0;
    for (int j = 0; j < s; j++) {
     fila[j] += matriz[ii][j];
     if (fila[j] == ii - i + 1) sum += fila[j];
     else sum = 0;
     if (sum > max) max = sum;
    }
   }
  }
  printf("%d\n", max);
  
 }
 return 0;
}

836 - Largest Submatrix, uva

#include<iostream>
#include<cstdio>
#include<cstring>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  freopen("ou.out", "w", stdout);
 #endif
 int test, i, j, n, matriz[100][100], fila[100], div = 1, sum = 0, max = 0;
 char var[100];
 scanf("%d\n", &test);
 while (test--) {
  i = 0;
  while (gets(var) && var[0] != '\0') {
   n = strlen(var);
   for (int j = 0; j < n; j++) {
    matriz[i][j] = var[j] - 48;
   }
   i++;
  }
  max = 0;
  for (int i = 0; i < n; i++) {
   memset(fila, 0, sizeof fila);
   for (int ii = i; ii < n; ii++) {
    sum = 0;
    for (int j = 0; j < n; j++) {
     fila[j] += matriz[ii][j];
     if (fila[j] == ii - i + 1) sum += fila[j];
     else sum = 0;
     if (sum > max) max = sum;
    }
   }
  }
  printf("%d\n", max);
  if (test != 0) puts("");
 }
 return 0;
}

507 - Jill Rides Again, uva

#include<iostream>
#include<cstdio>
#include<vector>
#include<utility>
#include<ctime>
#include<algorithm>
#define db(a) cout << #a << " = " << a << endl
#define db2(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl
#define db3(a, b, c) cout << #a << " = " << a << " " << #b << " = " << b << " " << #c << " = " << c << endl
using namespace std;
int main() {
 #ifdef dennisbot
  freopen("in.in", "r", stdin);
  //freopen("ou.out", "w", stdout);
  clock_t start = clock();
 #endif
 int b, s;
 cin >> b;
 for (int i = 0; i < b; i++) {
  cin >> s;
  int sum = -1, cur = 0, inf = 0, sup = 0, max = -1, var, d = 0;
  for (int j = 0; j < s - 1; j++) {
   cin >> var;
   if (j != 0) {
    if (sum >= 0)
     sum += var;
    else
     sum = var, cur = j;
    if (sum == max and j - cur > d or sum > max)
     inf = cur, sup = j, max = sum, d = sup - inf;
   }
   else
    sum = var, max = var;
  }
  if (max > 0)
   printf("The nicest part of route %d is between stops %d and %d\n", i + 1, inf + 1, sup + 2);
  else
   printf("Route %d has no nice parts\n", i + 1);
 }
 #ifdef dennisbot
  printf("\ntime=%.3fs\n", (clock() - start) * 1. / CLOCKS_PER_SEC);
 #endif
 return 0;
}

294 - Divisors - UVA

#include<iostream>
#include<cstdio>
#define MAX 40000
using namespace std;
int crivo[MAX + 1];
int primos[MAX + 1];
int n_primos;
void init_crivo() {
 n_primos = 0;
 crivo[0] = crivo[1] = 1;
 for (int i = 2; i <= MAX; i++) {
  if(!crivo[i]) {
   primos[n_primos++] = i;
   for (int j = i; i * j <= MAX; j++)
    crivo[i * j] = 1;
  }
 }
}
int NOD (int n) {
 if(n == 1) return 1;
 int r = 1, j;
 if(n <= MAX && !crivo[n]) return 2;
 for (int i = 0; primos[i] * primos[i] <= n; i++) {
  j = 0;
  while(n % primos[i] == 0) {
   n /= primos[i];
   j++;
  }
  r *= (j + 1);
  if(n == 1) return r;
 }
 if(r == 1) return 2;
 return r * 2;
}
int main() {
 int t, L, H, P, D;
 init_crivo();
 cin >> t;
 while(t--) {
  cin >> L >> H;
  D = P = 0;
  for (int i = L; i <= H; i++) {
   int nod = NOD(i);
   if(nod > D) D = nod, P = i;
  }
  printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, H, P, D);
 }
 return 0;
}

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;
}