NextFloor

すきな物やモノに囲まれて生きていく!

「増井技術士事務所 今週のお題:指定された回数で移動できる経路は何通り?正答率80%」

解けなかったのでメモ。
f:id:aizirohutaai:20170718161041p:plain

回答

/*
 
 入力値
 m (0 < m <= 20)
 横マスの数
 
 n (0 < n <= 20)
 縦マスの数
 
 a (1 < a <= m + n)
 
 入力フォーマット
 m n a
 
 -------------------------------
 
 求め方
 以下の数式で求まるはず。
 
    p = aCk * (a-k)Cwi * (a-k-wi)Chj
 
 入力値 m n aより以下の値を求める。
 
    ①斜め移動の回数をkと置く
        k = m + n - a
 
    ②横移動の回数をwiと置く
        wi = n - k
 
    ③縦移動の回数をhjと置く
        hj = n - k
 
 -------------------------------
 
 実装方針
 
 ①順列数を求める機能
 ②組み合わせ数を求める機能
 ③上記の式を実装した機能
 
 */

#include<stdio.h>

// 順列数を求める機能
int permutation(int n, int r)
{
    int i, p = 1;
    for(i = n; (n - r) < i; i--){
        p *= i;
    }
    return(p);
}

// 組み合わせ数を求める機能
int combination(int n, int r)
{
    int p, q, c;
    // 順列数を求める
    p = permutation(n, r);
    // 重複度の順列数を求める
    q = permutation(r, r);
    // 順列数を重複度の順列数でわる
    c = p / q;
    return(c);
}

// 上記の式を実装した機能
long ans(int m, int n, int a)
{
    int k, wi, hj, t1, t2, t3;
    long ans = 1;
    
    k = m + n - a;
    wi = m - k;
    hj = n - k;
    
    t1 = combination(a, k);
    t2 = combination(a - k, wi);
    t3 = combination(a - k - wi, hj);
    
    ans = ans * t1 * t2 * t3;
    
    return(ans);
}

int main(int argc, const char * argv[])
{
    int m, n, a;
    scanf("%d %d %d", &m, &n, &a);
    printf("%ld\n", ans(m, n, a));
    return 0;
}