We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #15: Lattice paths
  4. Discussions

Project Euler #15: Lattice paths

Sort by

recency

|

121 Discussions

|

  • yonahel
     + 0 comments

    Haskell

    import Control.Applicative
import Control.Monad
import System.IO
import Prelude

-- Nice memoizer from StackOverflow
memo :: (Int -> Int -> a) -> [[a]]
memo f = map (\x -> map (f x) [0..]) [0..]

pascstore :: [[Integer]]
pascstore = memo pascal

fastpasc :: Int -> Int -> Integer
fastpasc x y = pascstore !! x !! y

-- Basic Pascal Triangle Recursion
pascal :: Int -> Int -> Integer
pascal n 0 = 1
pascal 0 k = 1
pascal n k = (fastpasc n (k-1)) + (fastpasc (n-1) k)

main :: IO ()
main = do
    t_temp <- getLine
    let t = read t_temp :: Int
    forM_ [1..t] $ \a0  -> do
        n_temp <- getLine
        let n = (map (read :: String -> Int) . words) n_temp 
        let m = max (n !! 0) (n !! 1) 
        let k = min (n !! 0) (n !! 1) 
        let routes = pascal m k
        print(routes `mod` 1000000007)

  • CS_2212256_T
     + 0 comments
    import java.util.Scanner;

public class Solution {
    public static long factorial(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result = (result * i) % (1000000007);
        }
        return result;
    }

    public static long pow(long base, long exponent, long mod) {
        long result = 1;
        base = base % mod;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % mod;
            }
            exponent = exponent / 2;
            base = (base * base) % mod;
        }
        return result;
    }

    public static long modInverse(long a, long m) {
        return pow(a, m - 2, m);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        scanner.nextLine(); // Consume newline left-over
        for (int i = 0; i < t; i++) {
            String[] item = scanner.nextLine().split(" ");
            int n = Integer.parseInt(item[0]);
            int m = Integer.parseInt(item[1]);
            long answer = (factorial(n + m) * modInverse((factorial(n) * factorial(m)) % 1000000007, 1000000007)) % 1000000007;
            System.out.println(answer);
        }
    }
}

  • akshaymoolath
     + 0 comments
    #python
import math
for i in range(int(input())):
    n, m=map(int, input().split())
    print(math.comb(n+m, m) %(10**9+7))

  • SAGILE_MANOJ_KU1
     + 0 comments

    for C#

    using System;

    class Program { const int MOD = 1000000007;

    static int CountRoutes(int N, int M)
{
    int[,] dp = new int[N + 1, M + 1];

    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (i == 0 || j == 0)
            {
                dp[i, j] = 1;
            }
            else
            {
                dp[i, j] = (dp[i - 1, j] + dp[i, j - 1]) % MOD;
            }
        }
    }

    return dp[N, M];
}

static void Main()
{
    int T = int.Parse(Console.ReadLine());

    for (int t = 0; t < T; t++)
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        int result = CountRoutes(N, M);
        Console.WriteLine(result);
    }
}

    }

  • srikv
     + 0 comments

    passed all test cases

    # Enter your code here. Read input from STDIN. Print output to STDOUT
import sys

sys.setrecursionlimit(5000)

def findpath(n , m, seen):
    if (n,m) in seen:
        return(seen[(n,m)]%(7+10**9))
    if n == 0 or m == 0:
        return(1)
    else:
        seen[(n,m)] = (findpath(n-1,m,seen)+findpath(n,m-1,seen))%(7+10**9)
        return(seen[(n,m)])
        
seen = {(0,0): 1}

findpath(500, 500, seen)

for a0 in range(int(input())):
    n, m =list(map(int, input().split()))
    print(seen[(n, m)])

    for a0 in range(int(input())): n, m =list(map(int, input().split())) print(seen[(n, m)])****