3n + 1

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

Consider the following algorithm to generate a sequence of numbers. Start with an
integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this
process with the new value of n, terminating when n = 1. For example, the following
sequence of numbers will be generated for n = 22:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for
every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000.

For an input n, the cycle-length of n is the number of numbers generated up to and
including the 1. In the example above, the cycle length of 22 is 16. Given any two
numbers i and j, you are to determine the maximum cycle length over all numbers
between i and j, including both endpoints.

Input
The input will consist of a series of pairs of integers i and j, one pair of integers per
line. All integers will be less than 1,000,000 and greater than 0.

Output
For each pair of input integers i and j, output i, j in the same order in which they
appeared in the input and then the maximum cycle length for integers between and
including i and j. These three numbers should be separated by one space, with all three
numbers on one line and with one line of output for each line of input.

Sample Input
1 10
100 200
201 210
900 1000

Sample Output
1 10 20
100 200 125
201 210 89
900 1000 174

Here is the solution in C++.
Another solution in Perl.
Another solution in Python.

The Trip

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

A group of students are members of a club that travels annually to different lo-
cations. Their destinations in the past have included Indianapolis, Phoenix, Nashville,
Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.

The group agrees in advance to share expenses equally, but it is not practical to share
every expense as it occurs. Thus individuals in the group pay for particular things, such
as meals, hotels, taxi rides, and plane tickets. After the trip, each student’s expenses
are tallied and money is exchanged so that the net cost to each is the same, to within
one cent. In the past, this money exchange has been tedious and time consuming. Your
job is to compute, from a list of expenses, the minimum amount of money that must
change hands in order to equalize (within one cent) all the students’ costs.

Input
Standard input will contain the information for several trips. Each trip consists of a
line containing a positive integer n denoting the number of students on the trip. This is
followed by n lines of input, each containing the amount spent by a student in dollars
and cents. There are no more than 1000 students and no student spent more than
$10,000.00. A single line containing 0 follows the information for the last trip.

Output
For each trip, output a line stating the total amount of money, in dollars and cents,
that must be exchanged to equalize the students’ costs.

Sample Input
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

Sample Output
$10.00
$11.99

Here is my solution in C++.

Common Permutation

This problem is from the book Programming Challenges. Here is the problem's description.

Given two strings a and b, print the longest string x of letters such that there is a
permutation of x that is a subsequence of a and there is a permutation of x that is a
subsequence of b.

Input
The input file contains several cases, each case consisting of two consecutive lines. This
means that lines 1 and 2 are a test case, lines 3 and 4 are another test case, and so on.
Each line contains one string of lowercase characters, with first line of a pair denoting
a and the second denoting b. Each string consists of at most 1,000 characters.

Output
For each set of input, output a line containing x. If several x satisfy the criteria above,
choose the first one in alphabetical order.

Sample Input
pretty
women
walking
down
the
street

Sample Output
e
nw
et

Here is my solution in C#.

Minesweeper

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

Have you ever played Minesweeper? This cute little game comes with a certain op-
erating system whose name we can’t remember. The goal of the game is to find where
all the mines are located within a M × N field.

The game shows a number in a square which tells you how many mines there are
adjacent to that square. Each square has at most eight adjacent squares. The 4 × 4 field
on the left contains two mines, each represented by a “*” character. If we represent the
same field by the hint numbers described above, we end up with the field on the right:
*...
....
.*..
....

*100
2210
1*10
1110

Input
The input will consist of an arbitrary number of fields. The first line of each field
contains two integers n and m (0 < n, m ≤ 100) which stand for the number of lines
and columns of the field, respectively. Each of the next n lines contains exactly m
characters, representing the field.

Safe squares are denoted by “.” and mine squares by “*,” both without the quotes.
The first field line where n = m = 0 represents the end of input and should not be
processed.

Output
For each field, print the message Field #x: on a line alone, where x stands for the
number of the field starting from 1. The next n lines should contain the field with the
“.” characters replaced by the number of mines adjacent to that square. There must
be an empty line between field outputs.


Here is my solution in C#.
Another solution in C++.
Another solution in Python.

Stacks of Flapjacks

This problem appeared in University of Puerto Rico at Bayamon Programming Competitions.
Here is the description of the problem:

Cooking the perfect stack of pancakes on a grill is a tricky business, because no matter
how hard you try all pancakes in any stack have different diameters. For neatness’s sake,
however, you can sort the stack by size such that each pancake is smaller than all the
pancakes below it. The size of a pancake is given by its diameter.

Sorting a stack is done by a sequence of pancake “flips.” A flip consists of inserting
a spatula between two pancakes in a stack and flipping (reversing) all the pancakes on
the spatula (reversing the sub-stack). A flip is specified by giving the position of the
pancake on the bottom of the sub-stack to be flipped relative to the entire stack. The
bottom pancake has position 1, while the top pancake on a stack of n pancakes has
position n.

A stack is specified by giving the diameter of each pancake in the stack in the order
in which the pancakes appear. For example, consider the three stacks of pancakes below
in which pancake 8 is the top-most pancake of the left stack:
8 7 2
4 6 5
6 4 8
7 8 4
5 5 6
2 2 7
The stack on the left can be transformed to the stack in the middle via flip(3). The
middle stack can be transformed into the right stack via the command flip(1).

Input
The input consists of a sequence of stacks of pancakes. Each stack will consist of between
1 and 30 pancakes and each pancake will have an integer diameter between 1 and 100.
The input is terminated by end-of-file. Each stack is given as a single line of input with
the top pancake on a stack appearing first on a line, the bottom pancake appearing
last, and all pancakes separated by a space.

Output
For each stack of pancakes, your program should echo the original stack on one line,
followed by a sequence of flips that results in sorting the stack of pancakes so that the
largest pancake is on the bottom and the smallest on top. The sequence of flips for each
stack should be terminated by a 0, indicating no more flips necessary. Once a stack is
sorted, no more flips should be made.

Sample Input
1 2 3 4 5
5 4 3 2 1
5 1 2 3 4

Sample Output
1 2 3 4 5
0
5 4 3 2 1
1 0
5 1 2 3 4
1 2 0
Here is the solution of the problem.
Another solution in Java.

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!!!