Cerinta completa

You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width):

d	h	w
1	1	1
1	1	2
1	1	3
1	1	4

Using these blocks, you want to make a wall of height and width . Features of the wall are:

– The wall should not have any holes in it.
– The wall you build should be one solid structure, so there should not be a straight vertical break across all rows of bricks.
– The bricks must be laid horizontally.

How many ways can the wall be built?

Example


The height is and the width is . Here are some configurations:

image

These are not all of the valid permutations. There are valid permutations in all.

Function Description

Complete the legoBlocks function in the editor below.

legoBlocks has the following parameter(s):

  • int n: the height of the wall
  • int m: the width of the wall

Returns
– int: the number of valid wall formations modulo

Input Format

The first line contains the number of test cases .

Each of the next lines contains two space-separated integers and .

Constraints


Sample Input

STDIN   Function
-----   --------
4       t = 4
2 2     n = 2, m = 2
3 2     n = 3, m = 2
2 3     n = 2, m = 3
4 4     n = 4, m = 4

Sample Output

3  
7  
9  
3375

Explanation

For the first case, we can have:

image

For the second case, each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically. Thus, the number of ways is and .

Limbajul de programare folosit: rust

Cod:

use std::env;
use std::fs::File;
use std::io::{self, BufRead, Write};

/*
 * Complete the 'legoBlocks' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n
 *  2. INTEGER m
 */

fn legoBlocks(n: i32, m: i32) -> i32 {
    let h = n as usize;
    let w = m as usize;

    let modulo: u64 = 1000000007;

    // if width is 0, combination is 1
    // if width is 1, combination is 1
    // if width is 2, combination is 2
    // if width is 3, combination is 4
    let mut row_combinations: Vec<u64> = vec![1, 1, 2, 4];

    // Build row combinations up to current wall's width
    while row_combinations.len() <= w {
        row_combinations.push(row_combinations.iter().rev().take(4).sum::<u64>() % modulo);
    }

    // Calculate total combination containing violations
    let mut total_combination: Vec<u64> = vec![];

    for (i, combination) in row_combinations.iter().enumerate() {
        total_combination.push(1);

        for _ in 0..h {
            total_combination[i] = total_combination[i] * combination % modulo;
        }
    }

    // Calculate unstable
    let mut unstable: Vec<u64> = vec![0, 0];

    for i in 2..=w {
        let mut unstable_i = 0;

        for j in 1..i {
            unstable_i = (unstable_i
                + (total_combination[j] + modulo - unstable[j]) * total_combination[i - j])
                % modulo;
        }

        unstable.push(unstable_i);
    }

    ((total_combination[w] + modulo - unstable[w]) % modulo) as i32
}

fn main() {
    let stdin = io::stdin();
    let mut stdin_iterator = stdin.lock().lines();

    // let mut fptr = File::create(env::var("OUTPUT_PATH").unwrap()).unwrap();

    let t = stdin_iterator
        .next()
        .unwrap()
        .unwrap()
        .trim()
        .parse::<i32>()
        .unwrap();

    for _ in 0..t {
        let first_multiple_input: Vec<String> = stdin_iterator
            .next()
            .unwrap()
            .unwrap()
            .split(' ')
            .map(|s| s.to_string())
            .collect();

        let n = first_multiple_input[0].trim().parse::<i32>().unwrap();

        let m = first_multiple_input[1].trim().parse::<i32>().unwrap();

        let result = legoBlocks(n, m);

        // writeln!(&mut fptr, "{}", result).ok();
        println!("{}", result);
    }
}

Scor obtinut: 1.0

Submission ID: 464612683

Link challenge: https://www.hackerrank.com/challenges/lego-blocks/problem

Lego Blocks