BYTESH1 - Filchs Dilemna
Filch’s Dilemma (15 points)
Argus Filch, the caretaker of Hogwarts, has been given the task to carpet the way to Hogwarts through the grounds. The way is 2 units wide and ‘N’ units long. He has only two types of carpets available, one is 1 unit wide and 2 units long and the other one is L shaped, having 3 square units. Here are their pictures:
Filch can rotate the carpets when he lays them and has an infinite supply of both types of carpets. As Filch is a squib he cannot magically arrange the carpets and has to resort to logic to find out all possible ways of carpeting the way. He wishes to calculate the number of different ways of carpeting the way.
For instance, a 2x3 way can be carpeted in 5 different ways as follows:
Notice that both types of carpets can be used simultaneously. Consider, for instance the following way of carpeting a 2x4 way:
Given N, you have to help Filch determine the number of ways to carpet the way of size 2xN. Since this number may be very large, it is sufficient to report the last four digits of the answer. For instance the number of ways to carpet a 2x13 way is 13465. Your program should just print 3465. If the answer is in 4 digits or less it should print the entire answer. For example, if N=3 you should print 5.
The first line of the input consists of a single integer T(1<=T<=100). Each of the next T lines consists of a single integer N (1<=N<=1000000), indicating the size of the way.
For each test case, output the last four digits of the number of ways of carpeting the 2xN way. If the answer involves fewer than 4 digits, print the entire number.
Important Update - If the output of last four digits has leading zeros, print the output without the leading zeros
Input: 2 3 13 Output: 5 3465
Good problem ! Don't forget to mod the ans while generating.
No extreme test cases!
Blog Thuật toán SPOJ can help you : http://www.oni.vn/uR57W
Deepak Singh Tomar:
my 150th... :)
nice one !! love such kinda problems
I've made a copy of the problem description (as of 2012-11-19) with images here.Last edit: 2012-11-19 11:18:11
image not visible
N is not precise , N<100000
Images are not visible
|Added by:||Paritosh Aggarwal|
|Cluster:||Cube (Intel G860)|
|Languages:||ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST TEXT WHITESPACE|