Problem 1 - American vs. European Dates
---------------------------------------
You've just been hired on as a programmer for Amalgamated Calendar Makers
(ACM, for short). Since the Y2K crisis is over, your job is to tackle a
different date-related problem - the difference between U.S. and European
date formats.
In the U.S. most people write dates using three numbers: first the month,
then the day, and then the year. This is called "MM DD YYYY" format. For
example:
In the U.S. 03 07 2000 means March 7, 2000.
People in Europe also write dates using three numbers. However, most
Europeans write the *day* first, and then the *month*, and then the year.
This is called "DD MM YYYY" format. For instance:
In Europe 03 07 2000 means July 3, 2000.
Some dates (like "03 07 2000") are inherently ambiguous, but in most cases, a
date written in U.S. or European format simply doesn't make sense in the
other. For example, "03 13 2000" doesn't make sense as a European date
because 13 is not a valid month number. Similarly, "13 03 2000" doesn't make
sense as an American date. In cases like this, a computer program should be
able to tell that "03 13 2000" means March 13, 2000.
Your first job at ACM is to write a program that determines if an input date
must be in U.S. format, must be in European format, or could be in either
format.
Your program will input three numbers on a single line. These numbers will
represent a *valid* date in U.S. (MM DD YYYY) or European (DD MM YYYY)
format. The three numbers will be separated by spaces.
Your program must print one of the following words:
- "American" if the input date makes sense *only* in U.S. format;
- "European" if the input date makes sense *only* in European format;
- "Ambiguous" if the input date makes sense in *both* formats.
After printing the word, your program must print a newline character and then
quit. Do not print prompts or any information other than the single word.
Examples:
---------
Input: Input: Input:
03 13 2000 13 03 2000 07 04 1976
Output: Output: Output:
American European Ambiguous
Input: Input: Input:
07 24 1847 01 01 2000 31 12 1999
Output: Output: Output:
American Ambiguous European
Problem 2 - Screaming HTML
--------------------------
Anyone who uses computers very much knows that text written in all upper case
letters implies shouting and is generally considered to be extremely rude.
With that in mind, the Angry Cretan Maniacs (ACM, for short), a popular rock
group, has decided to update their web pages. Since this group isn't clever
enough to make the changes themselves, they hired you to do it for them.
For this problem you are to write a program for ACM that reads a line of
input and outputs the same line after replacing lower case text with upper
case and replacing periods with exclamation marks. It must leave HTML tags
alone, however. A tag consists of any text that begins with `<' and ends
with `>' (without the quotes). You may assume that neither `<' nor `>' will
appear within a tag or as part of text; they will always delineate a tag.
Do not print prompts or any information other than the single line of
translated HTML text.
Examples:
---------
Input:
Welcome to my web page.
Output:
WELCOME TO MY WEB PAGE!
Input:
Look at my bookmark page.
Output:
LOOK AT MY BOOKMARK PAGE!
Input:
Look at Me!
Output:
LOOK AT ME!
Input:
Welcome to the ACM page.
Output:
WELCOME TO THE ACM PAGE!
Input:
We have lots of good stuff here...
Output:
WE HAVE LOTS OF GOOD STUFF HERE!!!
Problem 3 - MP3 File Quality
----------------------------
The Augusta Conservatory of Musicians (ACM, for short) has recently started
using a MS-DOS based system to archive the work of local musicians. The
musicians record a variety of jazz, country, and religious music and then
submit it to ACM for archiving. ACM requested that all music be submitted in
MP3 files. (MP3 files use a sound compression scheme that can compress the
sound file by as much as 30:1.) Unfortunately, each musician used a
different level of compression when submitting the MP3 files. The Augusta
Chamber of Musicians has asked you to help classify the music.
You are to write a program that will take information about a recorded piece
of music and determine the Quality Measure of the file. Quality of a sound
file is determined by how many bits of information are stored for every
second of music. The following table lists the Quality Measures you will use.
quality value for MP3 file Quality Measure
-------------------------- ---------------
32,000 bits per second Phone quality
64,000 bits per second AM radio quality
96,000 bits per second LP record quality
128,000 bits per second FM radio quality
196,000 bits per second CD quality
256,000 bits per second Studio quality
Your program will input the size of the MP3 file (in kilobytes), and the time
for the music in minutes and seconds. It will then calculate a quality value
(bits per second) for the music file. Next, it will find the Quality Measure
for the file by determining which number in the table above is closest to the
calculated quality value. (In case of a tie, round to the lower Measure.)
Lastly, you will display the bits per second and Quality Measure.
Your program will first input three positive integers, with one space between
them and one return following the last number. The first integer is the size
of the music file in kilobytes, the second and third integers are the time
for the music in minutes and seconds (in that order).
Your program must then print out the number of bits per second for that MP3
file (rounded to the nearest integer, 0.5 rounds up), a comma, one space, and
its Quality Measure. Do not print prompts or anything other than the
required information. Be sure to use the same upper and lower case as
described above.
Remember that there are 1024 bytes in a kilobyte, and 8 bits in a byte. For
this problem sound files will be no larger than 100,000 kilobytes.
Example 1:
----------
Input:
3048 5 32
Output:
75208 bits per second, AM radio quality
Example 2:
----------
Input:
10245 32 1
Output:
43689 bits per second, Phone quality
Example 3:
----------
Input:
20084 12 8
Output:
226000 bits per second, Studio quality
(Note that for this example, the bit rate rounds to 226000 for output. This
is exactly half way between two quality measures, but the actual calculated
value, without rounding, is closer to the upper quality measure.)
Problem 4 - Where There's Smoke ...
-----------------------------------
There have been several lightning strikes in the Canadian forests lately, and
the Academie Canadien de Mounties (ACM, for short) has decided that they need
to be able to predict how large the lightning-caused forest fires would be
if left alone for a certain number of days. They have given you the job of
writing a program to do this.
Your program will simulate the behavior of a fire by dividing the forest into
a 2-dimensional grid of squares. Each lightning strike will occur at the
beginning of day 0 and each will be located in a unique square. The program
will make the following assumptions:
- forest fires spread from a currently burning square north, south, east
and west at a rate of one square each day
- forest fires do not spread diagonally
- after one day the fire in any square will go out
- a burned square will be destroyed and cannot catch fire again
- forests are no more than 30 squares in each direction
Input to the program will be the following on separate lines:
- the width (east-west) and height (north-south) of the forest
- the number of lightning strikes (no more than width*height)
- x and y coordinates for each lightning strike
- how many days to run the simulation
The x and y coordinates are the distance from the upper left corner of the
forest. The first input is the horizontal (east) distance, and the second is
vertical (south). The upper left square is at location 0 0.
Your program is to print the number of burning squares at the end of the
simulation. Do not print prompts, or any additional output other than a
single integer.
Here are some examples. The first two include maps to help you see what is
going on and should not be output by your program.
Example 1:
----------
Input:
5 5
1
2 2
1
Output:
4
For this example, here's what the map would look like after 1 day:
.....
..*.. * = fire
.*_*. . = tree
..*.. _ = dead
.....
Example 2:
----------
Input: map after 2 days:
7 5
3 __*....
0 0 _**....
5 4 **_*.*.
2 3 *___*_*
2 .*_*___
Output:
12
Example 3:
----------
Input:
30 30
10
25 11
23 23 you'll have to trust us on this one
27 5 (or you draw the map)
10 23
8 16
14 18
10 15
28 27
19 21
4 18
4
Output:
105
Problem 5 - What To Do Next???
------------------------------
AAA Cold Medication, Inc. (ACM, for short) is in a fix - their production
manager just quit and they don't know what they are going to do. They have
several milestones to meet before they can release their final product, but
they've lost all of the notes on what order to do them in!
That's where you come in. Given a list of milestones (up to 26, named A-Z),
and which other milestone(s) need to be done before you can finish each one
of them, you are to write a program that helps ACM out by giving them a
prioritized list. Your output should be a list of milestones such that each
milestone appears sometime after the milestone(s) on which it depends; i.e.,
each one is listed after any milestone(s) that must be completed before it.
There will always be at least one solution. Milestones will never depend on
each other in a loop. There may be multiple solutions, but you only need to
find one.
Input will be in the following form:
# of milestones
...
...
.
.
.
Output will be a list of upper case letters with spaces between them and then
a return. Each milestone must appear exactly once in your output list.
Example 1:
----------
Input:
3
A 0
B 2 C A
C 1 A
Output:
A C B
Example 2:
----------
Input:
6
A 0
B 2 A F
C 2 D B
D 3 A B F
E 2 F C
F 0
Output:
A F B D C E
Example 3:
----------
Input:
10
A 2 E J
B 4 E A C H
C 1 A
D 3 C E A
E 1 J
F 3 B H A
G 0
H 2 A E
I 5 A C E J F
J 0
Output:
G J E A C H B D F I