Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
UPCOMING CHALLENGES:
CURRENT CHALLENGES:
Niobium 2019
PAST CHALLENGES
Zirconium 2019
Yttrium 2019
Strontium 2019
Rubidium 2018
Arsenicum 2018
Krypton 2018
Bromum 2018
Future Mobility
Grand Challenge
Digital Gold
Selenium 2018
Germanium 2018
Gallium 2018
Zinc 2018
Cuprum 2018
Cutting Complexity
Nickel 2018
Cobaltum 2018
Ferrum 2018
Manganum 2017
Chromium 2017
Vanadium 2016
Titanium 2016
Scandium 2016
Calcium 2015
Kalium 2015
Argon 2015
Chlorum 2014
Sulphur 2014
Phosphorus 2014
Silicium 2014
Aluminium 2014
Magnesium 2014
Natrium 2014
Neon 2014
Fluorum 2014
Oxygenium 2014
Nitrogenium 2013
Carbo 2013
Boron 2013
Beryllium 2013
Lithium 2013
Helium 2013
Hydrogenium 2013
Omega 2013
Psi 2012
Chi 2012
Phi 2012
Upsilon 2012
Tau 2012
Sigma 2012
Rho 2012
Pi 2012
Omicron 2012
Xi 2012
Nu 2011
Mu 2011
Lambda 2011
Kappa 2011
Iota 2011
Theta 2011
Eta 2011
Zeta 2011
Epsilon 2011
Delta 2011
Gamma 2011
Beta 2010
Alpha 2010
ambitious

TilingsCount

START
Count tilings of a narrow but long rectangle with tiles of size 1x1 or 2x2.
Programming language: Spoken language:

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

int solution(int N, int M);

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

int solution(int N, int M);

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

class Solution { public int solution(int N, int M); }

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

func Solution(N int, M int) int

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

class Solution { public int solution(int N, int M); }

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

function solution(N, M);

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

function solution(N, M)

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

function solution(N: longint; M: longint): longint;

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

def solution(N, M)

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

def solution(n, m)

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

object Solution { def solution(n: Int, m: Int): Int }

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

public func solution(_ N : Int, _ M : Int) -> Int

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

A board consisting of squares arranged into N rows and M columns is given. A tiling of this board is a pattern of tiles that covers it. A tiling is interesting if:

  • only tiles of size 1x1 and/or 2x2 are used;
  • each tile of size 1x1 covers exactly one whole square;
  • each tile of size 2x2 covers exactly four whole squares;
  • each square of the board is covered by exactly one tile.

For example, the following images show a few interesting tilings of a board of size 4 rows and 3 columns:

Two interesting tilings of a board are different if there exists at least one square on the board that is covered with a tile of size 1x1 in one tiling and with a tile of size 2x2 in the other. For example, all tilings shown in the images above are different.

Write a function:

Private Function solution(N As Integer, M As Integer) As Integer

that, given two integers N and M, returns the remainder modulo 10,000,007 of the number of different interesting tilings of a board of size N rows and M columns.

For example, given N = 4 and M = 3, the function should return 11, because there are 11 different interesting tilings of a board of size 4 rows and 3 columns:

Write an efficient algorithm for the following assumptions:

  • N is an integer within the range [1..1,000,000];
  • M is an integer within the range [1..7].
Copyright 2009–2019 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

For programmers

LessonsChallengesTermsFAQPrivacy

For companies

TourAbout usPricingJobsBlogTermsPrivacyCookiesAPI

Sign up for our newsletter:

Information about upcoming challenges, solutions and lessons directly in your inbox.

Social:

Contact us:

For customer support queries:

UK +44 (208) 970 78 68

US 1-415-466-8085

support@codility.com

For sales queries:

UK +44 (208) 970 78 68

US 1-415-466-8085

sales@codility.com

© 2009–2019 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN