York programming contest 2002
October 25, 2002
Rules:
-
There are 3 members per
team. You will be given one computer per team.
-
There are FIVE questions
to be completed in 180 minutes.
-
The allowed programming
languages are C, C++, Java.
-
You are not allowed to
talk or communicate by any electronic means to anyone other than your team
members during the contest.
-
You may not use code written
by anyone (including you) prior to the contest. The only exception to this
rule is code that you have brought in as a hard copy BEFORE the contest
begins.
-
If you are caught violating
the above rules, you will be automatically disqualified.
-
You may bring books or
other printed material if you like.
-
Input/Output format
rules:
-
All questions require
you to read the test data from standard input and write results to standard
output. You cannot use files for input or output.
-
No whitespace should appear
at the end of a line, and all lines should be terminated with a new-line.
-
Tabs should never be used.
-
Output must correspond
exactly to the provided sample output, including (mis)spelling and spacing.
Multiple spaces will not be used in any of the judges' output, except where
expressly stated.
-
All programs will be re-compiled
prior to testing with the judges' data.
-
Non-standard libraries
cannot be used in your solutions. The Standard Template Library (STL) and
C++ string libraries are allowed.
-
Programming style is not
considered in this contest. You are free to code in whatever style you
prefer. Documentation is not required.
-
Each solution is given
limited CPU time and memory to run for each input file.
-
Submitting solutions: Your
program for problem x should be called x.c (C program) or x.java (Java
program) or x.cc (C++ program).
-
Please submit your solution
for problem y in the following format:
submit acm y y.; e.g. submit acm A A.c
-
You should be able to see
the online scoreboard at http://www.cs.yorku.ca/acm/contest/
Problem
A: A display problem
An old Geology professor
has bought his first computer with a fancy monitor. Being computer illiterate
and short-sighted, he cannot think of a better use for his computer than
to have it display a large clock. He wants you to write a program that
does this. Being a smart programmer, you realize how hard it is to display
an analog clock. So you convince the professor that your clock should look
like the LED-display of his 1971 alarm clock. For this problem, you will
write the part of the clock program that displays numbers in an LED-display-like
style on his computer.
Input
The input
contains several lines, one for each number to be displayed. Each line
contains two integers s, n (1 <= s <= 10; 0 <= n <= 99 999
999), where n is the number to be displayed and s is the size in which
it shall be displayed. The input will be terminated by a line containing
two zeros. This line should not be processed.
Output
Output
the numbers given in the input in an LED-display-style using s "-" signs
for the horizontal segments and s "|" signs for the vertical ones. Each
digit occupies exactly s + 2 columns and 2s + 3 rows. (Be sure to fill
all the white space occupied by the digits with blanks, also for the last
digit.) There has to be exactly one column of blanks between two digits.
Output a blank line after each
number.
You will find a sample of each digit in the sample output.
Sample Input
2 12345
3 67890
0 0
Sample Output
-- -- --
| | | | | |
| | | | | |
-- -- -- --
| | | | |
| | | | |
-- -- --
--- --- --- --- ---
| | | | | | | |
| | | | | | | |
| | | | | | | |
--- --- ---
| | | | | | | |
| | | | | | | |
| | | | | | | |
--- --- ---
Problem B: The professor's dream
The professor had a dream. In the dream, he was the chief scientist for
a Roman emperor. The professor's job is to choose locations of forts to
guard cities in the empire.
The professor knows that cities are labeled in uppercase letters in
alphabetical order, starting with A. Also, there is exactly one path between
any given pair of cities. For example, in the figure below, The path from
J to B passes through C, G and F.
J ----------- C -------------A -------------- D
|
|
|
I ------------G ------------ F -------------B ----------E
| |
| |
| |
H K
The professor wants you to write a program to solve the problem he dreamt
about. You may assume that distance between cities is measured in hops.
E.g., the distance between J and C is 1 and the distance between J and
B is 4. Initially only one of the cities is fortified. Your program will
add k more forts, where k will be specified in the input. The rules governing
addition of forts is given as follows:
-
If a city is not fortified, it is said to be vulnerable. Further, its degree
of vulnerability is the distance between it and the nearest fortified city.
-
When one or more cities have been fortified, the location of an additional
fort is chosen to be the city with the highest degree of vulnerability.
Ties are broken by choosing the alphabetically first city.
Input
The first line consists of three items
-
The total number of cities n, 3 <= n <= 26.
-
An uppercase letter in the valid range of cities, denoting the city initially
fortified.
-
The total number of cities to be fortified, including the initially fortified
one. This will be at least 3 and no more than the number of cities.
The remaining lines specify the connections between cities. Each line has
2 uppercase letters denoting direct connections between cities.
You may assume that all lines of input will be free of leading or trailing
blanks.
Output
The output will list the cities to be fortified in uppercase letters in
the correct order. The uppercase letters should be separated by one blank
space. There should be no blank lines or leading blank spaces.
Sample Input
The sample input below is for the cities shown above:
11 J 5
A D
B E
F B
C G
F G
C A
G H
G I
J C
K F
Sample Output
J E D H K
Problem
C: The surveying problem
Our professor is fascinated by your solution to the previous problems,
and now suspects that the computer can solve certain other problems he
has. So he asks you to solve the following problem. The professor is looking
at aerial photos of a city (hardcopies) and is trying to find out the total
area covered by parks in the city. You are careful not to tell him that
such a quantity can be computed accurately by using the digitized photograph.
Instead, you tell him that you can compute the areas of the parks (which
are all rectangles) if the professor gives you a list of rectangles.
Input
The input
consists of several test cases. Each test case starts with a line containing
a single integer n (1 <= n <= 100) of available parks. The n following
lines describe one park each. Each of these lines contains four numbers
x1, y1, x2, y2 (0 <= x1 < x2 <= 100 000, 0 <= y1 < y2 <=
100 000), not necessarily integers. The values (x1, y1) and (x2, y2) are
the coordinates of the top-left (respectively bottom-right corner of the
park. The input is terminated by a line containing a single 0. Don't process
it.
Output
For each
test case, your program should output one section. The first line of each
section must be ``Test case #k'', where k is the number of the test case
(starting with 1). The second one must be ``Total explored area: a'', where
a is the total explored area (i.e. the area of the union of all rectangles
in this test case), printed exact to two digits to the right of the decimal
point.
Output a blank line after each test case.
Sample Input
2
10 10 20 20
15 15 25 25.5
0
Sample Output
Test case #1
Total explored area: 180.00
Problem
D: The Professor's first game
The
professor has seen you play a video game when he came to you for help with
yet another problem and he is interested! So you recommend a strategy game
for him. In this game, the player has to defend a medieval city, the roads
of which form a tree. He has to put the minimum number of soldiers on the
nodes so that they can observe all the edges. The professor is catching
on fast and realizes that you can write a program for him that computes
the answer which he can use to win this game!
Your program should find
the minimum number of soldiers that the professor has to put for a given
tree.
The input contains several data sets in text
format. Each data set represents a tree with the following description:
·the
number of nodes
·the
description of each node in the following format
node_identifier:(number_of_roads)
node_identifier1 node_identifier2 ... node_identifiernumber_of_roads
or
node_identifier:(0)
The
node identifiers are integer numbers between 0and n-1,
for n
nodes (0 < n <= 1500). Every edge appears only once in the
input data.
For example for the tree:
the solution is one soldier
( at the node 1).
The output
should be printed on the standard output. For each given input data set,
print one integer number in a single line that gives the result (the minimum
number of soldiers).
Sample Input and
Output
An example is given in
the following table:
Input
|
Output
|
|
4
0:(1)
1
1:(2)
2 3
2:(0)
3:(0)
5
3:(3)
1 4 2
1:(1)
0
2:(0)
0:(0)
4:(0) |
1
2
|
Problem
E: The Professor's loose change
Our professor is really enjoying making you solve sundry problems.
He notices loose change jingling in his pockets one day and thinks about
how one makes change in real-life. He realizes that there are many ways
of making change for a certain amount. For example, suppose there are 5
types of coins: 50-cent, 25-cent, 10-cent, 5-cent, and 1-cent. If we want
to make changes with these coins for, say, 11 cents, then we can make changes
with one 10-cent coin and one 1-cent coin, two 5-cent coins and one 1-cent
coin, one 5-cent coin and six 1-cent coins, or eleven 1-cent coins. So
there are four ways of making changes for 11 cents with the above coins.
Note that we count that there is one way of making change for zero cent.
The professor wants you to write a program to find the total number
of different ways of making changes for any amount of money in cents. Your
program should be able to handle up to 7488 cents.
Input
The input contains n, the number of lines, followed by n lines, each one
consisting of a number for the amount of money in cents.
Output
For each input line, output a line containing the number of different ways
of making changes with the above 5 types of coins.
Sample Input
2
11
26
Sample Output
4
13