カエル跳びゲームを一般化して！

カエル跳びゲームを一般化して！

締め切りが 2018/01/02 10:00 AM なので，その 1 分後に投稿されるように予約

パズルで有名な「カエル跳びゲーム」を一般化したものを考えます。
n 個のマスがあり、左側から a マスには右に進むa匹のカエルが、右側から b マスには左に進むb匹のカエルがいます。
1つのマスには1匹のカエルしか入れられず、一度に1匹のカエルを移動します。

このカエルの位置を左右入れ替えることを考えます。
（右向きのカエルをすべて右側に、左向きのカエルをすべて左端に寄せるまで繰り返します。）

それぞれのカエルは、進む方向の隣のマスが空いていれば、その場所に移動できます。
また、隣に相手のカエルがいても、その先が空いていれば、一マスだけ飛び越えることができます。
二匹以上のカエルは飛び越えることはできませんし、同じ向きのカエルを飛び越えることもできません。
当然、逆方向に進むこともできません。

この操作を行い、最短の回数で移動するときの移動回数を求めてください。
なお、それぞれの向きのカエルを交互に移動する必要はありませんので、どちらから始めても構いませんし、同じ向きのカエルを連続して動かしても構いません。

例えば、n = 5, a = 2, b = 2 のとき、以下の図のような手順で移動すると、8回で移動できます。

標準入力から n, a, b がスペースで区切って与えられますので、最短の移動回数を標準出力に出力してください。
なお、n, a, b は n > a + b を満たす整数で、n は最大で14とします。

【入出力サンプル】
標準入力
5 2 2

標準出力
8

==================================================================

n, a, b が小さいときの解を求め，規則性を調べる。

これをプログラム化して，以下を得る。計算は，瞬時に終わる。

f = function(n, a, b) {
  x = array(0, dim = c(n - 2, n - 2, n))
  for (N in 3:n) {
    mx = N - 2
    for (A in 1:mx) {
      B = mx + 1 - A
      x[A, B, N] = A * B + A + B
    }
    if (N >= 4) {
      for (A in 1:(mx - 1)) {
        for (B in 1:(mx - A)) {
          x[A, B, N] = x[A, B, N - 1] + A + B
        }
      }
    }
  }
  cat(x[a, b, n])
}

#arg = scan(file("stdin", "r"))
#f(arg[1], arg[2], arg[3])

f(5, 2, 2) # 8
f(8, 2, 5) # 17
f(10, 3, 3) # 33
f(12, 4, 5) # 47
f(14, 6, 6) # 60

参考までに，n, a, b が小さいときの解を求めるプログラムを以下に示す。
これは，http://www.geocities.jp/m_hiroi/puzzle/kaeru.html に示されている perl によるプログラムを R に書き換えたものである。

f = function(n, a, b) {
  space = rep(" ", n - a - b)
  a = rep("a", a)
  b = rep("b", b)
  start = paste(c(a, space, b), collapse = "")
  goal  = paste(c(b, space, a), collapse = "")
 
  state = integer(50000)        # 状態を格納
  prev_state = integer(50000)   # 前の状態を指す
  state_check = character(50000)  # 状態チェックのハッシュ
 
  # 置換用
  search =  c("ab ", " ab", "a ", " b")
  replace = c(" ba", "ba ", " a", "b ")
 
  w = 2     # ライトカウンタ
  r = 0     # リードカウンタ
  # 初期化
  state[1] = start
  prev_state[1] = -1
 
  print_answer = function(i, disp = FALSE) {
    count = 0
    
    if (disp) {
      cat(state[i], "\n")
    }
    repeat {
      i = prev_state[i]
      if (disp) {
        cat(state[i], "\n")
      }
      count = count + 1
      if (prev_state[i] == -1) {
        break
      }
    }
    #cat(count)
    count
  }
 
  repeat {
    r = r + 1
    if (r >= w) {
      break
    }
    for (i in 1:4) {
      new = state[r]
      sea = sprintf("(.*)%s(.*)", search[i])
      rep = sprintf("\\1%s\\2", replace[i])
      new2 = sub(sea, rep, new)
      if (new != new2) {
        state[w] = new2
        prev_state[w] = r
        if (!any(grepl(new2, state_check[1:w]))) {
          if (goal == new2) {
            return(print_answer(w))
          }
          state_check[w] = new2
          w = w + 1
        }
      }
    }
  }
}