2013年8月31日

UVa 10306 - e-Coins

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int m, s;
    scanf("%d%d", &m, &s);
    int dp[301][301];
    for (int j = 0; j <= s; j++) {
      for (int k = 0; k <= s; k++) {
        dp[j][k] = 1e7;
      }
    }
    dp[0][0] = 0;
    while (m--) {
      int x, y;
      scanf("%d%d", &x, &y);
      for (int j = x; j <= s; j++) {
        for (int k = y; k <= s; k++) {
          dp[j][k] = min(dp[j][k], dp[j - x][k - y] + 1);
        }
      }
    }
    int ans = 1e7;
    for (int j = 0; j <= s; j++) {
      for (int k = 0; k <= s; k++) {
        if (j * j + k * k == s * s) {
          ans = min(ans, dp[j][k]);
        }
      }
    }
    if (ans >= 1e7) {
      puts("not possible");
    } else {
      printf("%d\n", ans);
    }
  }
  return 0;
}

沒有留言:

張貼留言