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 →
EppsNet Archive: Competitive Programming
Competitive Programming: POJ 1159 – Palindrome
Description A palindrome is a symmetrical string, that is, a string read identically from left to right as well as from right to left. You are to write a program which, given a string, determines the minimal number of characters to be inserted into the string in order to obtain a palindrome. As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome. Input Your program is to read from standard input. The first line contains one integer: the length of the input string N, 3 <= N <= 5000. The second line contains one string with length N. The string is formed from uppercase letters from ‘A’ to ‘Z’, lowercase letters from ‘a’ to ‘z’ and digits from ‘0’ to ‘9’. Uppercase and lowercase letters are to be considered distinct.… 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 1426 – Find The Multiple
Description Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits. Input The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input. Output For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable. Sample Input 2 6 19 0 Sample Output 10 100100100100100100 111111111111111111 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 Read more →
Competitive Programming: USACO Big Barn
Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis. EXAMPLE Consider the following grid of Farmer John’s land where ‘.’ represents a parcel with no trees and ‘#’ represents a parcel with trees: 1 2 3 4 5 6 7 8 1 . . . . . . . . 2 . # .… Read more →
Competitive Programming: POJ 1654 – Area
Description Consider an infinite full binary search tree (see the figure below), the numbers in the nodes are 1, 2, 3, …. In a subtree whose root node is X, we can get the minimum number in this subtree by repeating going down the left node until the last level, and we can also find the maximum number by going down the right node. Now you are given some queries as “What are the minimum and maximum numbers in the subtree whose root node is X?” Please try to find answers for the queries. Input In the input, the first line contains an integer N, which represents the number of queries. In the next N lines, each contains a number representing a subtree with root number X (1 Read more →
Competitive Programming: POJ 2242 – The Circumference of the Circle
Description To calculate the circumference of a circle seems to be an easy task – provided you know its diameter. But what if you don’t? You are given the cartesian coordinates of three non-collinear points in the plane. Your job is to calculate the circumference of the unique circle that intersects all three points. Input The input will contain one or more test cases. Each test case consists of one line containing six real numbers x1,y1,x2,y2,x3,y3, representing the coordinates of the three points. The diameter of the circle determined by the three points will never exceed a million. Input is terminated by end of file. Output For each test case, print one line containing one real number telling the circumference of the circle determined by the three points. The circumference is to be printed accurately rounded to two decimals. The value of pi is approximately 3.141592653589793. Sample Input 0.0 -0.5… Read more →