ACM TJU SPOJ Solutions

417 - Word Index, uva, solution

2012-11-22T13:57:00.000-08:00

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

2012-11-18T19:21:00.003-08:00

#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

2012-11-10T15:52:00.001-08:00

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

2012-10-19T07:39:00.001-07:00

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

2012-10-03T14:39:00.000-07:00

#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

2012-10-03T12:53:00.000-07:00

#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

2012-07-29T13:58:00.005-07:00

#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

2012-07-17T14:32:00.003-07:00

#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

2012-07-17T13:16:00.003-07:00

#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

2012-07-13T16:02:00.001-07:00

#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

2012-07-13T14:07:00.001-07:00

#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

2012-07-13T13:24:00.000-07:00

#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

2012-07-13T12:47:00.002-07:00

#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

2012-07-12T16:11:00.003-07:00

#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

2012-07-12T15:09:00.001-07:00

#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

2012-06-20T12:33:00.001-07:00

#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

2012-04-18T23:30:00.002-07:00

#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

2012-04-18T22:25:00.001-07:00

#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

2012-04-17T09:27:00.002-07:00

#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

2012-04-08T08:38:00.001-07:00

#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

2012-04-01T10:02:00.000-07:00

#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

2012-04-01T05:12:00.002-07:00

#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

2012-03-31T19:46:00.003-07:00

#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

2012-03-31T18:24:00.003-07:00

 #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

2012-03-30T11:12:00.003-07:00

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