10668. Paths on a grid

 

You have a piece of paper and you choose a rectangle of size n * m on it. Let’s call this rectangle together with the lines it contains a grid. Starting at the lower left corner of the grid, you move your pencil to the upper right corner, taking care that it stays on the lines and moves only to the right or up. The result is shown on the left:

 

prb10668.gif

 

Really a masterpiece, isn’t it? Repeating the procedure one more time, you arrive with the picture shown on the right. Now you wonder: how many different works of art can you produce?

 

Input. Two positive integers n and m.

 

Output. Print the number of different art works that can be generated using the procedure described above. You may safely assume that this number fits into a 64-bit signed integer.

 

Sample input 1

Sample output 1

3 4

35

 

 

Sample input 2

Sample output 2

1 1

2

 

 

SOLUTION

combinatorics

 

Algorithm analysis

The required path is a broken line consisting of n + m links. Of these, n links must be vertical, and the rest must be horizontal. The number of ways to choose n vertical links out of n + m is equal to .

 

Example

For the first test case n = 3, m = 4. The answer is  =  =  = 35.

For the second test case n = 1, m = 1. The answer is  =  = 2.

 

Algorithm realization

The Cnk function computes the value of the binomial coefficient .

 

long long Cnk(long long n, long long k)

{

  long long res = 1;

  if (k > n - k) k = n - k;

  for (long long i = 1; i <= k; i++)

    res = res * (n - i + 1) / i;

  return res;

}

 

The main part of the program. Read the input data.

 

scanf("%lld %lld", &n, &m);

 

Compute and print the answer .

 

res = Cnk(n + m, n);

printf("%lld\n", res);

 

Python realization

 

import math

 

Read the input data.

 

n, m = map(int,input().split())

 

Compute and print the answer .

 

res = math.comb(n + m, n)

print(res)