@ravi.. The recurrence would be : F(N) = F(N-1) + F(N-2) + 2*F(N-3), for N>=3..
F(0) = F(1) = 1, F(2) = F(1) + F(2) = 2 On Jan 11, 11:08 pm, Ravi Ranjan <ravi.cool2...@gmail.com> wrote: > *Problem 1: Number of Tilings, (K Narayan Kumar, CMI)* > > You have to tile a room that is two units wide and *N* units long. You have > with you two types of tiles: a rectangle that is one unit wide and two > units long, and an L-shaped tile covering three square units. Here are > pictures of the two types of tiles. > > [image: Figure 1] > > You are allowed to rotate the tiles when you lay them. You have an infinite > supply of both types of tiles. Your objective is to calculate the number of > different ways of tiling the room using these tiles. > > For instance, a 2×3 room can be tiled in 5 different ways, as follows: > > [image: Figure 2] > > Notice that a tiling can use both types of tiles. Consider, for instance, > the following tiling of a 2×4 room. > > [image: Figure 3] > > Given *N*, your task is to determine the number of ways to tile a room of > size 2×*N*. 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 tile > a 2×13 room is 13465. Your program should just print 3465. If the answer > involves fewer than 4 digits then print the entire answer. For example, if * > N* = 3 you should print 5. > > *Input format* > > A single integer *N*, indicating the size of the room. > > *Output format* > > The last four digits of the number of ways of tiling the 2×*N* room. If the > answer involves fewer than 4 digits, print the entire answer. > > *Test Data:* > > You may assume *N* ≤ 1000000. > > *Example:* > > Here is the sample input and output corresponding to the example discussed > above. > > *Sample Input* > > 13 > > *Sample Output* > > 3465 > > source::http://www.iarcs.org.in/inoi/2006/zio2006/zio2006-qpaper.pdf -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
