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