UVA 10444 - Multi-peg Towers of Hanoi

math dp uva

這題最麻煩的是理解題目, 很難明白. 我是看了別人答題才明白那段文字的意思. (code can explain itself)

重點是圖片下面那一段介紹.

That is, if there are disks each of which requires 2^k+1 moves to reach destination, then number of disks each
of which require 2^k moves to reach destination is p−3+kCk (number of combinations of (p−3+k) things
taken k at a time)

如果當前所有 disks 之中有disk要用到 2^(k+1) 的次數去移動.那當中有p−3+kCk 的disk要用 ２^k 的次數去移動. 由此可見當中是有遞進的關係.

設 n(k) = p−3+kCk = disk 的數目

  • n(k+1) = n(k)(2^k) + (n(k+1) - n(k))(2^k+1)
  • n(k) = n(k-1)(2^k-1) + (n(k) - n(k-1))(2^k)
  • …
uva10444.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long LL;

LL fac(int k) {
  LL sum = 1;
  for(int i = 2; i <= k; ++i)
    sum *= i;
  return sum;
}

int ncr(int n, int r) {
  if(r == 0 || n == r) return 1;
  r = min(r, n-r);

  LL nf = fac(n);
  LL rf = fac(r);
  LL nrf = fac(n - r);
  return nf/(rf * nrf);
}

int main() {
  int counter = 1;
  int n, p;

  while(scanf("%d%d", &n, &p) && (n || p)) {
    if(n == 0) {
      printf("Case %d: %d\n", counter++, 0);
    } else {
        int moved = 0;
        int result = 0;
        for(int k = 0; ;++k) {
          int num = ncr(p-3+k, k);
          int cost = 1 << k; // 2 ^ k
          if(moved + num >= n) {
            result += cost*(n - moved);
            break;
          } else {
            moved += num;
            result += cost * num;
          }
        }
        printf("Case %d: %d\n", counter++, result);
    }
  }

  return 0;
}