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

2012年11月30日

UVa 11074 - Draw Grid


#include <stdio.h>

char map[1000][1000];

int main() {
  int s, t, n, test = 1;
  while (scanf("%d%d%d", &s, &t, &n) && s) {
    printf("Case %d:\n", test++);
    int r, c, l = s * n + t * (n + 1);
    for (r = 1; r <= l; r++) {
      for (c = 1; c <= l; c++)
        map[r][c] = '*';
      map[r][c] = 0;
    }
    int sr, sc;
    for (sr = t + 1; sr < l; sr += s + t)
      for (sc = t + 1; sc < l; sc += s + t) {
        int er, ec;
        for (er = sr; er < sr + s; er++)
          for (ec = sc; ec < sc + s; ec++)
            map[er][ec] = '.';
      }
    for (r = 1; r <= l; r++)
      puts(map[r] + 1);
    puts("");
  }
  return 0;
}

2012年11月27日

UVa 10027 - Language Cardinality


#include <cstdio>
#include <set>
#include <string>
using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  getchar();
  while (n--) {
    int now, l;
    char init[50];
    set<string> dic;
    gets(init);
    for (l = 0; init[l]; l++);
    init[l - 1] = '\0';
    dic.insert(string(init + 1));
    int num = 0, len[200], inf = 0;
    char s[100], ori[20][100], rep[20][100];
    while (gets(s) && s[0]) {
      int l1 = 0, l2 = 0;
      for (l = 1; s[l]; l++)
        if (s[l] == '\"') break;
        else ori[num][l1++] = s[l];
      ori[num][l1] = '\0';
      len[num] = l1;
      for (l += 4; s[l]; l++)
        if (s[l] == '\"') break;
        else rep[num][l2++] = s[l];
      rep[num][l2] = '\0';
      if (!l1 && l2) {
        inf = 1;
      } else if (l1 && l2 && l1 != l2) {
        int loc = string(rep[num]).find(ori[num]);
        if (loc >= 0 && loc < l2) inf = 1;
      }
      num++;
    }
    for (now = 0; now < num && !inf; now++) {
      int rec = dic.size();
      for (set<string>::iterator it = dic.begin(); it != dic.end() && !inf; it++) {
        string temp = *it;
        int start, add = 0;
        while (!inf) {
          start = temp.find(ori[now], add++);
          if (start < 0 || start >= temp.length()) break;
          string next(temp);
          next.erase(start, len[now]);
          next.insert(start, rep[now]);
          dic.insert(next);
          if (dic.size() > 1000) inf = 1;
        }
      }
      if (rec != dic.size()) now = -1;
    }
    if (!inf) printf("%d\n", dic.size());
    else puts("Too many.");
    if (n) puts("");
  }
  return 0;
}

UVa 762 - We Ship Cheap

STL, STL, and STL! lol
#include <cstdio>
#include <string>
#include <map>
#include <set>
#define MP make_pair
using namespace std;
typedef pair<string, string> P;

void print(map<string, string> parent, string now) {
  if (now.compare(parent[now]) == 0) return;
  print(parent, parent[now]);
  printf("%s %s\n", parent[now].c_str(), now.c_str());
}

int main() {
  int n, first = 1;
  while (scanf("%d", &n) == 1) {
    if (!first) puts("");
    first = 0;
    set<string> road;
    set<P> con;
    while (n--) {
      char s1[20], s2[20];
      scanf("%s%s", s1, s2);
      road.insert(string(s1));
      road.insert(string(s2));
      con.insert(MP(string(s1), string(s2)));
      con.insert(MP(string(s2), string(s1)));
    }
    char s[20], e[20];
    scanf("%s%s", s, e);
    map<string, string> parent;
    map<string, int> d;
    set<string> visit;
    for (set<string>::iterator it = road.begin(); it != road.end(); it++)
      d[*it] = 2e9;
    d[s] = 0;
    parent[s] = s;
    while (1) {
      int min = 2e9, flag = 0;
      set<string>::iterator now;
      for (set<string>::iterator it = road.begin(); it != road.end(); it++)
        if (!visit.count(*it) && d[*it] < min) min = d[*it], now = it, flag = 1;
      if (!flag) break;
      visit.insert(*now);
      for (set<string>::iterator it = road.begin(); it != road.end(); it++)
        if (con.count(MP(*it, *now)) && !visit.count(*it) && d[*now] + 1 < d[*it]) {
          d[*it] = d[*now] + 1;
          parent[*it] = *now;
        }
    }
    if (!road.count(s) || !road.count(e) || d[e] == 2e9)puts("No route");
    else print(parent, e);
  }
  return 0;
}

UVa 599 - The Forrest for the Trees


#include <stdio.h>

int i, num[26], team[26];

void u(int a, int b) {
  int t1 = team[a], t2 = team[b];
  for (i = 0; i < 26; i++)
    if (team[i] == t2) num[t1]++, num[t2]--, team[i] = t1;
}

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  while (n--) {
    char s[200] = {};
    for (i = 0; i < 26; i++)
      num[i] = 1, team[i] = i;
    while (gets(s) && s[0] != '*')
      u(s[1] - 'A', s[3] - 'A');
    char t[200] = {};
    gets(t);
    int check[26] = {}, tree = 0, acorn = 0;
    for (i = 0; t[i]; i += 2) {
      int now = team[t[i] - 'A'];
      if (!check[now]) {
        check[now] = 1;
        if (num[now] == 1) acorn++;
        else tree++;
      }
    }
    printf("There are %d tree(s) and %d acorn(s).\n", tree, acorn);
  }
  return 0;
}

UVa 336 - A Node Too Far


#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#include <set>
#define MP make_pair
using namespace std;
typedef pair<int, int> P;

int main() {
  int i, n, c = 1;
  while (scanf("%d", &n) && n) {
    map<int, vector<int> > road;
    set<int> number;
    while (n--) {
      int a, b;
      scanf("%d%d", &a, &b);
      number.insert(a);
      number.insert(b);
      road[a].push_back(b);
      road[b].push_back(a);
    }
    int s, l;
    while (scanf("%d%d", &s, &l) && s || l) {
      queue<P> q;
      set<int> visit;
      visit.insert(s);
      q.push(MP(s, 0));
      int ans = 0;
      while (!q.empty()) {
        int now = q.front().first, dis = q.front().second;
        q.pop();
        if (dis <= l) ans++;
        else break;
        for (i = 0; i < road[now].size(); i++) {
          int next = road[now][i];
          if (!visit.count(next)) {
            q.push(MP(next, dis + 1));
            visit.insert(next);
          }
        }
      }
      printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", c++, number.size() - ans, s, l);
    }
  }
  return 0;
}

2012年11月26日

UVa 10004 - Bicoloring


#include <cstdio>
#include <vector>

std::vector<int> v[210];
int flag, rec[210];

void dfs(int now, int c) {
  if (!flag) return;
  rec[now] = c;
  for (int i = 0; i < v[now].size(); i++)
    if (rec[v[now][i]] == -1) dfs(v[now][i], !c);
    else if (rec[v[now][i]] == c) flag = 0;
}

int main() {
  int n, m, c = 1;
  while (scanf("%d", &n) && n) {
    int a, b;
    for (a = 0; a <= n; a++) {
      v[a].clear();
      rec[a] = -1;
    }
    scanf("%d", &m);
    while (m--) {
      scanf("%d%d", &a, &b);
      v[a].push_back(b);
      v[b].push_back(a);
    }
    flag = 1;
    dfs(0, 0);
    if (flag) puts("BICOLORABLE.");
    else puts("NOT BICOLORABLE.");
  }
  return 0;
} 

2012年11月22日

UVa 10986 - Sending email


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

typedef pair<int, int> P;

int main() {
  int i, j, k, C, N;
  scanf("%d", &N);
  for (C = 1; C <= N; C++) {
    int n, m, S, T;
    scanf("%d%d%d%d", &n, &m, &S, &T);
    map<P, int> dis;
    vector<int> v[20005];
    for (i = 0; i < m; i++) {
      int a, b, w;
      scanf("%d%d%d", &a, &b, &w);
      dis[MP(a, b)] = dis[MP(b, a)] = w;
      v[a].push_back(b);
      v[b].push_back(a);
    }
    int d[20005];
    for (i = 0; i < n; i++)
      d[i] = 2e9;
    d[S] = 0;
    queue<int> q;
    q.push(S);
    while (!q.empty()) {
      int a = q.front(), b;
      q.pop();
      for (i = 0; i < v[a].size(); i++) {
        b = v[a][i];
        if (dis.count(MP(a, b))) {
          int w = dis[MP(a, b)];
          if (d[a] + w < d[b]) {
            d[b] = d[a] + w;
            q.push(b);
          }
        }
      }
    }
    printf("Case #%d: ", C);
    if (d[T] != 2e9) printf("%d\n", d[T]);
    else puts("unreachable");
  }
  return 0;
}

2012年11月21日

UVa 10801 - Lift Hopping


#include <stdio.h>

int main() {
  int n, i, j, k, E;
  while (scanf("%d %d", &n, &E) == 2) {
    getchar();
    int t[100];
    for (i = 0; i < n; i++) {
      scanf("%d", &t[i]);
      getchar();
    }
    int max[5] = {}, d[5][100], visit[5][100] = {}, ok[5][100] = {};
    for (i = 0; i < 5; i++)
      for (j = 0; j < 100; j++)
        d[i][j] = 1e9;
    for (i = 0; i < n; i++) {
      char temp[200];
      gets(temp);
      int sum = 0;
      for (j = 0; ; j++)
        if ('0' <= temp[j] && temp[j] <= '9') {
          sum = sum * 10 + temp[j] - '0';
        } else {
          ok[i][sum] = 1;
          max[i] = sum > max[i] ? sum : max[i];
          if (!sum) d[i][0] = 0;
          sum = 0;
          if (!temp[j]) break;
        }
    }
    int ans = -1;
    while (1) {
      int type = -1, h, min = 1e9;
      for (i = 0; i < n; i++)
        for (j = 0; j <= max[i]; j++)
        if (ok[i][j] && !visit[i][j] && d[i][j] < min) {
          min = d[i][j];
          type = i;
          h = j;
        }
        if (type == -1) break;
        if (h == E) {
          ans = min;
          break;
        }
        visit[type][h] = 1;
        for (i = 0; i < n; i++)
          for (j = 0; j <= max[i]; j++)
            if (ok[i][j] && !visit[i][j]) {
              int w = d[type][h] + t[i] * ((j - h) < 0 ? (h - j) : (j - h));
              if (i == type) {
                if (w < d[i][j]) d[i][j] = w;
              } else if (j == h) {
                if (w + 60 < d[i][j]) d[i][j] = w + 60;
              }
            }
    }
    if (ans != -1) printf("%d\n", ans);
    else puts("IMPOSSIBLE");
  }
  return 0;
}

2012年11月12日

UVa 314 - Robot


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

typedef pair<int, int> P;

int dr[] = {1, 0, -1, 0};
int dc[] = {0, 1, 0, -1};
int word[] = {'s', 'e', 'n', 'w'};
int r0, c0, r1, c1;

int BFS(int dir, set<P> ok) {
  int i;
  queue<pair<P, int> > q;
  map<pair<P, int>, int> visit;
  visit[MP(MP(r0, c0), dir)] = 0;
  q.push(MP(MP(r0, c0), dir));
  while (!q.empty()) {
    int r = q.front().first.first, c = q.front().first.second, dis = visit[q.front()];
    if (r == r1 && c == c1) return dis;
    int d = q.front().second, times;
    q.pop();
    P p;
    for (times = 1; times < 4; times++) {
      p = MP(r + dr[d] * times, c + dc[d] * times);
      if (!ok.count(p)) break;
      if (visit.count(MP(p, d))) continue;
      visit[MP(p, d)] = dis + 1;
      q.push(MP(p, d));
    }
    int left, right;
    right = (d + 1) % 4;
    p = MP(r, c);
    if (ok.count(p) && !visit.count(MP(p, right))) {
      visit[MP(p, right)] = dis + 1;
      q.push(MP(p, right));
    }
    left = (d + 4 - 1) % 4;
    if (!visit.count(MP(p, left))) {
      visit[MP(p, left)] = dis + 1;
      q.push(MP(p, left));
    }
  }
  return -1;
}

int main() {
  int i, j, r, c;
  while (scanf("%d%d", &r, &c) && r || c) {
    int grid[50][50];
    set<P> ok;
    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++) {
        scanf("%d", &grid[i][j]);
        if (!grid[i][j]) ok.insert(MP(i, j));
      }
    for (i = 0; i < r; i++)
      for (j = 0; j < c; j++)
        if (grid[i][j]) {
          ok.erase(MP(i, j));
          ok.erase(MP(i, j + 1));
          ok.erase(MP(i + 1, j));
          ok.erase(MP(i + 1, j + 1));
        }
    for (i = 0; i <= r; i++) {
      ok.erase(MP(i, 0));
      ok.erase(MP(i, c));
    }
    for (i = 0; i <= c; i++) {
      ok.erase(MP(0, i));
      ok.erase(MP(r, i));
    }
    char dir[20];
    scanf("%d%d%d%d%s", &r0, &c0, &r1, &c1, dir);
    if (!ok.count(MP(r1, c1))) {
      puts("-1");
      continue;
    }
    int d;
    for (d = 0; d < 4; d++)
      if (word[d] == dir[0]) break;
    printf("%d\n", BFS(d, ok));
  }
  return 0;
}

UVa 785 - Grid Colouring


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

typedef pair<int, int> P;

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

int main() {
  int n;
  char grid[100][100];
  while (gets(grid[0]) != NULL) {
    set<P> ok;
    map<P, int> visit;
    queue<pair<P, char> > start;
    int r, c, r0, c0;
    for (r = 1; ; r++) {
      gets(grid[r]);
      if (grid[r][0] == '_') break;
      for (c = 0; grid[r][c]; c++) {
        if (grid[r][c] != 'X') ok.insert(MP(r, c));
        if (grid[r][c] != 'X' && grid[r][c] != ' ') {
          ok.insert(MP(r, c));
          start.push(MP(MP(r, c), grid[r][c]));
        }
      }
    }
    while (!start.empty()) {
      queue<P> q;
      q.push(MP(start.front().first.first, start.front().first.second));
      char ch = start.front().second;
      while (!q.empty()) {
        int r = q.front().first, c = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
          P p = MP(r + dr[i], c + dc[i]);
          if (visit.count(p) || !ok.count(p)) continue;
          grid[r + dr[i]][c + dc[i]] = ch;
          q.push(p);
          visit[p] = 1;
        }
      }
      start.pop();
    }
    for (r = 0; ; r++) {
      puts(grid[r]);
      if (grid[r][0] == '_') break;
    }
  }
  return 0;
}

2012年10月21日

UVa 760 - DNA Sequencing


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

int main() {
  int first = 1;
  while (1) {
    if (!first) {
      char tmp[10];
      if (!gets(tmp)) break;
      puts("");
    }
    first = 0;
    char s1[310], s2[310];
    gets(s1 + 1);
    gets(s2 + 1);
    int i, j, lcs[310][310] = {}, N = 0, max = 0;
    for (i = 1; s1[i]; i++)
      for (j = 1; s2[j]; j++)
        if (s1[i] == s2[j]) {
          lcs[i][j] = lcs[i - 1][j - 1] + 1;
          if (lcs[i][j] > max) max = lcs[i][j];
        } else lcs[i][j] = 0;
    if (max < 1) {
      puts("No common sequence.");
      continue;
    }
    string ans[10000];
    int k = 0;
    for (i = 1; s1[i]; i++)
      for (j = 1; s2[j]; j++)
        if (lcs[i][j] == max)
          ans[k++] = string(s1 + i - max + 1, s1 + i + 1);
    sort(ans, ans + k);
    for (i = 0; i < k; i++)
      if (i && !(ans[i].compare(ans[i - 1]))) continue;
      else puts(ans[i].c_str());
  }
  return 0;
}

2012年10月20日

UVa 12241 - Digits Count


#include <stdio.h>

void cal(long long n, long long* num) {
  long long fac = 1;
  while (n / fac) {
    long long low = n - (n / fac) * fac, now = (n / fac) % 10, high = n / (fac * 10);
    int i;
    for (i = 0; i < 10; i++) {
      if (now < i) num[i] += high * fac;
      else if (now == i) num[i] += high * fac + low + 1;
      else if (now > i) num[i] += (high + 1) * fac;
    }
    fac *= 10;
  }
  while ((fac /= 10))
    num[0] -= fac;
}

int main() {
  int start, end;
  while (scanf("%d%d", &start, &end) && start || end) {
    long long ans[10] = {}, sub[10] = {};
    cal(start - 1, sub);
    cal(end, ans);
    int i;
    for (i = 0; i < 10; i++)
      printf("%lld%c", ans[i] - sub[i], i == 9 ? '\n' : ' ');
  }
  return 0;
}

2012年10月15日

UVa 112 - Tree Summing


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

int main() {
  int ans;
  while (scanf("%d", &ans) == 1) {
    int l = 0, r = 0, num = 0, sum = 0;
    stack<int> tree;
    char c, old[4] = {0};
    bool flag = 0, start = 0, neg = 0;
    while (!start || l != r) {
      c = getchar();
      switch (c) {
        case '(':
          l++;
          if (start && old[2] != ')') {
            if (neg) num *= -1;
            sum += num;
            tree.push(num);
            num = 0;
            neg = 0;
          }
          old[0] = old[1];
          old[1] = old[2];
          old[2] = c;
          start = 1;
          break;
        case ')':
          r++;
          if (old[2] != '(' && tree.size()) {
            sum -= tree.top();
            tree.pop();
          } else if (old[0] == '(' && old[1] == ')' && old[2] == '(' && sum == ans) {
            flag = 1;
          }
          old[0] = old[1];
          old[1] = old[2];
          old[2] = c;
          break;
        case '-':
          neg = 1;
        case ' ':
        case '\n':
          break;
        default:
          num = num * 10 + c - '0';
      }
    }
    if (flag) puts("yes");
    else puts("no");
  }
  return 0;
}

2012年10月11日

UVa 10344 - 23 out of 5


#include <cstdio>
#include <algorithm>

int num[12], flag;

void run(int sum, int times) {
  if (flag) return;
  if (times == 5) {
    if (sum == 23) flag = 1;
    return;
  }
  run(sum + num[times], times + 1);
  run(sum - num[times], times + 1);
  run(sum * num[times], times + 1);
}

int main() {
  while (scanf("%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &num[4])) {
    if (!num[0] && !num[1] && !num[2] && !num[3] && !num[4]) break;
    flag = 0;
    std::sort(num, num + 5);
    do {
      run(num[0], 1);
    } while (!flag && std::next_permutation(num, num + 5));
    if (flag) puts("Possible");
    else puts("Impossible");
  }
  return 0;
}

UVa 574 - Sum It Up


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

int num[12], flag, n;
map<string, int> dic;

void run(int sum, int times, int *check) {
  if (!sum) {
    flag = 1;
    int i;
    string s;
    for (i = n - 1; i >= 0; i--)
      if (check[i]) {
        char temp[10];
        sprintf(temp, "%d", num[i]);
        s.append(temp);
        break;
      }
    for (i--; i >= 0; i--)
      if (check[i]) {
        char temp[10];
        sprintf(temp, "+%d", num[i]);
        s.append(temp);
      }
    if (dic[s]) return;
    else dic[s] = 1;
    puts(s.c_str());
    return;
  }
  if (sum < 0 || times == -1) return;
  check[times] = 1;
  run(sum - num[times], times - 1, check);
  check[times] = 0;
  run(sum, times - 1, check);
}

int main() {
  int t;
  while (scanf("%d%d", &t, &n) && t || n) {
    dic.erase(dic.begin(), dic.end());
    for (int i = 0; i < n; i++)
      scanf("%d", &num[i]);
    flag = 0;
    std::sort(num, num + n);
    int check[12] = {};
    printf("Sums of %d:\n", t);
    run(t, n - 1, check);
    if (!flag) puts("NONE");
  }
  return 0;
}

300!

2012年10月6日

UVa 750 - 8 Queens Chess Problem


#include <stdio.h>

int times, R, C;

void run(int r, int *checkC, int *checkL, int *checkR, int *p) {
  if (r == 8) {
    printf("%2d     ", times++);
    int i, j;
    for (j = 0; j < 8; j++)
      printf(" %d", 8 - p[j]);
    puts("");
    return;
  }

  if (r == R) {
    p[R] = C;
    run(r + 1, checkC, checkL, checkR, p);
    return;
  }

  int c;
  for (c = 7; c >= 0; c--) {
    if (!checkC[c] && !checkL[r + c] && !checkR[r - c + 8]) {
      p[r] = c;
      checkC[c] = 1;
      checkL[r + c] = 1;
      checkR[r - c + 8] = 1;
      run(r + 1, checkC, checkL, checkR, p);
      checkC[c] = 0;
      checkL[r + c] = 0;
      checkR[r - c + 8] = 0;
    }
  }
}

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    times = 1;
    scanf("%d%d", &R, &C);
    puts("SOLN       COLUMN\n #      1 2 3 4 5 6 7 8\n");
    int checkC[8] = {}, checkL[16] = {}, checkR[16] = {}, p[8] = {};
    R--;
    C--;
    int tmp;
    tmp = R;
    R = C;
    C = tmp;
    C = 7 - C;
    checkC[C] = 1;
    checkL[R + C] = 1;
    checkR[R - C + 8] = 1;
    run(0, checkC, checkL, checkR, p);
    if (n) puts("");
  }
  return 0;
}

2012年9月20日

UVa 343 - What Base Is This?


#include <stdio.h>

int turn(char *s, int n) {
  int i, sum = 0;
  for (i = 0; s[i]; i++) {
    if ('0' <= s[i] && s[i] <= '9') {
      if ((s[i] - '0') >= n) return -1;
      sum = sum * n + s[i] - '0';
    } else {
      if ((s[i] - 'A' + 10) >= n) return -1;
      sum = sum * n + s[i] - 'A' + 10;
    }
  }
  return sum;
}
int main() {
  char a[200], b[200];
  while (scanf("%s%s", &a, &b) == 2) {
    int i, j, flag = 0;;
    for (i = 2; i < 37; i++) {
      if (turn(a, i) == -1) continue;
      for (j = 2; j < 37; j++)
        if (turn(a, i) == turn(b, j)) {
          printf("%s (base %d) = %s (base %d)\n", a, i, b, j);
          flag = 1;
          i = 37;
          j = 37;
        }
    }
    if (!flag) printf("%s is not equal to %s in any base 2..36\n", a, b);
  }
  return 0;
}

2012年9月14日

200!


UVa 484 - The Department of Redundancy Department


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

struct link {
  int n;
  link *next;
};

int main() {
  int n, I = 0;
  map<int, int> form;
  link *head = NULL;
  link *current = NULL;
  link *prev = NULL;
  while (scanf("%d", &n) == 1) {
    form[n]++;
    if (form[n] == 1) {
      current = new link;
      current -> n = n;
      current -> next = NULL;
      if (head == NULL)
        head = current;
      else
        prev -> next = current;
      prev = current;
    }
  }

  current = head;
  while (current != NULL) {
    printf("%d %d\n", current -> n, form[current -> n]);
    current = current -> next;
  }
  return 0;
}

UVa 397 - Equation Elation

Suck problem...
#include <cstdio>
#include <string>
#include <vector>
using std::string;
using std::vector;

class C {
public:
  C (int value, int start, int end) {
    this -> value = value;
    this -> start = start;
    this -> end = end;
  }
  int value, start, end;
};

void handle(string &s) {
  for (int i = 0, cmd = 0; s[i]; i++) {
    if ('0' <= s[i] && s[i] <= '9') {
      cmd = 0;
      if (s[i + 1] != ' ' && (s[i + 1] < '0' || s[i + 1] > '9'))
        s.insert(s.begin() + ++i, ' ');
    } else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
      if (cmd) {
        if (s[i] == '+') 
          s.erase(s.begin() + i--);
        cmd = 0;
      } else {
        cmd = s[i];
        if (s[i + 1] != ' ')
          s.insert(s.begin() + ++i, ' ');
      }
    } else if (s[i] == '=') {
      if (s[i + 1] != ' ') 
        s.insert(s.begin() + ++i, ' ');
      break;
    }
  }
  puts(s.c_str());
}

void cal(C a, C b, char op, string &s) {
  int n1 = a.value;
  int i1 = a.start - (n1 < 0);
  int n2 = b.value;
  int i2 = b.end;
  int n;
  char N[100];
  switch (op) {
  case '+':
    n = n1 + n2;
    break;
  case '-':
    n = n1 - n2;
    break;
  case '*':
    n = n1 * n2;
    break;
  case '/':
    n = n1 / n2;
    break;
  }
  sprintf(N, "%d", n);
  s.erase(s.begin() + i1, s.begin() + i2 + 1);
  s.insert(i1, N);
  puts(s.c_str());
}

int main() {
  int first = 1;
  char str[1000];
  while (gets(str)) {
    if (!first)
      puts("");
    first = 0;
    string s(str);
    handle(s);
    vector<C> num, op;
    int cmd = 0, tmp = 0, start = 0, end = 0, neg = 0;;
    for (int i = 0; s[i]; i++) {
      if ('0' <= s[i] && s[i] <= '9') {
        if (!i || (s[i - 1] < '0' || s[i - 1] > '9')) 
          start = i;
        end = i;
        tmp = tmp * 10 + s[i] - '0';
      } else if (s[i] == '+' || s[i] == '-') {
        if (s[i] == '-' && '0' <= s[i + 1] && s[i + 1] <= '9') {
          neg = 1;
        } else {
          op.push_back(C(s[i], i, i));
          tmp = 0;
        }
      } else if (s[i] == '*' || s[i] == '/') {
        op.push_back(C(s[i], i, i));
        cmd = s[i];
        tmp = 0;
      } else if (s[i] == ' ') {
        if (neg) {
          tmp *= -1;
          neg = 0;
        }
        if ('0' <= s[i - 1] && s[i - 1] <= '9')
          num.push_back(C(tmp, start, end));
        tmp = 0;
        start = 0;
        end = 0;
        if (num.size() > 1 && (num.back().start > op.back().end) && (op.back().value == '*' || op.back().value == '/')) {
          cal(num[num.size() - 2], num[num.size() - 1], op.back().value, s);
          num.erase(num.begin(), num.end());
          op.erase(op.begin(), op.end());
          i = -1;
          continue;
        }
      } else if (s[i] == '=') {
        if (!op.size() && num.size() <= 1) 
          break;
        cal(num[0], num[1], op[0].value, s);
        num.erase(num.begin(), num.end());
        op.erase(op.begin(), op.end());
        i = -1;
        continue;
      }
    }
  }
  return 0;
}

UVa 640 - Self Numbers


#include <stdio.h>

int generator(int n) {
  int sum = n;
  while (n) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
int main() {
  int *x = malloc(1000001 * sizeof(int));
  int i, n = 1;
  for (i = 1; i <= 1000000; i++)
    x[i] = 0;
  for (i = 1; i <= 1000000; i++) {
    n = generator(i);
    if (n <= 1000000)
      x[n] = 1;
  }
  for (i = 1; i <= 1000000; i++)
    if (!x[i]) printf("%d\n", i);
  free(x);
  return 0;
}

2012年9月13日

UVa 195 - Anagram


#include <cstdio>
#include <algorithm>

int main() {
  int n;
  scanf("%d", &n);
  getchar();
  while (n--) {
    char s[1000];
    gets(s);
    int l, nS[1000];
    for (l = 0; s[l]; l++)
      if (s[l] >= 'a') nS[l] = (s[l] - 'a') * 2 + 1;
      else nS[l] = (s[l] - 'A') * 2;
    std::sort(nS, nS + l);
    do {
      for (l = 0; s[l]; l++)
        if (nS[l] % 2 == 0) putchar(nS[l] / 2 + 'A');
        else putchar(nS[l] / 2 + 'a');
      puts("");
    } while (std::next_permutation(nS, nS + l));
  }
  return 0;
}

UVa 146 - ID Codes

lol
#include <cstdio>
#include <cstring>
#include <algorithm>

int main() {
  char s[100];
  while (gets(s) && s[0] != '#') {
    if (std::next_permutation(s, s + strlen(s))) {
      puts(s);
    } else {
      puts("No Successor");
    }
  }
  return 0;
}

2012年9月12日

UVa 127 - "Accordian" Patience


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

class Card {
public:
  Card(char suit, char value) {
    this -> suit = suit;
    this -> value = value;
  }
  char suit;
  char value;
};

int match(Card a, Card b) {
  if (a.suit == b.suit) return 1;
  if (a.value == b.value) return 1;
  return 0;
}

int main() {
  char cmd;
  while ((cmd = getchar()) && cmd != '#') {
    vector<vector<Card> > pile(52);
    for (int i = 0; i < 52; i++) {
      char value, suit;
      if (!i) value = cmd;
      else value = getchar();
      suit = getchar();
      pile[i].push_back(Card(suit, value));
      getchar();
    }
    for (int i = 1; i < pile.size(); i++) {
      while ((i && match(pile[i].back(), pile[i - 1].back())) || (i > 2 && match(pile[i].back(), pile[i - 3].back()))) {
        if (i > 2 && match(pile[i].back(), pile[i - 3].back())) pile[i - 3].push_back(pile[i].back());
        else pile[i - 1].push_back(pile[i].back());
        pile[i].pop_back();
        if (!pile[i].size()) pile.erase(pile.begin() + i);
        i = 0;
      }
    }
    if (pile.size() == 1) {
      puts("1 pile remaining: 52");
      continue;
    }
    printf("%d piles remaining:", pile.size());
    for (int i = 0; i < pile.size(); i++)
      printf(" %d", pile[i].size());
    puts("");
  }
  return 0;
}

2012年9月9日

UVa 307 - Sticks


I hate this problem...
#include <cstdio>
#include <algorithm>

int n, num[200], len, sides, found, ans;
bool check[200];

bool cmp(int a, int b) {
  return a > b;
}

void find(int sum, int now, int times) {
  if (times == (sides - 1)) {
    found = 1;
    return;
  }
  if (found) return;
  int i;
  for (i = now; i < n; i++) {
    if (check[i] || (sum + num[i]) > len) continue;
    if (i && num[i] == num[i - 1] && !check[i - 1]) continue;
    if (sum + num[i] == len) {
      check[i] = 1;
      find(0, 0, times + 1);
      check[i] = 0;
      return;
    } else if (sum + num[i] < len) {
      check[i] = 1;
      find(sum + num[i], i + 1, times);
      check[i] = 0;
      if (sum == 0) return;
      if (num[i] == sum - len) return;
    }
  }
}

int main() {
  while (scanf("%d", &n) && n) {
    int i, sum = 0;
    for (i = 0; i < n; i++) {
      scanf("%d", &num[i]);
      sum += num[i];
    }
    std::sort(num, num + n, cmp);
    found = 0;
    ans = 0;
    if (num[0] == num[n - 1]) {
      ans = num[0];
    } else {
      ans = sum;
      for (len = num[0]; len <= sum / 2; len++) {
        if (sum % len) continue;
        for (i = 0; i < n; i++) check[i] = 0;
        sides = sum / len;
        find(0, 0, 0);
        if (found) {
          ans = len;
          break;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

2012年9月8日

UVa 10023 - Square root


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

public class Main {
  public static int lowSqrt(int n) {
    int i;
    for (i = 10; i >= 0; i--)
      if ((i * i) <= n) break;
    return i;
  }

  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    while (n > 0) {
      n--;
      String s = cin.next();
      int i;
      BigInteger tmp, cal;
      if (s.length() % 2 == 1) tmp = BigInteger.valueOf(s.charAt(0) - '0');
      else tmp = BigInteger.valueOf((s.charAt(0) - '0') * 10 + s.charAt(1) - '0');
      cal = BigInteger.valueOf(lowSqrt(tmp.intValue()));
      tmp = tmp.subtract(cal.multiply(cal));
      System.out.print(cal);
      cal = cal.add(cal);
      for (i = 2 - (s.length() % 2); i < s.length(); i += 2) {
        tmp = tmp.multiply(BigInteger.valueOf(100)).add(BigInteger.valueOf((s.charAt(i) - '0') * 10 + s.charAt(i + 1) - '0'));
        int run;
        BigInteger temp = BigInteger.valueOf(0);
        for (run = 9; run >= 0; run--) {
          temp = cal.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(run)).multiply(BigInteger.valueOf(run));
          if (temp.compareTo(tmp) <= 0) {
            tmp = tmp.subtract(temp);
            cal = cal.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(run * 2));
            break;
          }
        }
        System.out.print(run);
      }
      System.out.println("");
      if (n > 0) System.out.println("");
    }
  }
}

2012年9月7日

UVa 133 - The Dole Queue


#include <stdio.h>

int main() {
  int n, k, m;
  while (scanf("%d%d%d", &n, &k, &m) && n) {
    int people = 0, times = 0, left = 0, right = n + 1, p[21] = {0};
    while (people < n) {
      int L = k, R = m;
      if (L > (n - people)) L %= (n - people);
      if (R > (n - people)) R %= (n - people);
      if (!L) L = n - people;
      if (!R) R = n - people;
      for (; L; L--) {
        left++;
        if (left > n) left -= n;
        while (p[left]) {
          left++;
          if (left > n) left -= n;
        }
      }
      for (; R; R--) {
        right--;
        if (!right) right += n;
        while (p[right]) {
          right--;
          if (!right) right += n;
        }
      }
      times += 2;
      people += 2;
      printf("%3d", left);
      if (right != left) printf("%3d", right);
      else people--;
      if (!(times % 2) && people < n) printf(",");
      p[left] = 1;
      p[right] = 1;
    }
    puts("");
  }
  return 0;
}

2012年9月6日

UVa 12397 - Roman Numerals


#include <stdio.h>
 
int main() {
  int i, n, num[4000];
  for (i = 0; i < 4000; i++) {
    num[i] = 0;
    n = i;
    if ((n % 1000) >= 900) n += 200;
    if ((n % 1000) <= 499 && (n % 1000) >= 400) n += 200;
    if ((n % 100) <= 49 && (n % 100) >= 40) n += 20;
    if ((n % 100) >= 90) n += 20;
    if (n % 10 == 4 || n % 10 == 9) n += 2;
    num[i] += (n / 1000) * 4;
    n %= 1000;
    num[i] += (n / 500) * 3;
    n %= 500;
    num[i] += (n / 100) * 2;
    n %= 100;
    num[i] += (n / 50) * 2;
    n %= 50;
    num[i] += (n / 10) * 2;
    n %= 10;
    num[i] += (n / 5) * 2;
    n %= 5;
    num[i] += n;
  }
  while (scanf("%d", &n) == 1)
    printf("%d\n", num[n]);
  return 0;
}

UVa 103 - Stacking Boxes


#include <stdio.h>
#include <stdlib.h>

typedef struct Box Box;

struct Box {
  int index;
  int num[10];
};

int big(Box a, Box b, int s) {
  int i;
  for (i = 0; i < s; i++)
    if (a.num[i] <= b.num[i]) return 0;
  return 1;
};

int cmpInt(const void* a, const void* b) {
  return *(int *)a - *(int *)b;
};

int cmpBox(const void* a, const void* b) {
  return (*(Box *)a).num[0] - (*(Box *)b).num[0];
};

void print(int pos, int* prev, Box* box, int ans) {
  if (prev[pos] != -1) print(prev[pos], prev, box, ans - 1);
  printf("%d", box[pos].index);
  if (ans) printf(" ");
}

int main() {
  int i, j, n, m;
  while (scanf("%d%d", &n, &m) == 2) {
    Box *box = malloc(n * sizeof(Box));
    for (i = 0; i < n; i++) {
      box[i].index = i + 1;
      for (j = 0; j < m; j++)
        scanf("%d", &box[i].num[j]);
      qsort(box[i].num, m, sizeof(int), cmpInt);
    }
    qsort(box, n, sizeof(Box), cmpBox);
    int *dp = malloc(n * sizeof(int)), *prev = malloc(n * sizeof(int));
    for (i = 0; i < n; i++) {
      dp[i] = 1;
      prev[i] = -1;
    }
    for (i = 0; i < n; i++)
      for (j = i + 1; j < n; j++)
        if (big(box[j], box[i], m))
          if (dp[i] + 1 > dp[j]) {
            dp[j] = dp[i] + 1;
            prev[j] = i;
          }
    int ans = 0, pos = 0;
    for (i = 0; i < n; i++)
      if (dp[i] > ans) {
        ans = dp[i];
        pos = i;
      }
    printf("%d\n", ans);
    print(pos, prev, box, ans);
    puts("");
  }
  return 0;
}

2012年9月5日

UVa 10066 - The Twin Towers


#include <cstdio>

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

int main() {
  int m, n, c = 1;
  while (scanf("%d%d", &m, &n) && m || n) {
    int i, j, a[101], b[101], dp[101][101] = {0};
    for (i = 1; i <= m; i++)
      scanf("%d", &a[i]);
    for (i = 1; i <= n; i++)
      scanf("%d", &b[i]);
    for (i = 1; i <= m; i++)
      for (j = 1; j <= n; j++)
        if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
        else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    printf("Twin Towers #%d\nNumber of Tiles : %d\n\n", c++, dp[m][n]);
  }
  return 0;
}

UVa 344 - Roman Digititis


#include <stdio.h>

typedef struct Num Num;

struct Num {
  int i, v, x, l, c;
};

int main() {
  int i, n;
  Num num[101], ans[101];
  for (i = 0; i <= 100; i++) {
    n = i;
    if (n <= 49 && n >= 40) n += 20;
    if (n >= 90) n += 20;
    if (n % 10 == 4 || n % 10 == 9) n += 2;
    num[i].c = n / 100;
    n %= 100;
    num[i].l = n / 50;
    n %= 50;
    num[i].x = n / 10;
    n %= 10;
    num[i].v = n / 5;
    n %= 5;
    num[i].i = n;
  }
  ans[0].c = 0;
  ans[0].l = 0;
  ans[0].x = 0;
  ans[0].v = 0;
  ans[0].i = 0;
  for (i = 1; i <= 100; i++) {
    ans[i].c = num[i].c + ans[i - 1].c;
    ans[i].l = num[i].l + ans[i - 1].l;
    ans[i].x = num[i].x + ans[i - 1].x;
    ans[i].v = num[i].v + ans[i - 1].v;
    ans[i].i = num[i].i + ans[i - 1].i;
  }
  while (scanf("%d", &n) && n) {
    printf("%d:", n);
    printf(" %d i, %d v, %d x, %d l, %d c\n", ans[n].i, ans[n].v, ans[n].x, ans[n].l, ans[n].c);
  }
  return 0;
}

2012年9月4日

UVa 108 - Maximum Sum


#include <stdio.h>

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int i, j, map[150][150], cal[150][150];
    for (i = 1; i <= n; i++)
      for (j = 1;j <= n; j++)
        scanf("%d", &map[i][j]);
    for (i = 0; i <= n; i++) {
      cal[i][0] = 0;
      cal[0][i] = 0;
    }
    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++)
        cal[i][j] = cal[i - 1][j] + cal[i][j - 1] - cal[i - 1][j - 1] + map[i][j];
    int a, c, start, all, ans = 0;
    for (a = 1; a <= n; a++)
      for (c = a; c <= n; c++) {
        start = cal[c][n] - cal[a - 1][n] - cal[c][n - 1] + cal[a - 1][n - 1];
        all = start;
        for (i = n - 1; i >= 1; i--) {
          if (start < 0) start = 0;
          start += (cal[c][i] - cal[a - 1][i] - cal[c][i - 1] + cal[a - 1][i - 1]);
          if (start > all) all = start;
        }
        if (all > ans) ans = all;
      }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 498 - Polly the Polynomial


#include <stdio.h>

int main() {
  char s[10000];
  while (gets(s) != NULL) {
    int i, j, l, n = 0, times = 0, cal = 0, c[10000];
    for (l = 0; ; l++) {
      if (s[l] == ' ' || !s[l]) {
        if (n) cal *= -1;
        c[times++] = cal;
        n = 0;
        cal = 0;
        if (!s[l]) break;
      } else if (s[l] == '-') {
        n = 1;
      } else {
        cal = cal * 10 + s[l] - '0';
      }
    }
    gets(s);
    int x = 0, first = 0, sum = 0, temp;
    for (l = 0; ; l++) {
      if (s[l] == ' ' || !s[l]) {
        if (first) printf(" ");
        first = 1;
        if (n) x *= -1;
        sum = 0;
        for (i = 0; i < times; i++) {
          temp = c[i];
          for (j = 0; j < (times - 1 - i); j++)
            temp *= x;
          sum += temp;
        }
        printf("%d", sum);
        x = 0;
        n = 0;
        if (!s[l]) break;
      } else if (s[l] == '-') {
        n = 1;
      } else {
        x = x * 10 + s[l] - '0';
      }
    }
    puts("");
  }
  return 0;
}

2012年8月30日

UVa 10037 - Bridge

Reference : http://www.csie.ntnu.edu.tw/~u91029/Greedy.html#4
#include <cstdio>
#include <algorithm>

int main() {
  int i, n, c, num[1001];
  scanf("%d", &c);
  while (c--) {
    scanf("%d", &n);
    for (i = 0; i < n; i++)
      scanf("%d", &num[i]);
    std::sort(num, num + n);
    int t = 0, t1, t2, rec = n;
    
    for (n--; n >= 3; n -= 2) {
      t1 = num[0] + num[1] * 2 + num[n];
      t2 = num[0] * 2 + num[n - 1] + num[n];
      if (t1 < t2) t += t1;
      else t += t2;
    }

    if (n == 2) t += num[0] + num[1] + num[2];
    else if (n == 1) t += num[1];
    else t += num[0];
    printf("%d\n", t);

    n = rec;

    for (n--; n >= 3; n -= 2) {
      t1 = num[0] + num[1] * 2 + num[n];
      t2 = num[0] * 2 + num[n - 1] + num[n];
      if (t1 < t2) printf("%d %d\n%d\n%d %d\n%d\n", num[0], num[1], num[0], num[n - 1], num[n], num[1]);
      else printf("%d %d\n%d\n%d %d\n%d\n", num[0], num[n], num[0], num[0], num[n - 1], num[0]);
    }

    if (n == 2) printf("%d %d\n%d\n%d %d\n", num[0], num[1], num[0], num[0], num[2]);
    else if (n == 1) printf("%d %d\n", num[0], num[1]);
    else printf("%d\n", num[0]);
    if (c) puts("");
  }
  return 0;
}

2012年8月25日

UVa 111 - History Grading


It's hard to understand the meaning of this problem by my poor English.
#include <stdio.h>

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

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int i, j, tmp, a[50], b[50], array[50][50];
    for (i = 1; i <= n; i++) {
      scanf("%d", &tmp);
      a[tmp] = i;
    }
    while (scanf("%d", &tmp) == 1) {
      b[tmp] = 1;
      for (i = 2; i <= n; i++) {
        scanf("%d", &tmp);
        b[tmp] = i;
      }
      for (i = 0; i <= n; i++)
        for (j = 0; j <= n; j++)
          array[i][j] = 0;
      for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
          if (a[i] == b[j]) array[i][j] = array[i - 1][j - 1] + 1;
          else array[i][j] = max(array[i - 1][j], array[i][j - 1]);
      printf("%d\n", array[n][n]);
    }
  }
  return 0;
}

2012年8月24日

UVa 729 - The Hamming Distance Problem


Practice to use next_permutation!
#include <stdio.h>
#include <algorithm>

using std::next_permutation;

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int i, n, h;
    scanf("%d%d", &n, &h);
    int *num = new int[n];
    for (i = 0; i < n - h; i++)
      num[i] = 0;
    for (; i < n; i++)
      num[i] = 1;

    do {
      for (i = 0; i < n; i++)
        printf("%d", num[i]);
      puts("");
    } while (next_permutation(num, num + n));
    if (t) puts("");
    delete[] num;
  }
  return 0;
}

UVa 353 - Pesky Palindromes


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

int N;
char all[100][1000];

int pal(char* tmp, int min, int max) {
  int i, l = max - min, flag = 1;
  for (i = min; i <= min + l / 2; i++)
    if (tmp[i] != tmp[max - i + min]) {
      flag = 0;
      break;
    }
  char temp[100];
  for (i = 0; i < l; i++)
    temp[i] = tmp[i + min];
  temp[i] = '\0';
  for (i = 0; i < N; i++)
    if (!strcmp(all[i], temp)) {
      flag = 0;
      break;
    }
  if (flag == 1) strcpy(all[N++], temp);
  return flag;
}

int main() {
  char tmp[100];
  while (scanf("%s", &tmp) == 1) {
    N = 0;
    int i, j, asc[129] = {0}, times = 0;
    for (i = 0; tmp[i]; i++) {
      if (!asc[tmp[i]]) {
        asc[tmp[i]] = 1;
        times++;
      }
      for (j = i + 1; tmp[j]; j++)
        if (i != j && pal(tmp, i, j)) times++;
    }
    printf("The string '%s' contains %d palindromes.\n", tmp, times);
  }
  return 0;
}

UVa 11466 - Largest Prime Divisor

Critical point : n should have more than one prime divisors.
For example : 16 : 2*2*2*2 , should print -1!

#include <stdio.h>
#include <math.h>
#define S 10000000

bool *prime = new bool[S];
int N = 0;
int *p = new int[664600];
void build() {
  long long int i, j, k, s = sqrt(S);
  prime[0] = true;
  prime[1] = true;
  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] = true;
  for (i = 0; i < S; i++)
    if (!prime[i]) p[N++] = i;
}

int main() {
  build();
  long long int n, max, tmp;
  while (scanf("%lld", &n) && n) {
    int i, times = 0;
    if (n < 0) n *= -1;
    tmp = n;
    max = -1;
    for (i = 0; i < N && n != 1; i++) {
      if (!(n % p[i]) && p[i] != tmp) {
        times++;
        while (!(n % p[i])) {
          n /= p[i];
          if (n == 1 && times > 1) {
            max = p[i];
            break;
          }
        }
      }
    }
    if (n != 1 && n != tmp) max = n;
    printf("%lld\n", max);
  }
  delete[] prime;
  delete[] p;
  return 0;
}

2012年8月23日

UVa 537 - Artificial Intelligence?

#include <stdio.h>

int main() {
  int i, c, n;
  scanf("%d%*c", &n);
  for (c = 1; c <= n; c++) {
    printf("Problem #%d\n", c);
    double U = -1, I = -1, P = -1;
    char tmp[20000];
    for (i = 0; ; i++) {
      tmp[i] = getchar();
      if (tmp[i] == '\n') break;
      if (tmp[i] == '=') {
        switch (tmp[i - 1]) {
        case 'U':
          U = 0;
          scanf("%lf", &U);
          tmp[i] = getchar();
          if (tmp[i] == 'm') U *= 0.001;
          else if (tmp[i] == 'k') U *= 1000.0;
          else if (tmp[i] == 'M') U *= 1000000.0;
          break;
        case 'P':
          P = 0;
          scanf("%lf", &P);
          tmp[i] = getchar();
          if (tmp[i] == 'm') P *= 0.001;
          else if (tmp[i] == 'k') P *= 1000.0;
          else if (tmp[i] == 'M') P *= 1000000.0;
          break;
        case 'I':
          I = 0;
          scanf("%lf", &I);
          tmp[i] = getchar();
          if (tmp[i] == 'm') I *= 0.001;
          else if (tmp[i] == 'k') I *= 1000.0;
          else if (tmp[i] == 'M') I *= 1000000.0;
          break;
        }
      }
    }
    if (P == -1) printf("P=%.2lfW", U * I);
    else if (I == -1) printf("I=%.2lfA", P / U);
    else printf("U=%.2lfV", P / I);
    puts("");
    puts("");
  }
  return 0;
}

UVa 748 - Exponentiation

It will be easy by using Java!

import java.math.BigDecimal;
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner cin = new Scanner(System.in);
    while (cin.hasNext()) {
      BigDecimal a = cin.nextBigDecimal();
      int e = cin.nextInt();
      a = a.pow(e);
      char[] s = a.toPlainString().toCharArray();
      int l, flag = 0;
      if (s[0] == '0') flag = 1;
      for (l = s.length; l >= 0; l--)
        if (s[l - 1] != '0') break;
      for (int i = flag; i < l; i++)
        System.out.print(s[i]);
      System.out.println("");
    }
  }
}

UVa 495 - Fibonacci Freeze


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

string add(string a, string b) { 
  string answer;
  int carry = 0, temp;
  int digit, digitA, digitB;
  digitA = a.length();
  digitB = b.length();;
  digit = digitA > digitB ? digitA : digitB;
  while (digit > 0) {
    temp = carry;
    if (--digitA >= 0) temp += a[digitA] - '0';
    if(--digitB >= 0) temp += b[digitB] - '0';
    carry = temp / 10;
    temp %= 10;
    answer.insert(answer.begin(), temp + '0');
    --digit;
  }
  if (carry) answer.insert(answer.begin(), carry + '0');
  return answer;
}

int main() {
  int i, n;
  string num[5001];
  num[0] = "0";
  num[1] = "1";
  for (i = 2; i < 5001; i++)
    num[i] = add(num[i - 1], num[i - 2]);
  while (scanf("%d", &n) == 1)
    printf("The Fibonacci number for %d is %s\n", n, num[n].c_str());
  return 0;
}

2012年8月22日

UVa 489 - Hangman Judge

There's a trap, round = n you input, not times!

#include <stdio.h>

int main() {
  int n;
  while (scanf("%d", &n) && n > 0) {
    char q[20], a[20];
    int i, asc[129] = {0}, max = 0, line = 0;
    scanf("%s", &q);
    for (i = 0; q[i]; i++) {
      if (!asc[q[i]]) max++;
      asc[q[i]] = 1;
    }
    scanf("%s", &a);
    for (i = 0; a[i]; i++)
      if (!asc[a[i]]) {
        asc[a[i]] = 2;
        line++;
        if (line == 7) break;
      } else if (asc[a[i]] == 1) {
        max--;
        asc[a[i]] = 2;
        if (max == 0) break;
      }
    printf("Round %d\n", n);
    if (!max) puts("You win.");
    else if (line == 7) puts("You lose.");
    else puts("You chickened out.");
  }
  return 0;
}

UVa 492 - Pig-Latin


#include <stdio.h>

int main() {
  char c;
  int flag = 0, remove = 0, word = 0;
  while (scanf("%c", &c) == 1) {
    if (!flag) {
      if (isalpha(c)) {
        flag = 1;
        if (c != 'a' && c != 'A' && c != 'e' && c != 'E' && c != 'i' && c != 'I' && c != 'o' && c != 'O' && c != 'u' && c != 'U') {
          remove = c;
          continue;
        } else remove = 0;
      }
    }
    if (!isalpha(c)) {
      if (flag) {
        if (remove) putchar(remove);
        printf("ay");
      }
      remove = 0;
      flag = 0;
    }
    putchar(c);
  }
  return 0;
}

2012年8月21日

UVa 160 - Factors and Factorials

A prime problem.

#include <stdio.h>

int p = 0, prime[110];

void build() {
  int i, j, tmp[110];
  for (i = 0; i < 110; i++)
    tmp[i] = 1;
  tmp[0] = 0;
  tmp[1] = 0;
  for (i = 2; i < 110; i++)
    if (tmp[i])
      for (j = i * i; j < 110; j += i)
        tmp[j] = 0;
  for (i = 0; i < 110; i++)
    if (tmp[i]) prime[p++] = i;
}

int main() {
  build();
  int i, j, n;
  while (scanf("%d", &n) && n) {
    int tmp, pNum[110] = {0};
    printf("%3d! =", n);
    for (i = n; i >= 2; i--) {
      tmp = i;
      for (j = 0; tmp > 1; j++)
        while (!(tmp % prime[j])) {
          pNum[j]++;
          tmp /= prime[j];
        }
    }
    for (i = 0; pNum[i]; i++) {
      if (i && !(i % 15)) printf("\n      ");
      printf("%3d", pNum[i]);
    }
    puts("");
  }
  return 0;
}

UVa 119 - Greedy Gift Givers


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

typedef struct People People;

struct People {
  char name[20];
  int money;
};

int main() {
  int i, j, n, first = 0;
  while (scanf("%d\n", &n) == 1) {
    if (first)
      puts("");
    first = 1;
    People people[20];
    for (i = 0; i < n; i++) {
      scanf("%s", &people[i].name);
      people[i].money = 0;
    }
    getchar();
    for (i = 0; i < n; i++) {
      int money, Money, num;
      char name[20];
      scanf("%s %d %d", &name, &Money, &num);
      getchar();
      if (num) {
        for (j = 0; j < n; j++)
          if (!strcmp(people[j].name, name)) break;
        money = Money / num;
        people[j].money -= money * num;
      }
      while (num--) {
        scanf("%s", &name);
        for (j = 0; j < n; j++)
          if (!strcmp(people[j].name, name)) break;
        people[j].money += money;
      }
    }
    for (i = 0; i < n; i++)
      printf("%s %d\n", people[i].name, people[i].money);
  }
  return 0;
}

100!



UVa 11547 - Automatic Answer

It took me a while to know the meaning of this problem!

#include <stdio.h>

int main() {
  int t, n;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    int ans = ((n * 63 + 7492) * 5 - 498) % 100 / 10;
    printf("%d\n", ans < 0 ? -1 * ans : ans);
  }
  return 0;
}

2012年8月20日

UVa 612 - DNA Sorting

#include <stdio.h>
#include <stdlib.h>

typedef struct Value Value;
struct Value{
  int index;
  int meansure;
};

int cmp (const void *a, const void *b) {
  return ((Value*)a) -> meansure - ((Value *)b) -> meansure;
}

int main() {
  int t;
  scanf("%d", &t);
  getchar();
  while (t--) {
    char map[110][110];
    Value v[110];
    int i, j, k, n, m, tmp;
    scanf("%d%d", &n, &m);
    getchar();
    for (i = 0; i < m; i++) {
      v[i].index = i;
      gets(map[i]);
    }
    for (i = 0; i < m; i++) {
      tmp = 0;
      for (j = 0; j < n; j++)
        for (k = j + 1; k < n; k++)
          if (map[i][j] > map[i][k]) tmp++;
      v[i].meansure = tmp;
    }
    qsort(v, m, sizeof(Value), cmp);
    for (i = 0; i < m; i++)
      puts(map[v[i].index]);
    if (t)
      puts("");
  }
  return 0;
}

UVa 706 - LCD Display


#include <stdio.h>
void display(int n, int t, int type) {
  int i, j;
  switch (type) {
  case 1:
    putchar(' ');
    for (i = 0; i < t; i++)
      printf("%c", (n == 1 || n == 4) ? ' ' :  '-');
    putchar(' ');
    break;
  case 2:
    if (n == 1 || n == 2 || n == 3 || n == 7) putchar(' ');
    else putchar('|');
    for (i = 0; i < t; i++)
      putchar(' ');
    printf("%c", (n == 5 || n == 6) ? ' ' :  '|');
    break;
  case 3:
    putchar(' ');
    for (i = 0; i < t; i++)
      printf("%c", (n == 1 || n == 7 || n == 0) ? ' ' :  '-');
    putchar(' ');
    break;
  case 4:
    if (n == 1 || n == 3 || n == 4 || n == 5 || n == 7 || n == 9) putchar(' ');
    else putchar('|');
    for (i = 0; i < t; i++)
      putchar(' ');
    printf("%c", (n == 2) ? ' ' :  '|');
    break;
  case 5:
    putchar(' ');
    for (i = 0; i < t; i++)
      printf("%c", (n == 1 || n == 4 || n == 7) ? ' ' :  '-');
    putchar(' ');
    break;
  }
}
int main() {
  int i, j, k, n, times, type;
  while (scanf("%d %d", ×, &n) && times || n) {
    char num[20];
    sprintf(num, "%d", n);
    for (type = 1; type <= 5; type++) {
      if (type == 2 || type == 4) k = times;
      else k = 1;
      while (k--) {
        for (i = 0; num[i] != '\0'; i++) {
          if (i) putchar(' ');
          display(num[i] - '0', times, type);
        }
        puts("");
      }
    }
    puts("");
  }
  return 0;
}

UVa 106 - Fermat vs. Pythagoras

We have to know a formula before doing this problem.
This problem will be very easy by using this formula!

#include <stdio.h>

int gcd (int a, int b) {
  while ((a %= b) && (b %= a));
  return a + b;
}

int main() {
  int n;
  while (scanf("%d", &n) == 1) {
    int i, j, ans = 0, part = 0;
    bool *have = new bool[n + 1];
    for (i = 0; i <= n; i++)
      have[i] = 0;
    for (i = 1; i * i < n; i++) {
      for (j = i + 1; (i * i + j * j) <= n; j += 2) {
        if (gcd(i, j) != 1) continue;
        int a = 2 * j * i, b = j * j - i * i, c = j * j + i * i;
        ans++;
        int A = a, B = b, C = c;
        while (C <= n) {
          if (!have[A]) part++;
          if (!have[B]) part++;
          if (!have[C]) part++;
          have[A] = 1;
          have[B] = 1;
          have[C] = 1;
          A += a;
          B += b;
          C += c;
        }
      }
    }
    printf("%d %d\n", ans, n - part);
    delete[] have;
  }
  return 0;
}

UVa 294 - Divisors


#include <stdio.h>
#include <math.h>
#define S 35000

bool *prime = new bool[S];
int *p = new int[S], num = 0;
void build() {
  long long int i, j, k, s = sqrt(S);
  prime[0] = true;
  prime[1] = true;
  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] = true;
  for (i = 0; i < S; i++)
    if (!prime[i])
      p[num++] = i;
}
int div(int n) {
  if (n == 1) return 1;
  int i, ans = 0, tmp;
  for (i = 0; i < num && p[i] <= n; i++) {
    tmp = 0;
    while (n % p[i] == 0) {
      tmp++;
      n /= p[i];
    }
    if (!ans && tmp)
      ans = 1;
    ans *= (tmp + 1);
  }
  return ans;
}
int main() {
  build();
  int i, a, b, n;
  scanf("%d", &n);
  while (n--) {
    scanf("%d%d", &a, &b);
    int tmp, max = 0, ans;
    for (i = a; i <= b; i++) {
      tmp = div(i);
      if (tmp > max) {
        max = tmp;
        ans = i;
      }
    }
    printf("Between %d and %d, %d has a maximum of %d divisors.\n", a, b, ans, max);
  }
  return 0;
}

UVa 10281 - Average Speed

#include <stdio.h>

int main() {
  char tmp[20];
  double h = 0, m = 0, s = 0, speed = 0, H, M, S, Speed, km = 0;
  while (gets(tmp) != NULL) {
    if (tmp[8]) sscanf(tmp, "%lf:%lf:%lf %lf", &H, &M, &S, &Speed);
    else sscanf(tmp, "%lf:%lf:%lf", &H, &M, &S);
    if (!tmp[8]) {
      km += (H - h) * speed + (M - m) * speed / 60 + (S - s) * speed / 3600;
      printf("%s %.2lf km\n", tmp, km);
    } else {
      km += (H - h) * speed + (M - m) * speed / 60 + (S - s) * speed / 3600;
    }
    h = H;
    m = M;
    s = S;
    speed = Speed;
  }
  return 0;
}

UVa 583 - Prime Factors

#include <stdio.h>
#include <math.h>
#define S 50000

bool *prime = new bool[S];
int *p = new int[S], num = 0;
void build() {
  long long int i, j, k, s = sqrt(S);
  prime[0] = true;
  prime[1] = true;
  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] = true;
  for (i = 0; i < 50000; i++)
    if (!prime[i])
      p[num++] = i;
}

int main() {
  build();
  int i, n;
  while (scanf("%d", &n) && n != 0) {
    printf("%d = ", n);
    if (n < 0) {
      printf("-1 x ");
      n *= -1;
    }
    if (n == 2147483647) {
      printf("%d\n", n);
      continue;
    }
    int first = 1, flag = 0;
    for (i = 0; n > 1 && i < num && p[i] <= n; i++) {
      while (n > 1 && n % p[i] == 0) {
        if (first == 1) printf("%d", p[i]);
        else printf(" x %d", p[i]);
        first = 0;
        n /= p[i];
        flag = 1;
      }
    }
    if (!flag)
      printf("%d", n);
    puts("");
  }
  delete[] p;
  delete[] prime;
  return 0;
}

UVa 300 - Maya Calendar


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

char* M[20] = {"imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk", "ok", "chuen", "eb", "ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau"};
int main() {
  int t, d, m, y;
  char tmp[30];
  scanf("%d\n", &t);
  printf("%d\n", t);
  while (t--) {
    scanf("%d. %s %d", &d, &tmp, &y);
    m = 0;
    if (!strcmp(tmp, "no"))
      m = 1;
    if (!strcmp(tmp, "zip"))
      m = 2;
    if (!strcmp(tmp, "zotz"))
      m = 3;
    if (!strcmp(tmp, "tzec"))
      m = 4;
    if (!strcmp(tmp, "xul"))
      m = 5;
    if (!strcmp(tmp, "yoxkin"))
      m = 6;
    if (!strcmp(tmp, "mol"))
      m = 7;
    if (!strcmp(tmp, "chen"))
      m = 8;
    if (!strcmp(tmp, "yax"))
      m = 9;
    if (!strcmp(tmp, "zac"))
      m = 10;
    if (!strcmp(tmp, "ceh"))
      m = 11;
    if (!strcmp(tmp, "mac"))
      m = 12;
    if (!strcmp(tmp, "kankin"))
      m = 13;
    if (!strcmp(tmp, "muan"))
      m = 14;
    if (!strcmp(tmp, "pax"))
      m = 15;
    if (!strcmp(tmp, "koyab"))
      m = 16;
    if (!strcmp(tmp, "cumhu"))
      m = 17;
    if (!strcmp(tmp, "uayet"))
      m = 18;
    int days = m * 20 + d + 1 + y * 365;
    m = days % 20 - 1;
    if (m == -1)
      m = 19;
    d = days % 13;
    if (!d)
      d = 13;
    y = days / 260 - !(days % 260);
    printf("%d %s %d\n", d, M[m], y);
  }
  return 0;
}

UVa 10034 - Freckles


#include <stdio.h>
#include <math.h>

typedef struct {
  double x, y;
} Point;

int main() {
  int i, j, n, t;
  scanf("%d", &t);
  while (t--) {
    Point p[150];
    int visit[150] = {0};
    double x, y, w[150][150], d[150], ans = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++)
      d[i] = 2e9;
    d[0] = 0;
    parent[0] = 0;
    for (i = 0; i < n; i++)
      scanf("%lf%lf", &p[i].x, &p[i].y);
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        w[i][j] = sqrt(pow((p[i].x - p[j].x), 2) + pow(p[i].y - p[j].y, 2));
    for (i = 0; i < n; i++) {
      int a = -1, b = -1, min = 2e9;
      for (j = 0; j < n; j++)
        if (!visit[j] && d[j] < min) {
          a = j;
          min = d[j];
        }
        if (a == -1) break;
        visit[a] = 1;

        for (b = 0; b < n; b++)
          if (!visit[b] && w[a][b] < d[b]) d[b] = w[a][b];
    }
    for (i = 0; i < n; i++)
      ans += d[i];
    printf("%.2lf\n", ans);
    if (t)
      puts("");
  }
  return 0;
}

2012年8月18日

UVa 101 - The Blocks Problem


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

typedef struct {
  int loc;
  int num;
} Block;
Block block[25];
int map[25][25];

void put (int a, int b) {
  int i, j, loc = block[a].loc, nloc = block[b].loc;
  for (i = 0; map[nloc][i] != -1; i++);
  for (j = 0; map[loc][j] != a; j++);
  map[nloc][i] = map[loc][j];
  map[loc][j] = -1;
  block[a].loc = nloc;
}

void pile (int a, int b) {
  int i, j, loc = block[a].loc, nloc = block[b].loc;
  for (i = 0; map[nloc][i] != -1; i++);
  for (j = 0; map[loc][j] != a; j++);
  for ( ; map[loc][j] != -1; j++) {
    block[map[loc][j]].loc = nloc;
    map[nloc][i++] = map[loc][j];
    map[loc][j] = -1;
  }
}

void returning (int n) {
  int i, j, loc = block[n].loc, nloc;
  for (i = 0; map[loc][i] != n; i++);
  for (i++; map[loc][i] != -1; i++) {
    nloc = block[map[loc][i]].num;
    for (j = 0; map[nloc][j] != -1; j++);
    map[nloc][j] = map[loc][i];
    block[map[loc][i]].loc = nloc;
    map[loc][i] = -1;
  }
}

int main() {
  int i, j, n;
  while (scanf("%d", &n) == 1) {
    getchar();
    for (i = 0; i < n; i++) {
      for (j = 0; j < n; j++)
        map[i][j] = -1;
      block[i].loc = i;
      block[i].num = i;
      map[i][0] = i;
    }

    char action[10], method[10];
    int a, b;
    while (scanf("%s", &action)) {
      if (action[0] == 'q')
        break;
      scanf(" %d %s %d", &a, &method, &b);
      if (block[a].loc == block[b].loc)
        continue;
      if (!strcmp(action, "move")) {
        returning(a);
        if (!strcmp(method, "onto"))
          returning(b);
        put(a, b);
      } else {
        if (!strcmp(method, "onto"))
          returning(b);
        pile(a, b);
      }
    }
    for (i = 0; i < n; i++) {
      printf("%d:", i);
      for (j = 0; map[i][j] != -1; j++)
        printf(" %d", map[i][j]);
      puts("");
    }
  }
  return 0;
}

UVa 105 - The Skyline Problem


#include <stdio.h>

int main() {
  int l, h, r, v[11111] = {0}, max = 0, flag = 0;
  while (scanf("%d%d%d", &l, &h, &r) == 3) {
    for (; l < r; l++)
      if (h > v[l]) v[l] = h;
    if (r > max) max = r;
  }
  for (l = 1; l <= max; l++)
    if (v[l] != v[l - 1]) {
      if (flag) printf(" ");
      flag = 1;
      printf("%d %d", l, v[l]);
    }
  puts("");
  return 0;
}