|
|
NOI 2003 TASKS
| |
Overview (Word format)
Task Statements (Postscript format)
|
|
Overview |
| |
Executable file |
Input file |
Output file |
Maximum execution time |
| Task 1: FILTER |
FILTER.EXE |
FILTER.IN |
FILTER.OUT |
5 seconds |
| Task 2: BLOCK |
BLOCK.EXE |
BLOCK.IN |
BLOCK.OUT |
5 seconds |
| Task 3: COIN |
COIN.EXE |
COIN.IN |
COIN.OUT |
5 seconds |
| Task 4: TRIANGLE |
TRIANGLE.EXE |
TRIANGLE.IN |
TRIANGLE.OUT |
5 seconds |
| Task 5: COMPRESS |
COMPRESS.EXE |
COMPRESS.IN |
COMPRESS.OUT |
5 seconds |
| Task 6: LABEL |
LABEL.EXE |
LABEL.IN |
LABEL.OUT |
15 seconds |
Notes:
- Each task will be tested on 5 data sets.
- Each data set is worth 20 points.
- Either zero mark or full mark (20 points) is awarded
to your answer to each data set. There is
no partial credit.
- The task statements are contained on 12 pages
following this overview page.
- In the event of tie breaking, a bigger-numbered task
is favoured over a smaller-numbered one.
|
|
|
Task 1: FILTER |
The median of 9 numbers is the fifth number when the numbers
are arranged in either increasing or decreasing order.
For example, the median of the 9 numbers 1, 3, 4, 1, 2, 6,
8, 4, 10 is 4 because 1 <= 1 <= 2 <= 3 <=
4 <= 4 <= 6 <= 8 <= 10.
An image I is a two dimensional R × C
array of pixels, 3 <= R <= 40,
3 <= C <= 40. A pixel has an integer
grey level value V, 0 <= V <= 255.
Median filter is an image processing operation to
remove noise. The filter can be implemented by moving
a 3 × 3 window over the image and finding the
median of the 9 pixel values covered by the 3 × 3
window.
For example, given the 6 × 5 image
the 4 × 3 filtered image is
You can easily check that as the 3 × 3 window
moves along the top row from left to right, the three
window contents are as shown below (the boundaries of the
3 × 3 window are shown via thick lines)
The corresponding medians for these positions of the
3 × 3 windows are 36, 36 and 21 respectively;
hence they constitute the top row of the filtered
image J. The pixel values of the other rows
of the filtered image J can be found similarly.
Write a program to output an integer which is the
number of pixels in the filtered image J whose
values are greater than or equal to a threshold T.
For the threshold T = 40, the program should
output 7 for the above example because there are 7
pixels in the filtered image J whose values are
larger than or equal to T.
Input
The input file FILTER.IN consists of R + 2
lines. The first line contains the two integers R
(the number of rows) and C (the number of columns)
separated by a blank. The subsequent R lines
contain the image: each line contains C pixel values,
with a single blank between two adjacent pixel values.
The last line contains the single integer T, the
threshold value.
Output
The output file FILTER.OUT contains a single integer,
which is the number of pixels in the filtered image
J whose values are larger than or equal to the
threshold.
Sample Input 1.
3 3
3 4 6
3 1 9
1 9 10
4
Sample Output 1.
1
Sample Input 2.
6 5
49 36 73 62 21
27 88 14 11 12
99 18 36 91 21
45 96 72 12 10
12 48 49 75 56
12 15 48 86 78
40
Sample Output 2.
7
|
|
|
Task #1 Input files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
Task #1 Output files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
|
Task 2: BLOCK |
You are given a two-dimensional r × c
arrangement of blocks of six different colors. The
arrangement consists of up to 100 rows and up to 100
columns. That is, 1 <= r <= 100 and
1 <= c <= 100. The colors are represented
by the letters A, B, C, D, E, and F. The blocks always
drop as far down as possible until they hit the ground.
Once the blocks sit still, they may eliminate each other
as follows. Consider two blocks to be adjacent, if
they are either side by side or one on top of another.
Each time the blocks sit still, the area of adjacent
blocks of the same color with the biggest number of
blocks in it will vanish. If there are several areas
with the same biggest number of adjacent blocks, all
these areas will vanish.
After they vanish, other blocks may drop down, and
a new area of blocks can vanish.
Given a starting arrangement of blocks, you need to
find out the number of blocks left when no blocks
vanish any more.
Example 1. With the starting arrangement
C
B A
B C
C B
the blocks will first drop, to yield the arrangement
C A
B C
C B B
Then, the area containing the color B will vanish,
leading to the arrangement
C A
C
C
which will make some blocks drop again,
yielding the arrangement
A
C C C
Finally, the area with color C will vanish, and the only
remaining block (which has color A) will drop.
Therefore, the answer is 1.
Example 2. In this example, we start with
the arrangement
C B B D
C C D D
C D
B B B B
After the blocks drop, we get
D
C B B D
C C D D
B C B B B
Note that now, there are two consecutive areas with the
biggest number of blocks, namely the area with color C
and the area with color D. Both will vanish, leading
(after the blocks drop) to
B
B B B B B
All these blocks vanish, leaving no blocks in the
arrangement. Thus the answer is 0.
Input
The input file BLOCK.IN consists of r + 1
lines where r is the number of rows in the starting
arrangement. The first line consists of the two numbers
r and c separated by a blank, where c
is the number of columns of the arrangement. Each of the
following r lines contains c characters
representing the colors of the blocks in the respective
row and column. Empty slots are indicated by the letter
X.
For instance, the file for the starting arrangement of
Example 1 above looks like this:
4 3
XCX
XBA
XBC
CXB
Output
The output file BLOCK.OUT contains an integer
which is the number of remaining blocks in the final
arrangement. For instance, the output file for
Example 1 above contains the integer:
1
|
|
|
Task #2 Input files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
Task #2 Output files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
|
Task 3: COIN |
There are k different coin denominations, that is,
there are k types of coins, 1 <= k <= 20.
Each coin denomination i has a monetary value
vi cents, 1 <= i <=
k. Without loss of generality, we assume
v1 <
v2 < ... <
vk.
For a given amount M, 0 <= M <= 500,
we would like to find the number of distinct ways to
form the amount of M cents.
You can assume an infinite supply of coins for each
denomination.
Example 1. If the k = 4 coin denominations
are
v1 = 10 cents,
v2 = 20 cents,
v3 = 50 cents, and
v4 = 100 cents,
there are 4 ways to form the amount of M = 50
cents: (50), (10,20,20), (10,10,10,20), and
(10,10,10,10,10).
Example 2. If the k = 3 coin denominations
are
v1 = 30 cents,
v2 = 70 cents, and
v3 = 80 cents,
there are 2 ways to form the amount of M = 200
cents: (30,30,30,30,80) and (30,30,70,70).
Input
The input file COIN.IN consists of 3 lines.
The first line contains the integer k.
The second line contains the k integer coin
denomination values sorted in increasing order,
with a blank between two adjacent values.
The third line contains the integer M.
Referring to Example 1 above, the input file looks
like:
4
10 20 50 100
50
Output
The output file COIN.OUT contains a single integer
which is the number of ways to form the amount of
M cents.
Referring to Example 1 above, the output file looks
like:
4
|
|
|
Task #3 Input files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
Task #3 Output files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
|
Task 4: TRIANGLE |
Let T0,0 be a triangle.
Draw an edge between the middle point of the longest
edge of T0,0 and the opposite vertex
(if there are two or three edges of maximum length, just
choose any of them; this will not change the final result
of this problem). This splits T0,0
into two smaller triangles T1,0 and
T1,1 (see first two trangles in
figure below). We then apply the same process to
T1,0 and T1,1
and obtain four triangles
T2,0,
T2,1,
T2,2 and
T2,3.
When we repeat this process indefinitely for all integer
i, it produces an infinite number of triangles
Ti,j with
j in {0, 1, ..., 2i - 1}.
These triangles take only a finite number of different
shapes. The goal of this problem is to write a program
that counts the number of these different shapes.
For any triangle T, let
l1( T ) <=
l2( T ) <=
l3( T )
be the lengths of its three edges. We say that two
triangles T and T' are similar
if and only if it is true that
l1( T ) /
l1( T' ) =
l2( T ) /
l2( T' ) =
l3( T ) /
l3( T' ) .
Otherwise, T and T' are not similar.
A similarity class gathers all the triangles
that are similar to a particular triangle T.
For instance, equilateral triangles (triangles whose
three edges have the same length) form a similarity
class.
Your program will have have to count the number of
different similarity classes that appear while
subdividing the input triangle T0,0.
This includes the similarity class of
T0,0 itself. For instance, if the
input triangle T0,0 is equilateral,
the number of similarity classes that will appear is
3 (see example below).
In order to use only integers, the input triangles
T0,0 has the following property.
For all (i, j), the three numbers
2i
(l1 (Ti,j)
)2,
2i
(l2 (Ti,j)
)2 and
2i
(l3 (Ti,j)
)2 are integers between 1 and 16000.
A consequence of this assumption is that the length of
the longest edge of T0,0 is an even
integer (see below).
You may also need the following result. Consider a triangle
ABC. Let M be the middle point of BC.
Then
2AM2 = AB2 +
AC2 - BC2 / 2.
Example. If the input triangle is equilateral,
only three similarity classes appear. Any triangle
Ti,j is similar to
one of the three shaded triangles in the picture below.
So in this case, the answer to the problem is 3.
Input
The input file TRIANGLE.IN contains three integers,
with a blank between two adjacent integers. They
represent the lengths of the edges of T0,0
in non-decreasing order. For instance, if the input
triangle is an equilateral traingle whose edges are of
length 12, the input will be
12 12 12
Output
The output file TRIANGLE.OUT contains an integer
which is the number of similarity classes that appear
while subdividing T0,0 indefinitely.
This includes the class of T0,0.
For instance, for the above input file, the output
file contains the integer
3
|
|
|
Task #4 Input files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
Task #4 Output files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
|
Task 5: COMPRESS |
In this task, we study the issue of rule-based
representation for the compression of very long strings
of lower case English letters a, b, ...,
z. Each string is represented by a set of rules.
Each rule has two parts, henceforth called left-hand side
(lhs) and right-hand side (rhs). The lhs of each rule
is a distinct upper case letter, i.e. any upper-case
letter in the representation appears in the lhs of
exactly one rule. The rhs of each rule is a string of
upper and lower case letters. An application of a rule
is the replacement of its lhs by its rhs. One of the
upper case letters is distinguished as the start symbol
S. When a string is represented by a set of
rules R, then we always get the string
from the symbol S by applying the rules of
R repeatedly (until no rule can be applied).
For example, the following two rules form a valid
representation of the string abcabc
S -> BB
B -> abc
Starting from S, we can use rule 1 to rewrite
S to BB. We then use rule 2 twice to
rewrite BB to abcabc. Clearly, there can
be several rule-based representations of the same string.
For example,
S -> aCaC
C -> bc
is another rule-based representation of the string
abcabc.
In the interests of compression, we require the rule-based
representation of any string to satisfy the following
properties.
- Any pair of adjacent letters (upper or lower case)
appearing in the rhs of any rule is unique, i.e.
it appears only once in all the rules.
This prevents us from representing abcabc
using the two rules S -> XcXc,
X -> ab, because Xc appears
twice in the first rule.
- Except the start symbol (S), every
upper-case letter must appear in the right-hand
sides of the rules at least twice.
This prevents
us from representing the string ab using
the two rules S -> aB,
B -> b, since B appears in
rhs only once.
Given an input string, your program should process the
string character-by-character from left to right to
produce a rule-based compressed representation satisfying
the above properties. You should do this in an iterative
fashion, i.e.
- read in the next character from the input string;
- append the character read to the end of the rule
containing S (the start symbol);
- check whether properties 1 and 2 are satisfied
in the resultant rules; if not, then repeatedly
insert/delete rules to satisfy properties 1 and 2.
For example, the rules representing the string
abcab are
S -> XcX
X -> ab
Now, if the next character is c (i.e. we consider
the string abcabc) then we get
S -> XcXc
X -> ab
This violates property 1, so we insert a new rule
as follows
S -> YY
Y -> Xc
X -> ab
This now violates property 2 since X appears in
the right hand sides of the rules only once. So,
we delete a rule to get
S -> YY
Y -> abc
At this stage, both properties 1 and 2 are satisfied,
and all characters of the string have been read, so we stop.
Input
The input file COMPRESS.IN consists of two lines.
The first line contains an integer L,
1 <= L <= 256, which is the length of the
input string. The second line contains the input string;
only lower case English letters a, b, ...,
z can appear in the string. The following is
a sample input file
6
abcabc
Output
The output file COMPRESS.OUT contains an integer
which is the number of rules in the compressed
representation of the input string obtained in the
described manner. The output for the sample input
will be
2
|
|
|
Task #5 Input files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
Task #5 Output files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
|
Task 6: LABEL |
Charles is an auto racing fan and he wants to make his
own collection of models. Each model comes with a set
of stickers with images of digits. The set of stickers
of all models is the same. Using the stickers, Charles
labels models with consecutive integers starting from 1.
For example, to label the 2070-th model, four stickers
are needed: one "2" sticker, two "0" stickers, and one
"7" sticker. He can only use stickers that come with
the current model or left-over stickers from the previous
models. If these stickers do not allow him to label
the current model, then he must stop.
Let N be the maximum number of models Charles can
label before he runs out of stickers for some digit
needed to label a model. It turns out that N
can be a very large number even with a small number of
stickers that comes with each model. Given the set of
stickers, write a program to find the number of digits
in the decimal representation of N. You can
assume that your calculation involves only decimal
numbers of at most 100 digits; that is, decimal number
< 10100.
Example
Suppose the set of stickers has one sticker for each
digit "0", "1", ..., "9". After labelling the 11-th
model, the remaining stickers consist of 7 stickers
for the digit "1" and 10 stickers for each of the
digits "0", "2", "3", ..., "9".
Charles will run out of stickers for the digit "1" after
labelling the 199990-th model. With only one "1" sticker
from the next model, he does not have two "1" stickers
required for the number 199991 to label the 199991-th
model. Therefore the maximum number of models Charles
can label is N = 199990 and the answer is 6 because
there are six digits in N.
Input
The input file LABEL.IN consists of one line and
it contains ten 1-digit integers, with a blank between
two adjacent integers. The first integer is the number
of "0" stickers, the second integer is the number of "1"
stickers, and so on. The last (the tenth) integer is
the number of "9" stickers.
Output
The output file LABEL.OUT contains one integer
which is the number of digits in the decimal
representation of the number of labelled models.
Sample Input 1
1 1 1 1 1 1 1 1 1 1
Sample Output 1
6
Sample Input 2
3 4 5 4 3 4 5 4 3 4
Sample Output 2
29
|
|
|
Task #6 Input files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
Task #6 Output files: |
[ Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 ] |
|
|
| Design by |
|
Home
