Since the elevators in Wean are slow and unreliable, many students prefer
to use the stairs. When a student walks upstairs, he can occasionally jump
across two or three steps, which means that he may climb stairs in many
different ways. For example, if the stairs consist of two steps, the student
has two options: (1) take the first step and then take the second step
or (2) jump the two steps at once. If the stairs include four steps, then
he has seven options: (1) one step, one step, one step, one step; (2) one
step, one step, two steps; (3) one step, two steps, one step; (4) two steps,
one step, one step; (5) two steps, two steps; (6) one step, three steps;
and (7) three steps, one step. Your task is to determine the total number
of ways to climb a given number of steps.
Input
The input includes multiple test cases; the number of cases is at most
26. Each test case is an integer between 1 and 26, on a separate line with
no surrounding spaces, which represents the number of steps. The last line
of the input is "-1", which does not represent a test case.
Output
For each test case, the output is a single integer on a separate line,
which represents the number of ways to climb the stairs.
Sample input
1
2
3
4
-1
Sample output
1
2
4
7
Problem B: Edit Distance
When a word processor suggests a replacement for a misspelled word, it
usually uses the edit distance to determine the closest word. The
edit distance between two words is the minimal number of point mutations
required for converting one word into the other, where each point mutation
is one of three operations: insert a new letter, delete a letter, or replace
a letter with a different letter. For example, we can convert "editing"
into "distance" using five point mutations, which means that the edit distance
between these words is five:
editing diting disting distang distanc distance
Your task is to write a program that computes the edit distance between
given words.
Input
The input is a list of word pairs, one pair per line; the words in a pair
are separated by a single space. Each word is a string of lower-case letters,
the length of which is between one and thirty; note that these strings
may not be valid English words. The total number of pairs is at most 10,000;
the last line is "end end", which does not represent a word pair.
Output
The output shows the edit distance for each word pair, one distance per
line.
Sample input
editing distance
distance editing
edit distance
edit edit
end end
Sample output
5
5
6
0
Problem C: Stock Prices
When traders analyze the historic performance of a stock, they may look
at its performance history; this history is a sequence of prices
that represent the stock's end-day values since the first day of its trading.
For example, the sequence "$3.00, $2.50, ..." shows that the stock's price
after the first day of its trading was $3.00, the price after the second
day was $2.50, and so on. This price may go up and down, depending on the
company's performance and on the investors' interest in this company. The
drawdown
of a stock is the reduction of its price between two specific days; for
instance, if its price on January 1 is $4.00, and its price on February
1 is $2.00, then the drawdown between these two days is $2.00. When traders
evaluate a stock, they may compute its greatest drawdown, that is,
the maximal historic reduction of its price. Your task is to write a program
that computes the greatest drawdown.
Input
The input is a list of prices, one price per line, which represent a stock's
performance history; each price is between 0.01 and 1000000.00. We represent
a price by a real value with exactly two digits after the decimal point.
Note that we include these two digits even if they are zeros; for instance,
we represent five dollars as $5.00 rather than $5. The total number of
lines in the input file is at most 1,000,000; the last line is "0.00",
which does not represent a price.
Output
The output is a single real value, with exactly two digits after the decimal
point, that represents the greatest drawdown in the stock's history. If
the stock prices are monotonically increasing, then the stock has no drawdowns,
and the output is 0.00.
Example input
3.00
2.50
4.00
2.00
2.00
1.50
3.00
Example output
2.50
Disclaimer
The financial terminology in this problem is slightly inaccurate, for the
purpose of simplifying the underlying scenario. In particular, we usually
apply the concept of drawdown to stock portfolios or mutual funds, rather
than to individual stocks.