2014年2月1日

UVa 11341 - Term Strategy

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, M;
    scanf("%d%d", &N, &M);
    int dp[11][101] = {}, sum = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 1; j <= M; j++) {
        int grade;
        scanf("%d", &grade);
        for (int w = M; grade >= 5 && w >= j; w--) {
          if ((i == 1 && w == j) || dp[i - 1][w - j]) {
            dp[i][w] = max(dp[i][w], dp[i - 1][w - j] + grade);
            if (i == N && dp[i][w] > sum) {
              sum = dp[i][w];
            }
          }
        }
      }
    }
    if (sum) {
      printf("Maximal possible average mark - %.2lf.\n", sum / (double)N + 1e-9);
    } else {
      puts("Peter, you shouldn't have played billiard that much.");
    }
  }
  return 0;
}

UVa 11658 - Best Coalitions

#include <cstdio>

int main() {
  int n, x;
  while (scanf("%d%d", &n, &x) && n) {
    int num[101];
    bool dp[10001] = {true};
    for (int i = 1; i <= n; i++) {
      int n1, n2;
      scanf("%d.%d", &n1, &n2);
      num[i] = n1 * 100 + n2;
      if (i == x) {
        continue;
      }
      for (int w = 10000; w >= num[i]; w--) {
        dp[w] |= dp[w - num[i]];
      }
    }
    int sum = 0;
    for (int w = 10000; w >= num[x] && w > 5000; w--) {
      if (dp[w - num[x]]) {
        sum = w;
      }
    }
    printf("%.2lf\n", (num[x] / (double)sum) * 100.0);
  }
  return 0;
}

UVa 10337 - Flight Planner

#include <cstdio>
#include <algorithm>

using namespace std;

int dp[1001][10], w[1000][10];

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int X;
    scanf("%d", &X);
    int n = X / 100;
    for (int h = 9; h >= 0; h--) {
      for (int i = 0; i < n; i++) {
        scanf("%d", &w[i][h]);
      }
    }
    for (int i = 0; i <= n; i++) {
      for (int h = 0; h <= 9; h++) {
        if (!i) {
          if (h) {
            dp[i][h] = 1e8;
          }
          continue;
        }
        dp[i][h] = dp[i - 1][h] + 30 - w[i - 1][h];
        if (h != 9) {
          dp[i][h] = min(dp[i][h], dp[i - 1][h + 1] + 20 - w[i - 1][h + 1]);
        }
        if (h != 0) {
          dp[i][h] = min(dp[i][h], dp[i - 1][h - 1] + 60 - w[i - 1][h - 1]);
        }
      }
    }
    printf("%d\n\n", dp[n][0]);
  }
  return 0;
}