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

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