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
|
#include <stdio.h>
#include <gmp.h>
// Compile Notes: use `gcc <program>.c -lgmp`
// Starting in the top left corner of a 2×2 grid,
// and only being able to move to the right and down,
// there are exactly 6 routes to the bottom right corner.
// How many such routes are there through a 20×20 grid?
// This is another problem where pure math is the best solution
// Taking a look at the 2x2 grid, you notice all paths need 4 steps
// Check for a 3x3 and a 4x4, you'll notice the paths need 6 and
// 8 steps respectively. So a 20x20 will take 2*20 or 40 steps
// Another way of stating this problem: we have forty steps to take
// and each one will be either right or down AND they must be equal.
// I couldn't traverse a 2 x 2 by going RRRD,
// it must be RRDD, RDRD, DDRR, DRDR, RDDR, DRRD
// So of 40 steps we have to make, we have twenty choices to choose from.
// i.e. 40 nCr 20
// nCr = n!/r!(n-r)!
// = 40!/(20! * 20!)
// = 40*39*38*...*21 / 20*19*18...
int main(){
mpz_t nCr;
mpz_init_set_ui(nCr, 1);
for(long i = 21; i <= 40; i++)
mpz_mul_ui(nCr, nCr, i);
for(long i = 20; i > 0; i--)
mpz_fdiv_q_ui(nCr, nCr, i);
gmp_printf("%Zd\n", nCr);
return 0;
}
|
