5104. Покатай меня, больша-а-ая Черепаха

Черепашка находится в левой верхней клетке (1, 1) таблицы размером 1012421 × 1099921. Ходить она умеет на клеточку вниз или на клеточку вправо.

Сколькими способами она может добраться до клетки (n, m)?

Вход. В одной строке находятся числа n и m (1 ≤ n, m ≤ 50).

Выход. Выведите одно число – количество способов добраться до клетки (n, m).

Пример входа	Пример выхода
2 2	2

РЕШЕНИЕ

биномиальный коэффициент

Анализ алгоритма

Для передвижения из клетки (1, 1) а клетку (n, m) черепашке следует совершить n + m – 2 шагов. Из них n – 1 шагов будут горизонтальными (и m – 1 вертикальных). Вертикальные и горизонтальные шаги черепашка может чередовать по своему усмотрению. Следовательно количество способов совершить требуемый путь равно = .

Поскольку n, m ≤ 50, то воспользуемся классом BigInteger в Java.

Реализация алгоритма

import java.util.*;

import java.math.*;

public class Main

{

static BigInteger Binom(int n, int k)

{

BigInteger res = BigInteger.ONE;

for (int i = 0; i < k; i++)

res = res.multiply(BigInteger.valueOf(n-i)).

divide(BigInteger.valueOf(i+1));

return res;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m = con.nextInt();

BigInteger res = Binom(n+m-2,n-1);

System.out.println(res);

con.close();

}

}