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