2013年4月30日

UVa 598 - Bundling Newspapers


#include <stdio.h>

int n;
char word[99][99];

void find(int now, int need, int already, int * used) {
  int i, j;
  if (already == need) {
    for (i = 0, j = 0; i < n; i++)
      if (used[i]) printf("%s%s", word[i], ++j == need ? "\n" : ", ");
    return;
  }
  for (i = now; i < n; i++) {
    used[i] = 1;
    find(i + 1, need, already + 1, used);
    used[i] = 0;
  }
}

int main() {
  char s[99];
  gets(s);
  int T;
  sscanf(s, "%d", &T);
  gets(s);
  while (T--) {
    gets(s);
    n = 0;
    while (gets(word[n]) && word[n][0])
      n++;
    int l, r;
    if (s[0] == '*') {
      l = 1, r = n;
    } else if (!s[1] || !s[2]) {
      sscanf(s, "%d", &l);
      r = l;
    } else {
      sscanf(s, "%d%d", &l, &r);
    }
    while (l <= r) {
      int used[99] = {};
      printf("Size %d\n", l);
      find(0, l++, 0, used);
      puts("");
    }
    if (T) puts("");
  }
  return 0;
}

UVa 10669 - Three powers


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

public class Main {

  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    BigInteger n;
    while (cin.hasNext()) {
      n = cin.nextBigInteger();
      if (n.compareTo(BigInteger.ZERO) == 0) break;
      n = n.subtract(BigInteger.ONE);
      Vector<BigInteger> ans = new Vector<BigInteger>();
      while (n.compareTo(BigInteger.ZERO) != 0) {
        BigInteger two = BigInteger.ONE, three = BigInteger.ONE;
        while (two.compareTo(n) < 0) {
          two = two.shiftLeft(1);
          three = three.multiply(BigInteger.valueOf(3));
        }
        if (two.compareTo(n) != 0) {
          two = two.shiftRight(1);
          three = three.divide(BigInteger.valueOf(3));
        }
        n = n.subtract(two);
        ans.add(three);
      }
      System.out.print("{");
      for (int i = ans.size() - 1; i >= 0; i--)
        System.out.print(" " + ans.elementAt(i) + (i == 0 ? "" : ","));
      System.out.println(" }");
    }
  }
    
}

2013年4月25日

UVa 10249 - The Grand Dinner


#include <cstdio>
#include <set>
#include <algorithm>

int main () {
  int m, n;
  while (scanf("%d%d", &m, &n) && m || n) {
    int num[99], size[99];
    for (int i = 0; i < m; i++)
      scanf("%d", &num[i]);
    for (int i = 0; i < n; i++)
      scanf("%d", &size[i]);
    std::set<int> table[99];
    int loc[99][99];
    bool fail = false;
    for (int i = 0; i < m && !fail; i++)
      for (int j = 0; j < num[i] && !fail; j++) {
        int max = 0, choose = -1;
        for (int k = 0; k < n; k++)
          if (table[k].size() < size[k] && !table[k].count(i) && size[k] - table[k].size() > max) {
            max = size[k] - table[k].size();
            choose = k;
          }
        if (choose == -1) {
          fail = true;
        } else {
          table[choose].insert(i);
          loc[i][j] = choose + 1;
        }
      }
    puts(fail ? "0" : "1");
    if (fail) continue;
    for (int i = 0; i < m; i++) {
      std::sort(loc[i], loc[i] + num[i]);
      for (int j = 0; j < num[i]; j++)
        printf("%d%s", loc[i][j], j == num[i] - 1 ? "\n" : " ");
    }
  }
  return 0;
}

2013年4月19日

UVa 902 - Password Search


#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
  string s;
  int l;
  while (cin >> l >> s) {
    map<string, int> dic;
    string ans;
    for (int i = 0, len = s.length(); i + l <= len; i++)
      dic[s.substr(i, l)]++;
    int max = 0;
    for (map<string, int>::iterator it = dic.begin(); it != dic.end(); it++)
      if (it->second > max) ans = it->first, max = it->second;
    puts(ans.c_str());
  }
  return 0;
}

2013年4月10日

UVa 10313 - Pay the Price


#include <stdio.h>

unsigned long long dp[1005][1005];

int main() {
  int i, j, k;
  dp[0][0] = 1;
  for (i = 1; i < 305; i++)
    for (j = i; j < 305; j++)
      for (k = 1; k < 305; k++)
        dp[j][k] += dp[j - i][k - 1];
  char s[99];
  while (gets(s)) {
    int space = 0;
    for (i = 0; s[i]; i++)
      if (s[i] == ' ' && i && s[i - 1] <= '9' && s[i - 1] >= '0') space++;
    int n, l1, l2;
    if (!space) {
      sscanf(s, "%d", &n);
      l1 = 0;
      l2 = 1004;
    } else if (space == 1) {
      sscanf(s, "%d%d", &n, &l2);
      l1 = 0;
    } else {
      sscanf(s, "%d%d%d", &n, &l1, &l2);
    }
    unsigned long long ans = 0;
    for (i = l1; i <= l2 && i <= n; i++)
      ans += dp[n][i];
    printf("%llu\n", ans);
  }
  return 0;
}

UVa 11517 - Exact Change


#include <stdio.h>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, m;
    scanf("%d%d", &m, &n);
    int i, j, p[100], dp[10001] = {1}, cnt[10001];
    for (i = 0; i < n; i++)
      scanf("%d", &p[i]);
    for (i = 0; i <= 10000; i++)
      cnt[i] = 2e9;
    cnt[0] = 0;
    for (i = 0; i < n; i++)
      for (j = 10000; j >= p[i]; j--)
        if (dp[j - p[i]]) {
          dp[j] = 1;
          if (cnt[j] > cnt[j - p[i]] + 1) cnt[j] = cnt[j - p[i]] + 1;
        }
    for (i = m; ; i++)
      if (dp[i]) {
        printf("%d %d\n", i, cnt[i]);
        break;
      }
  }
  return 0;
}

2013年4月9日

UVa 11450 - Wedding shopping


#include <stdio.h>

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int m, c, dp[21][200] = {};
    scanf("%d%d", &m, &c);
    int i, j, k, num[21], price[21][20];
    for (i = 1; i <= c; i++) {
      scanf("%d", &num[i]);
      for (j = 0; j < num[i]; j++)
        scanf("%d", &price[i][j]);
    }
    dp[0][0] = 1;
    for (i = 1; i <= c; i++)
      for (j = 0; j < num[i]; j++)
        for (k = price[i][j]; k <= m; k++)
          dp[i][k] += dp[i - 1][k - price[i][j]];
    int max = 0;
    for (i = 0; i <= m; i++)
      if (dp[c][i]) max = i;
    if (max) printf("%d\n", max);
    else puts("no solution");
  }
  return 0;
}

UVa 657 - The die is cast


#include <cstdio>
#include <vector>
#include <algorithm>

int w, h, cnt;
char map[99][99];
std::vector<int> ans;

void clear(int r, int c) {
  if (r < 0 || c < 0 || r >= h || c >= w ||map[r][c] != 'X') return;
  map[r][c] = '.';
  clear(r + 1, c);
  clear(r - 1, c);
  clear(r, c + 1);
  clear(r, c - 1);
}

void run(int r, int c) {
  if (r < 0 || c < 0 || r >= h || c >= w ||map[r][c] == '.') return;
  if (map[r][c] == 'X') {
    cnt++;
    clear(r, c);
  }
  map[r][c] = '.';
  run(r + 1, c);
  run(r - 1, c);
  run(r, c + 1);
  run(r, c - 1);
}

int main() {
  int T = 1;
  while (scanf("%d%d", &w, &h) && w || h) {
    ans.clear();
    int r, c;
    for (r = 0; r < h; r++)
      scanf("%s", map[r]);
    for (r = 0; r < h; r++)
      for (c = 0; c < w; c++)
        if (map[r][c] == '*' || map[r][c] == 'X') {
          cnt = 0;
          run(r, c);
          if (cnt) ans.push_back(cnt);
        }
    std::sort(ans.begin(), ans.end());
    printf("Throw %d\n", T++);
    for (r = 0; r < ans.size(); r++)
      printf("%d%s", ans[r], r == ans.size() - 1 ? "\n\n" : " ");
  }
  return 0;
}

2013年4月5日

UVa 10739 - String to Palindrome


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

int dp[1005][1005];

int min(int a, int b) {
  return a < b ? a : b;
}

int main() {
  int T, C = 1;
  scanf("%d\n", &T);
  while (T--) {
    memset(dp, 0, sizeof(dp));
    char s[1005];
    gets(s + 1);
    int len = strlen(s + 1), l, r;
    for (l = len; l >= 1; l--)
      for (r = l; r <= len; r++)
        if (s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1];
        else dp[l][r] = min(dp[l + 1][r - 1], min(dp[l + 1][r], dp[l][r - 1])) + 1;
    printf("Case %d: %d\n", C++, dp[1][len]);
  }
  return 0;
}