The university administration has decided to install several slot machines
in the university center, which are called Casino Machines for Universities
(CMUs). This machines are similar to the usual casino
slot machines, but the gambling is based on various science facts. In particular,
one machine allows students to bet on the number of primes in a specified
interval. After a student drops a quarter into this machine, it displays
an interval of integers, and the student has to guess the number of primes
in this interval. If her guess is larger than the correct answer, she loses;
if her guess is an underestimate, she gets back her quarter; finally, if
her guess is right, she wins a T-shirt with the slogan "Gamble less, study
more." Your task is to write a program that verifies the correctness of
guesses.
Input
The input is a list of games, one game per line; the description of a game
includes three integers, separated by single spaces. The first two integers
are the beginning and end of an interval; these integers are between 2
and 1,000,000, and the first of them is no greater than the second. The
third integer is a student's guess about the number of primes in this interval,
which is between 0 and 100,000. The total number of games is at most 1,000,000;
the last line is "0 0 0", which does not represent a game.
Output
The output shows the outcome of each game, one outcome per line. If the
guess is greater than the correct answer, the outcome is "loss";
if it is less than the correct answer, the outcome is "draw"; finally,
if it is correct, the outcome is "win".
Sample input
2 2 1
4 4 0
2 5 2
2 6 4
0 0 0
Sample output
win
win
draw
loss
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.