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

沒有留言:

張貼留言