Back
Close
  • 8

What will I learn?

Dynamic programmingTiling

Statement

 Goal

The Problem:

You are required to fill an K × N grid using the following pieces:

A 2×2 Piece:
┌───┐ 
│ │
└───┘
A 3×1 Piece which can be placed in two ways:
┌─────┐ 
└─────┘
┌─┐
│ │
│ │
└─┘
Given that K is always either 1, 2 or 3.

You have to output the total number of ways of doing this.

-------------------------------------------------- xxx --------------------------------------------------

Rules:

1. The entire grid must be filled i.e. there can be no empty cell.

2. No 2 tiles can overlap.

3. As already pointed above, the 3×1 Tile can be placed horizontally or vertically.

4. Since the answer might be large output it modulo 10⁹+7.

5. Note that there may also be 0 ways of filling a particular grid.

-------------------------------------------------- xxx --------------------------------------------------

Examples:

1. K = 1 and N = 6:
┌─────┬─────┐
└─────┴─────┘
So there is only 1 way of doing this.


2. K = 2 and N = 6:
┌─────┬─────┐  ┌───┬───┬───┐
├─────┼─────┤ │ │ │ │
└─────┴─────┘ └───┴───┴───┘
So there are 2 ways of doing this.


3. K = 3 and N = 6:
┌─────┬─────┐  ┌───┬───┬───┐  ┌─────┬─────┐  ┌─┬─┬─────┬─┐
├─────┼─────┤ │ │ │ │ ├───┬─┴─┬───┤ │ │ ├─────┤ │
├─────┼─────┤ ├───┴─┬─┴───┤ │ │ │ │ │ │ ├─────┤ │
└─────┴─────┘ └─────┴─────┘ └───┴───┴───┘ └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐ ┌─┬─┬─┬─────┐ ┌─────┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │ │ │ │ ├─────┤ ├─────┤ │ │ │ │ │ │ │ │ │ │
│ ├─────┤ │ │ │ │ │ ├─────┤ ├─────┤ │ │ │ │ │ │ │ │ │ │
└─┴─────┴─┴─┘ └─┴─┴─┴─────┘ └─────┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
So there are 8 ways of doing this.
Input
Line 1: An integer T, the number of test cases
Next T Lines: Integers K and N, the height and width of the grid respectively
Output
First T Lines: An integer W, the total number of ways of tiling the respective grid modulo 10⁹ + 7
Constraints
1 ≤ T ≤ 10
1 ≤ K ≤ 3
1 ≤ N ≤ 10⁶
Example
Input
2
1 6
1 9
Output
1
1
Solve it

A higher resolution is required to access the IDE

codingame x discord
Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!
JOIN US ON DISCORD
Online Participants