2012年12月28日

UVa 124 - Following Orders


#include <cstdio>
#include <set>
#include <string>

bool c[26][26], first;
std::set<int> alpha;

void dfs(int i, int* count, std::string s) {
  if (i == alpha.size()) {
    puts(s.c_str());
    return;
  }
  int j, k;
  for (j = 0; j < 26; j++) {
    if (!count[j] && alpha.count(j)) {
      count[j] = -1;
      s.insert(s.end(), j + 'a');
      for (k = 1; k < 26; k++)
        if (c[j][k]) count[k]--;
      dfs(i + 1, count, s);
      count[j] = 0;
      for (k = 1; k < 26; k++)
        if (c[j][k]) count[k]++;
      s.erase(s.end() - 1);
    }
  }
}

int main() {
  char s[99];
  while (gets(s)) {
    if (first) puts("");
    first = 1;
    alpha.erase(alpha.begin(), alpha.end());
    int i, j, k, count[26] = {};
    for (i = 0; i < 26; i++)
      for (j = 0; j < 26; j++)
        c[i][j] = 0;
    for (i = 0; s[i]; i++)
      if (s[i] != ' ') alpha.insert(s[i] - 'a');
    gets(s);
    for (i = 2; ; i += 4) {
      c[s[i - 2] - 'a'][s[i] - 'a'] = 1;
      count[s[i] - 'a']++;
      if (!s[i + 1]) break;
    }
    dfs(0, count, "");
  }
  return 0;
}

2012年12月26日

UVa 10162 - Last Digit


#include <stdio.h>
#include <string.h>

int main() {
  char s[200];
  int num[4][10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
                    0, 1, 4, 9, 6, 5, 6, 9, 4, 1,
                    0, 1, 8, 7, 4, 5, 6, 3, 2, 9,
                    0, 1, 6, 1, 6, 5, 6, 1, 6, 1};
  while (gets(s) && s[0] != '0') {
    int i, len = strlen(s), sum = 0, last = 0;
    if (len > 1) sum = (s[len - 2] - '0') * 47, last = (s[len - 2] - '0') * 10;
    for (i = 1; i <= s[len - 1] - '0'; i++)
      sum += num[(last + i + 3) % 4][i];
    printf("%d\n", sum % 10);
  }
  return 0;
}

2012年12月23日

C DCT / IDCT


#include <stdio.h>
#include <math.h>
#define N 512

double COS[8][8], C[8];
unsigned char pic[N][N];
double dct[N][N], idct[N][N];

void init() {
  int i, j;
  for (i = 0; i < 8; i++) {
    for (j = 0; j < 8; j++)
      COS[i][j] = cos((2 * i + 1) * j * acos(-1) / 16.0);
    if (i) C[i] = 1;
    else C[i] = 1 / sqrt(2);
  }
}

void DCT() {
  int r, c, i, j, x, y;
  for (r = 0; r < 64; r++)
    for (c = 0; c < 64; c++)
      for (i = 0; i < 8; i++)
        for (j = 0; j < 8; j++) {
          double sum = 0;
          for (x = 0; x < 8; x++)
            for (y = 0; y < 8; y++)
              sum += (pic[r * 8 + x][c * 8 + y] - 128) * COS[x][i] * COS[y][j];
          sum *= C[i] * C[j] * 0.25;
          dct[r * 8 + i][c * 8 + j] = sum;
      }
}

void IDCT() {
  freopen("idct.raw", "wb", stdout);
  int r, c, i, j, x, y;
  for (r = 0; r < 64; r++)
    for (c = 0; c < 64; c++)
      for (i = 0; i < 8; i++)
        for (j = 0; j < 8; j++) {
          double sum = 0;
          for (x = 0; x < 8; x++)
            for (y = 0; y < 8; y++)
              sum += C[x] * C[y] * dct[r * 8 + x][c * 8 + y] * COS[i][x] * COS[j][y];
          sum *= 0.25;
          sum += 128;
          idct[r * 8 + i][c * 8 + j] = sum;
      }
  for (r = 0; r < N; r++)
    for (c = 0; c < N; c++)
      putchar(idct[r][c]);
}

void quantization() {
  int table[8][8] = {
    16, 11, 10, 16, 24, 40, 51, 61,
    12, 12, 14, 19, 26, 58, 60, 55,
    14, 13, 16, 24, 40, 57, 69, 56,
    14, 17, 22, 29, 51, 87, 80, 82,
    18, 22, 37, 56, 68, 109, 103, 77,
    24, 35, 55, 64, 81, 104, 113, 92,
    49, 64, 78, 87, 103, 121, 120, 101,
    72, 92, 95, 98, 112, 100, 103, 99
  };
  int r, c, i, j;
  for (r = 0; r < 64; r++)
    for (c = 0; c < 64; c++)
      for (i = 0; i < 8; i++)
        for (j = 0; j < 8; j++) {
          dct[r * 8 + i][c * 8 + j] = round(dct[r * 8 + i][c * 8 + j] / table[i][j]);
          dct[r * 8 + i][c * 8 + j] = dct[r * 8 + i][c * 8 + j] * table[i][j];
        }
}

void MSE() {
  freopen("sub.raw", "wb", stdout);
  double MSE = 0;
  int r, c;
  for (r = 0; r < N; r++)
    for (c = 0; c < N; c++) {
      MSE += (pic[r][c] - idct[r][c]) * (pic[r][c] - idct[r][c]);
      putchar(abs(pic[r][c] - idct[r][c]));
    }
  MSE /= (512 * 512);
  double PSNR = 10 * log10(255 * 255 / MSE);
  freopen("PSNR.txt", "w", stdout);
  printf("%.2lf\n", PSNR);
}

int main() {
  freopen("Lena.raw", "rb", stdin);
  int r, c;
  for (r = 0; r < N; r++)
    for (c = 0; c < N; c++)
      scanf("%c", &pic[r][c]);
  init();
  DCT();
  quantization();
  IDCT();
  MSE();
  return 0;
}

2012年12月22日

UVa 652 - Eight


#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <map>
#include <algorithm>
#define N 9
using namespace std;

typedef vector<int> V;

map<V, string> visit;
queue<V> q;

void push(V& v, string& path, char c) {
  if (!visit.count(v)) {
    q.push(v);
    string nextP = path;
    nextP.insert(nextP.end(), c);
    visit[v] = nextP;
  }
}

int main() {
  int i, tmp;
  V now;
  for (i = 1; i <= N; i++)
    now.push_back(i % N);
  visit[now] = "";
  q.push(now);
  while (!q.empty()) {
    now = q.front();
    string path = visit[now];
    q.pop();
    int index;
    for (index = 0; index < N; index++)
      if (!now[index]) break;
    if (index % 3 != 2) {
      V nextV = now;
      swap(nextV[index], nextV[index + 1]);
      push(nextV, path, 'l');
    }
    if (index % 3) {
      V nextV = now;
      swap(nextV[index], nextV[index - 1]);
      push(nextV, path, 'r');
    }
    if (index > 2) {
      V nextV = now;
      swap(nextV[index], nextV[index - 3]);
      push(nextV, path, 'd');
    }
    if (index < 6) {
      V nextV = now;
      swap(nextV[index], nextV[index + 3]);
      push(nextV, path, 'u');
    }
  }
  int T;
  scanf("%d", &T);
  getchar();
  while (T--) {
    getchar();
    char temp[20];
    gets(temp);
    V ans;
    for (i = 0; temp[i]; i++)
      if ('0' < temp[i] && temp[i] <= '9') ans.push_back(temp[i] - '0');
      else if (temp[i] == 'x') ans.push_back(0);
    bool find = visit.count(ans);
    if (find) {
      string path = visit[ans];
      reverse(path.begin(), path.end());
      puts(path.c_str());
    } else {
      puts("unsolvable");
    }
    if (T) puts("");
  }
  return 0;
}

UVa 11513 - 9 Puzzle


#include <cstdio>
#include <cstdlib>
#include <queue>
#include <string>
#include <map>
using namespace std;

int main() {
  int i, tmp;
  map<int, string> visit; // every integer(key) has its string(value) http://www.cplusplus.com/reference/map/map/
  int now = 123456789; // first state
  visit[now] = ""; // path is NULL
  queue<int> q; // queue of BFS
  q.push(now); // push first state in queue

  // BFS
  while (!q.empty()) {
    now = q.front();
    string path = visit[now];
    q.pop();
    int index;
    char add[5], nextV[20];
    string nextP;
    for (i = 0; i < 3; i++) { // loop that swaps every row
      sprintf(nextV, "%d", now); // print this state on a string "nextV", it'll make it easy to do swap
      nextP = path;

      // shift this row
      index = i * 3 + 2;
      tmp = nextV[index - 2];
      nextV[index - 2] = nextV[index - 1];
      nextV[index - 1] = nextV[index];
      nextV[index] = tmp;

      if (visit.count(atoi(nextV))) continue; // if we've reached this state, then do nothing
      
      // add "H + row number" after path
      add[0] = 'H';
      add[1] = i + 1 + '0';
      add[2] = '\0';
      nextP.append(add); 


      q.push(atoi(nextV)); // push this state in BFS queue
      visit[atoi(nextV)] = nextP; // stored string of this path
    }
    for (i = 0; i < 3; i++) { // loop that swaps every column
      sprintf(nextV, "%d", now); // print this state on a string "nextV", it'll make it easy to do swap
      nextP = path;

      // shift this column
      tmp = nextV[i + 6];
      nextV[i + 6] = nextV[i + 3];
      nextV[i + 3] = nextV[i];
      nextV[i] = tmp;

      if (visit.count(atoi(nextV))) continue; // if we've reached this state, then do nothing
      
      // add "V + column number" after path
      add[0] = 'V';
      add[1] = i + 1 + '0';
      add[2] = '\0';
      nextP.append(add);
      q.push(atoi(nextV));
      visit[atoi(nextV)] = nextP;
    }
  }
  // After this BFS algorithm, we've generate all possible state which can reach from 123456789

  while (scanf("%d", &tmp) && tmp) {
    int ans = tmp;
    for (i = 1; i < 9; i++) {
      scanf("%d", &tmp);
      ans = ans * 10 + tmp;
    }

    bool find = visit.count(ans); // return true if we can find this state

    if (find) {
      string path = visit[ans]; // path of this state was stored in map
      printf("%d ", path.length() >> 1); // length of moving is length of this path / 2

      // because we generate solution from 123456789, 
      // but now we want to reach 123456789, 
      // so we have to print the answer in contrary direction
      for (i = path.length() - 2; i >= 0; i -= 2)
        printf("%c%c", path[i], path[i + 1]);
      puts("");
    } else {
      puts("Not solvable");
    }
  }
  return 0;
}

UVa 276 - Egyptian Multiplication


#include <stdio.h>

long long cal(char* s) {
  long long sum = 0;
  int i;
  for (i = 0; s[i]; i++)
    if (s[i] == '|') sum++;
    else if (s[i] == 'n') sum += 10;
    else if (s[i] == '9') sum += 100;
    else if (s[i] == '8') sum += 1000;
    else if (s[i] == 'r') sum += 10000;
  return sum;
}

int print(int n) {
  int now = 10, len = 0, first = 1;
  while (n) {
    int times = (n % now) / (now / 10);
    n = n / now * now;
    if (times && !first) putchar(' '), len++;
    if (times) first = 0;
    while (times--) {
      if (now == 10) putchar('|');
      else if (now == 100) putchar('n');
      else if (now == 1000) putchar('9');
      else if (now == 10000) putchar('8');
      else  putchar('r');
      len++;
    }
    now *= 10;
  }
  return len;
}

int main() {
  char a[100], b[100];
  while (gets(a) && a[0] != ' ') {
    gets(b);
    long long sum1 = cal(a), sum2 = cal(b), now, temp = sum2;
    int i, check[17] = {};
    for (i = 16, now = 65536; i >= 0 && temp > 0; i--, now >>= 1)
      if (temp >= now) check[i] = 1, temp -= now;
    for (i = 0, now = 1; now <= sum2; i++, now <<= 1) {
      int len = print(now);
      if (check[i]) {
        len += 2;
        printf(" *");
      }
      printf("%.*s", 34 - len, "                                  ");
      print((sum1 * now) % 100000);
      puts("");
    }
    printf("The solution is: ");
    print((sum1 * sum2) % 100000);
    puts("");
  }
  return 0;
}

2012年12月18日

UVa 536 - Tree Recovery


#include <cstdio>
#include <string>
using std::string;

int now;
char pre[50], in[50];

struct Node {
  Node (char c, Node* l, Node* r) : c(c), l(l), r(r) {
  }
  char c;
  Node* l;
  Node* r;
};

Node* build(string s) {
  char c = pre[now];
  if (s.find(c) != string::npos) {
    now++;
    return new Node(c, build(s.substr(0, s.find(c))), build(s.substr(s.find(c) + 1)));
  }
  return NULL;
}

void post(Node* node) {
  if (!node) return;
  post(node->l);
  post(node->r);
  putchar(node->c);
}

int main() {
  while (scanf("%s%s", pre, in) == 2) {
    now = 0;
    post(build(string(in)));
    puts("");
  }
  return 0;
}

UVa 10464 - Big Big Real Numbers

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    while (n > 0) {
      BigDecimal a = cin.nextBigDecimal(), b = cin.nextBigDecimal();
      String ans = a.add(b).toString();
      int i;
      for (i = ans.length() - 1; ans.charAt(i) == '0'; i--);
      if (ans.charAt(i) == '.') i++;
      boolean point = false;
      for (int j = 0; j <= i; j++) {
        if (ans.charAt(j) == '.') point = true;
        System.out.print(ans.charAt(j));
      }
      if (!point) System.out.print(".0");
      System.out.println();
      n--;
    }
  }
}

2012年12月17日

UVa 10551 - Basic Remains

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    while (cin.hasNext()) {
      BigInteger b = cin.nextBigInteger();
      if (b.compareTo(BigInteger.ZERO) == 0) break;
      String s1 = cin.next(), s2 = cin.next();
      BigInteger p = BigInteger.ZERO, m = BigInteger.ZERO;
      for (int i = 0; i < s1.length(); i++)
        p = p.multiply(b).add(BigInteger.valueOf(s1.charAt(i) - '0'));
      for (int i = 0; i < s2.length(); i++)
        m = m.multiply(b).add(BigInteger.valueOf(s2.charAt(i) - '0'));
      BigInteger ans = p.mod(m);
      System.out.println(ans.toString(b.intValue()));
    }
  }
}

2012年12月16日

UVa 10311 - Goldbach and Euler


#include <cstdio>
#include <cmath>
#include <algorithm>
#define S 100000001

bool prime[S];
int p[6000000], N;

int main() {
  int i, j, k, s = sqrt(S);
  prime[0] = prime[1] = 1;
  for (i = 2; i <= s; i++)
    if (!prime[i])
      for (k = (S - 1) / i, j = i * k; k >= i; k--, j -= i)
        if (!prime[k]) prime[j] = 1;
  p[N++] = 2;
  for (i = 3; i < S; i += 2)
    if (!prime[i]) p[N++] = i;
  int n;
  while (scanf("%d", &n) == 1) {
    int a = 0, b = 0;
    if (n & 1) {
      if (n > 3 && !prime[n - 2]) a = 2, b = n - 2;
    } else {
      i = std::lower_bound(p, p + N, n >> 1) - p;
      while (p[i] >= n >> 1) i--;
      for (; i >= 0; i--) {
        j = std::upper_bound(p, p + N, n - p[i]) - p;
        j--;
        if (i != j && p[i] + p[j] == n) {
          a = p[i], b = p[j];
          break;
        }
      }
    }
    if (a) printf("%d is the sum of %d and %d.\n", n, a, b);
    else printf("%d is not the sum of two primes!\n", n);
  }
  return 0;
}

UVa 11408 - Count DePrimes


#include <stdio.h>
#define S 5000001

int prime[S], rec[S], fac[S], sum[S];

int main() {
  int i, j;
  prime[0] = prime[1] = 1;
  for (i = 2; i < S; i++)
    if (!prime[i]) {
      fac[i] = i;
      for (j = i + i; j < S; j += i) {
        prime[j] = 1;
        rec[j] = i;
      }
    }
  for (i = 0; i < S; i++)
    if (!fac[i] && rec[i]) {
      fac[i] = fac[i / rec[i]];
      if ((i / rec[i]) % rec[i]) fac[i] += rec[i];
    }
  for (i = 1; i < S; i++)
    sum[i] = sum[i - 1] + !prime[fac[i]];
  int a, b;
  while (scanf("%d", &a) && a) {
    scanf("%d", &b);
    printf("%d\n", sum[b] - sum[a] + !prime[fac[a]]);
  }
  return 0;
}

2012年12月15日

UVa 10780 - Again Prime? No Time.


#include <stdio.h>
#define S 10000

int prime[S], p[S], N;

void add(int n, int* rec) {
  int i;
  for (i = 0; i < N && p[i] <= n; i++)
    while (!(n % p[i]) && n > 1) {
      n /= p[i];
      rec[i]++;
    }
}

int main() {
  int i, j;
  for (i = 2; i < S; i++)
    if (!prime[i]) {
      p[N++] = i;
      for (j = i + i; j < S; j += i)
        prime[j] = 1;
    }
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int m, n, num[S] = {}, fac[S] = {}, flag = 1, min = 2e9;
    scanf("%d%d", &m, &n);
    add(m, num);
    for (i = 2; i <= n; i++)
      add(i, fac);
    for (i = 0; i < N && flag; i++)
      if (num[i] > fac[i]) flag = 0;
      else if (num[i] && fac[i] && fac[i] / num[i] < min) min = fac[i] / num[i];
    printf("Case %d:\n", C++);
    if (flag) printf("%d\n", min);
    else puts("Impossible to divide");
  }
  return 0;
}

UVa 10140 - Prime Distance


#include <stdio.h>
#define S 47000

int prime[S] = {1, 1}, p[S], N, check[1000001];

int isprime(int n) {
  if (n < S) return !prime[n];
  int i;
  for (i = 0; i < N && n > p[i]; i++)
    if (!(n % p[i])) return 0;
  return 1;
}

int main() {
  int i, j, l, u;
  for (i = 2; i < S; i++)
    if (!prime[i]) {
      p[N++] = i;
      for (j = i + i; j < S; j += i)
        prime[j] = 1;
    }
  while (scanf("%d%d", &l, &u) == 2) {
    for (i = l; ; i++) {
      check[i - l] = 1;
      if (!isprime(i))
        check[i - l] = 0;
      if (i == u) break;
    }
    int a = -1, b = -1, max = 0, min = 2e9, mx1, mx2, mn1, mn2;
    for (i = 0; i <= u - l; i++) {
      if (check[i]) {
        a = i;
        if (b != -1) {
          if (a - b > max) max = a - b, mx1 = b, mx2 = a;
          if (a - b < min) min = a - b, mn1 = b, mn2 = a;
        }
        b = a;
      }
    }
    if (!max) puts("There are no adjacent primes.");
    else printf("%d,%d are closest, %d,%d are most distant.\n", mn1 + l, mn2 + l, mx1 + l, mx2 + l);
  }
  return 0;
}

2012年12月4日

UVa 11624 - Fire!


#include <cstdio>
#include <queue>
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

int d[1010][1010];
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int r, c, R, C;
    scanf("%d%d", &R, &C);
    getchar();
    queue<P> fire, q;
    bool ok[1010][1010] = {};
    for (r = 1; r <= R; r++) {
      char map[1010];
      gets(map + 1);
      for (c = 1; c <= C; c++) {
        d[r][c] = 0;
        if (map[c] == '.') ok[r][c] = 1;
        else if (map[c] == 'F') fire.push(MP(r, c));
        else if (map[c] == 'J') {
          ok[r][c] = 1;
          q.push(MP(r, c));
        }
      }
    }
    int find = 0, prev = -1;
    while (!q.empty() && !find) {
      int i, dis = d[q.front().first][q.front().second];
      if (dis != prev) {
        int burn = fire.size();
        while (burn--) {
          r = fire.front().first;
          c = fire.front().second;
          fire.pop();
          for (i = 0; i < 4; i++)
            if (ok[r + dr[i]][c + dc[i]]) {
              fire.push(MP(r + dr[i], c + dc[i]));
              ok[r + dr[i]][c + dc[i]] = 0;
            }
        }
      }
      r = q.front().first;
      c = q.front().second;
      q.pop();
      prev = d[r][c];
      for (i = 0; i < 4; i++) {
        if ((r + dr[i]) == (R + 1) || !(r + dr[i]) || (c + dc[i]) == (C + 1) || !(c + dc[i])) {
          printf("%d\n", dis + 1);
          find = 1;
          break;
        }
        if (!d[r + dr[i]][c + dc[i]] && ok[r + dr[i]][c + dc[i]]) {
          d[r + dr[i]][c + dc[i]] = dis + 1;
          q.push(MP(r + dr[i], c + dc[i]));
        }
      }
    }
    if (!find) puts("IMPOSSIBLE");
  }
  return 0;
}

2012年12月2日

UVa 110 - Meta-Loopless Sorts


#include <stdio.h>

char space[20] = "                ";
char alpha[20];

void swap (char* a, char* b) {
  char temp = *a;
  *a = *b;
  *b = temp;
}

void dfs(int now, int max) {
  int i;
  if (now == max - 1) {
    printf("%.*s", max * 2, space);
    printf("writeln");
    printf("%.*s%s", max * 2, alpha, ")\n");
    return;
  }
  for (i = 0; i < now + 2; i++) {
    printf("%.*s", 2 + 2 * now, space);
    if (i == 0) printf("if %c < %c then\n", alpha[now * 2 + 1], alpha[now * 2 + 3]);
    else if (i != now + 1) printf("else if %c < %c then\n", alpha[(now - i) * 2 + 1], alpha[(now - i) * 2 + 3]);
    else puts("else");
    dfs(now + 1, max);
    if (i == now + 1) {
      for (i = 0; i < max - 1; i++)
        swap(&alpha[i * 2 + 1], &alpha[i * 2 + 3]);
      return;
    }
    swap(&alpha[(now + 1 - i) * 2 + 1], &alpha[(now + 1 - i) * 2 - 1]);
  }
}

int main() {
  int N;
  scanf("%d", &N);
  while (N--) {
    int i, j, n;
    scanf("%d", &n);
    char rec[20] = "(a,b,c,d,e,f,g,h";
    for (i = 0; i < 20; i++)
      alpha[i] = rec[i];
    puts("program sort(input,output);");
    puts("var");
    printf("%.*s%s", n * 2 - 1, alpha + 1, " : integer;\n");
    printf("begin\n  readln");
    printf("%.*s%s", n * 2, alpha, ");\n");
    dfs(0, n);
    puts("end.");
    if (N) puts("");
  }
  return 0;
}

UVa 11974 - Switch The Lights


#include <cstdio>
#include <queue>

int main() {
  int T, c = 1;
  scanf("%d", &T);
  while (T--) {
    int n, m, i, j, s[100];
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++) {
      s[i] = 0;
      for (j = 0; j < n; j++) {
        int tmp;
        scanf("%d", &tmp);
        s[i] = s[i] * 2 + tmp;
      }
    }
    int source = 0, find = 0, visit[65536] = {};
    std::queue<int> q;
    for (j = 0; j < n; j++)
      source = source * 2 + 1;
    q.push(source);
    printf("Case %d: ", c++);
    while (!q.empty()) {
      int now = q.front(), dis = visit[now];
      if (!now) {
        printf("%d\n", dis);
        find = 1;
        break;
      }
      q.pop();
      for (i = 0; i < m; i++) {
        int temp = now, press = s[i], next = now, two = 1;
        while (temp || press) {
          int bit = temp & 1, change = press & 1;
          if (change) {
            bit = !bit;
            if (bit) next += two;
            else next -= two;
          }
          temp >>= 1;
          press >>= 1;
          two <<= 1;
        }
        if (next != source && !visit[next]) {
          visit[next] = dis + 1;
          q.push(next);
        }
      }
    }
    if (!find) puts("IMPOSSIBLE");
  }
  return 0;
}

UVa 12160 - Unlock the Lock


#include <cstdio>
#include <queue>

int main() {
  int l, u, r, c = 1;
  while (scanf("%d%d%d", &l, &u, &r) && l || u || r) {
    int i, method[20];
    for (i = 0; i < r; i++)
      scanf("%d", &method[i]);
    printf("Case %d: ", c++);
    std::queue<int> q;
    int flag = 0 , d[10000] = {};
    q.push(l);
    while (!q.empty()) {
      int now = q.front(), dis = d[now];
      q.pop();
      if (now == u) {
        printf("%d\n", dis);
        flag = 1;
        break;
      }
      for (i = 0; i < r; i++) {
        int next = (now + method[i]) % 10000;
        if (!d[next] && next != l) {
          q.push(next);
          d[next] = dis + 1;
        }
      }
    }
    if (!flag) puts("Permanently Locked");
  }
  return 0;
}

UVa 10267 - Graphical Editor


#include <stdio.h>

char map[255][255];
int R, C, visit[255][255];

void fill(int r, int c, char color) {
  if (r > R || r <= 0 || c > C || c <= 0 || visit[r][c]) return;
  visit[r][c] = 1;
  char now = map[r][c];
  if (r != R && map[r + 1][c] == now) fill(r + 1, c, color);
  if (c != C && map[r][c + 1] == now) fill(r, c + 1, color);
  if (r > 1 && map[r - 1][c] == now) fill(r - 1, c, color);
  if (c > 1 && map[r][c - 1] == now) fill(r, c - 1, color);
  map[r][c] = color;
}

int max(int a, int b) {
  return a > b ? a : b;
}

int main() {
  char s[100], color[20];
  int r, c, r1, c1, r2, c2;
  while (gets(s)) {
    if (s[0] == 'X') return 0;
    if (s[0] == 'I') {
      sscanf(s, "%*s%d%d", &C, &R);
      for (r = 1; r <= R; r++) {
        for (c = 1; c <= C; c++)
          map[r][c] = 'O';
        map[r][c] = 0;
      }
    } else if (s[0] == 'C') {
      for (r = 1; r <= R; r++)
        for (c = 1; c <= C; c++)
          map[r][c] = 'O';
    } else if (s[0] == 'L') {
      sscanf(s, "%*s%d%d%s", &c, &r, color);
      map[r][c] = color[0];
    } else if (s[0] == 'V') {
      sscanf(s, "%*s%d%d%d%s", &c, &r1, &r2, color);
      for (r = r1 + r2 - max(r1, r2); r <= max(r1, r2); r++)
        map[r][c] = color[0];
    } else if (s[0] == 'H') {
      sscanf(s, "%*s%d%d%d%s", &c1, &c2, &r, color);
      for (c = c1 + c2 - max(c1, c2); c <= max(c1, c2); c++)
        map[r][c] = color[0];
    } else if (s[0] == 'K') {
      sscanf(s, "%*s%d%d%d%d%s", &c1, &r1, &c2, &r2, color);
      for (r = r1 + r2 - max(r1, r2); r <= max(r1, r2); r++)
        for (c = c1 + c2 - max(c1, c2); c <= max(c1, c2); c++)
          map[r][c] = color[0];
    } else if (s[0] == 'F') {
      sscanf(s, "%*s%d%d%s", &c, &r, color);
      for (r1 = 1; r1 <= R; r1++)
        for (c1 = 1; c1 <= C; c1++)
          visit[r1][c1] = 0;
      fill(r, c, color[0]);
    } else if (s[0] == 'S') {
      puts(s + 2);
      for (r = 1; r <= R; r++)
        puts(map[r] + 1);
    }
  }
}