EppsNet Archive: Recursion

Competitive Programming: POJ 2488 – A Knight’s Journey

Description Background The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans? Problem Find a path such that the knight visits every square once. The knight can start and end on any square of the board. Input The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such… Read more →

Competitive Programming: POJ 2663 – Tri Tiling

Description In how many ways can you tile a 3xn rectangle with 2×1 dominoes? Here is a sample tiling of a 3×12 rectangle. Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30. Output For each test case, output one integer number giving the number of possible tilings. Sample Input 2 8 12 -1 Sample Output 3 153 2131 Link to problem Solution below . . . Read more →

Competitive Programming: POJ 2084 – Game of Connections

Description This is a small but ancient game. You are supposed to write down the numbers 1, 2, 3, . . . , 2n – 1, 2n consecutively in clockwise order on the ground to form a circle, and then, to draw some straight line segments to connect them into number pairs. Every number must be connected to exactly one another. And, no two segments are allowed to intersect. It’s still a simple game, isn’t it? But after you’ve written down the 2n numbers, can you tell me in how many different ways can you connect the numbers into pairs? Life is harder, right? Input Each line of the input file will be a single positive number n, except the last line, which is a number -1. You may assume that 1 < = n Read more →