Hi everybody, I make my official webpage. Hope you visit it and make it one of your favorites. It is going to have tutorials, and my new blog. Hope you like it. Remember www.josecartagena.info
Thursday, May 6, 2010
Thursday, March 4, 2010
Hi everybody
I know these days I'm not posting so much it is because I'm working in an investigation and some other things. Hope you continue visiting my blog because later I will keep posting some programming tips and problems.
Sunday, November 15, 2009
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.
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++.
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#.
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.
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.
Friday, November 13, 2009
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.
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.
Subscribe to:
Posts (Atom)
