DWITE '10 R3 #3 - Dominos Tiling

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, December 2010, Problem 3

Counting the number of tilings of different sized boards with dominoes (i.e. 2 by 1 rectangles) can be a pretty difficult task. However, here you must only determine the number of ways to tile boards of height 3 and some width.

The input will contain 5 lines, each containing an integer 0 \le N \le 30, the width of the board you want to tile with dominoes.

The output will contain 5 lines, where each line represents the number of ways to tile a 3 \times N board with dominoes modulo 1\,000\,000 (i.e. The output is the remainder you get when you divide the number of ways to tile a 3 \times N board with dominoes by 1\,000\,000).

Sample Input

1
4
3
25
13

Sample Output

0
11
0
0
0

Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


Comments