dailycoding-20120806

dc20120806.cs

using System;

namespace DailyCoding
{
	class MainClass
	{
		/*
		 * 2 × 2 のマス目の左上からスタートした場合、引き返しなしで右下にいくルートは 6 つある。
		 * では、20 × 20 のマス目ではいくつのルートがあるか。
		 */
		public static void Main(string[] args)
		{
			Console.WriteLine(GetRouteNum(20));
		}

		private static long GetRouteNum(long size)
		{
			return Combination(size * 2, size);
		}

		private static long Combination(long left, long right)
		{
			long res = 1;
			for (long i = 1; i <= right; i++) {
				res *= left - right + i;
				res /= i;
			}
			return res;
		}

	}
}

// 137846528820