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