Minimal Weight Paths

This problem was of the 2nd programming competition of Turabo's University.
Here is the description of the problem. Thanks to Luis Ojeda. He helped me in how to save the optimal values and the sum.

Given an m×n matrix of integers, you are to write a program that computes a path of
minimal weight from left to right across the matrix. A path starts anywhere in column
1 and consists of a sequence of steps terminating in column n. Each step consists of
traveling from column i to column i + 1 in an adjacent (horizontal or diagonal) row.
The first and last rows (rows 1 and m) of a matrix are considered adjacent; i.e., the
matrix “wraps” so that it represents a horizontal cylinder.



The weight of a path is the sum of the integers in each of the n cells of the matrix that
are visited.
The minimum paths through two slightly different 5 × 6 matrices are shown below.
The matrix values differ only in the bottom row. The path for the matrix on the right
takes advantage of the adjacency between the first and last rows.

Input
The input consists of a sequence of matrix specifications. Each matrix consists of the
row and column dimensions on a line, denoted m and n, respectively. This is followed
by m · n integers, appearing in row major order; i.e., the first n integers constitute the
first row of the matrix, the second n integers constitute the second row, and so on.
The integers on a line will be separated from other integers by one or more spaces.
Note: integers are not restricted to being positive. There will be one or more matrix
specifications in an input file. Input is terminated by end-of-file.
For each specification the number of rows will be between 1 and 10 inclusive; the
number of columns will be between 1 and 100 inclusive. No path’s weight will exceed
integer values representable using 30 bits.
11.6. Problems 261
Output
Two lines should be output for each matrix specification. The first line represents a
minimal-weight path, and the second line is the cost of this minimal path. The path
consists of a sequence of n integers (separated by one or more spaces) representing
the rows that constitute the minimal path. If there is more than one path of minimal
weight, the lexicographically smallest path should be output.

Sample Input
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10

Sample Output
1 2 3 4 4 5
16

1 2 1 5 4 5
11

1 2
19

Here is my solution in C#.

Vito's Family

This problem is from the book Programming Challenges. Here is the description of the problem.

The famous gangster Vito Deadstone is moving to New York. He has a very big
family there, all of them living on Lamafia Avenue. Since he will visit all his relatives
very often, he wants to find a house close to them.

Indeed, Vito wants to minimize the total distance to all of his relatives and has
blackmailed you to write a program that solves his problem.

Input
The input consists of several test cases. The first line contains the number of test cases.
For each test case you will be given the integer number of relatives r (0 < r < 500) and
the street numbers (also integers) s1 , s2 , . . . , si , . . . , sr where they live (0 < si < 30, 000).
Note that several relatives might live at the same street number.

Output
For each test case, your program must write the minimal sum of distances from the
optimal Vito’s house to each one of his relatives. The distance between two street
numbers si and sj is dij = |si − sj |.

Sample Input
2
2 2 4
3 2 4 6

Sample Output
2
4

Here is the solution of the problem in C#.
Another solution in Java.

Snail Matrix

This problem was of the 2nd competition of programming of turabo's university.

Description of the Problem: The problem will ask a even number to make a snail matrix. For example
a 4 * 4 snail matrix will be:

10 09 08 07
11 02 01 06
12 03 04 05
13 14 15 16

Then the program will ask the quadrant you want to see. The quadrants are 1, 2, 3, 4.

2 | 1
------
3 | 4

The program will run like this:

Please enter the number of rows: 4
Please enter the number of the quadrant you want to look: 1

08 07
01 05

Please enter the number of rows: 6
Please enter the number of the quadrant you want to look: 3


29 12 03
30 13 14
31 32 33

Here is my solution in C#

Tallest Indraneel's Pyramid

This problem was of the 2nd Programming Competitions of Turabo's university.
Problems Description:
Indraneel's Pyramid
Indraneel would like a build a pyramid of wooden blocks. A pyramid is built by placing a square block, say N cms by N cms, at the base, place another square block N-1 cms by N-1 cms on top of that, a square block of N-2 cms by N-2 cms on top of that and so on, ending with a 1 cm by 1 cm block on top. The height of such a pyramid is N.

Indraneel has with him M rectangular blocks of wood. He is willing to shape them into square blocks. His only cutting tool is a shaver that can be used to shave off the wood from any edge to reduce its length. This means that he can never get two square blocks from a single rectangular block.

For example, suppose the dimensions of the rectangular blocks available with Indraneel are 8×8, 2×8, 2×1 and 2×2. Then, he can build a pyramid of height 3 (the 2×1 block can be shaved to give a 1×1 block, and the 8×8 block can be shaved down to a 3×3 block.)

Given the dimensions of the blocks available, your task is determine the height of the tallest pyramid that Indraneel can build.

Input format

The first line of the input contains a single integer M indicating the number of blocks of wood available. This is followed by M lines of input (lines 2, 3,...,M+1) each containing the description of a block. A block is described by two integers i and j indicating the lengths of the two sides of the block. No block is longer or wider than 1000000 cms.

Output format

A single line with a single integer indicating the height of the tallest pyramid that Indraneel can build.

Test Data:

You may assume that M ≤ 1000000. Recall that all block dimensions are bounded by 1000000 cms.

Example:

Here is the sample input and output corresponding to the example discussed above.

Sample Input

4
8 8
2 8
2 1
2 2

Sample Output

3

My solution in C#

Jolly Jumpers

This problem was from the book Programming Challenges.
Here is the description of the problem:

A sequence of n > 0 integers is called a jolly jumper if the absolute values of the
differences between successive elements take on all possible values 1 through n − 1. For
instance,

1 4 2 3

is a jolly jumper, because the absolute differences are 3, 2, and 1, respectively. The
definition implies that any sequence of a single integer is a jolly jumper. Write a program
to determine whether each of a number of sequences is a jolly jumper.

Input
Each line of input contains an integer n < 3, 000 followed by n integers representing the
sequence.

Output
For each line of input generate a line of output saying “Jolly” or “Not jolly”.

Sample Input
4 1 4 2 3
5 1 4 2 -1 6

Sample Output
Jolly
Not jolly


Here is the Solution in C#
Another Solution in Java

Any sugestions and comments please write them. Thanks!

The Stern-Brocot Number System

This is a problem from the Programming Competitions of University of Puerto Rico at Bayamon.
The Stern-Brocot Number System

Here is the Problem Description
Here is the Source Code in C#

Any suggestions you can make please write them. Thanks

Welcome

In this blog I will talk about one of my passions which is computer programming. Soon I will upload my thesis called AJAX Efficiency so you can comment on it and some tips in programming languages. Later I will use this section to discuss music theory. Hope you like it!!!