|
|
NOI 1998 TASKS
| |
|
Overview |
| | Task 1 |
Task 2 | Task 3 |
| Program name: | SHIP.EXE |
KNIGHT.EXE | SUM.EXE |
| Input file: | SHIP.IN |
KNIGHT.IN | SUM.IN |
| Output file: | SHIP.OUT |
KNIGHT.OUT | SUM.OUT |
| Maximum execution time: |
1 minute | 1 minute | 1 minute |
| Test cases: | 6 |
6 | 6 |
| Total points: |
100 | 100 | 100
|
|
|
|
Task 1: Ship Berth Assignment |
Ships have to be berthed alongside a harbour for short stays.
To minimize the number of berths of the harbour used, the
harbour planners want to use berths efficiently, reusing them
when ships leave. You are charged with implementing a solution
to their berth assignment problem.
You are given the arrival and departure times for N
ships. The arrival time of the jth ship is A[j],
and its departure time is D[j], and these times occur
with a T-hour period, so that 1 <= A[j] <
D[j] <= T.
Each ship must be assigned a berth during its stay, namely,
during the time interval [A[j],D[j]]. For simplicity,
we assume that each ship has unit length and each berth also
has unit length and so any ship can be assigned to any berth.
However, of course, two ships cannot use the same berth at
the same time, so if ships numbered j and k use
the same berth, it must be the case that either A[j]
> D[k] or A[k] > D[j].
Your program is required to do the assignment of berths to
ships in such a way as to minimize the total number of berths
that are used at least once. Your program will output this
minimum total number of berths used (you should not output
the entire assignment).
You may assume that N <= 1000, T <= 48,
and, for each j, A[j] and D[j] are
integers between 1 and 48 inclusive.
|
|
Input File Format |
The input file SHIP.IN contains the integer
T (the number of hours) on the first line, the
integer N (the number of ships) on the second line,
followed by N lines, each containing three integers:
a ship number, the arrival time of the ship and the departure
time of the ship.
For example, consider the following input:
16
8
1 1 4
2 3 8
3 6 12
4 5 10
5 11 16
6 3 9
7 13 15
8 1 2
In this example, the value of T, given on the first
line, is 16. The number of ships N is given next: 8.
Finally, ship number 1 arrives at time 1 and leaves at time 4,
ship number 2 arrives at time 3 and leaves at time 8, and
so on.
|
|
Output File Format |
The output file SHIP.OUT contains a single integer,
which indicates the minimum number of berths used.
For the above example, the output will be:
4
|
|
Task #1 Data: |
[ Set #0 |
Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 |
Set #6 ] |
|
|
Task 2: Knight Moves |
A jump of a knight on an N x N chess board
consists of two horizontal steps and one vertical step, or
one horizontal step and two vertical steps. For example,
consider a knight on position K=(3,2) in the
following 5 x 5 board.
1 2 3 4 5
+---+---+---+---+---+
1 | | | | X | P |
+---+---+---+---+---+
2 | | | | X | |
+---+---+---+---+---+
3 | | K | | X | |
+---+---+---+---+---+
4 | | | | X | |
+---+---+---+---+---+
5 | | | | | |
+---+---+---+---+---+
This knight can jump to positions (1,1), (1,3), (2,4), (4,4),
(5,3) and (5,1). The knight can move to position
P=(1,5) by jumping first to (5,3), then to (3,4) and
then to P. This is the least number of jumps to get
from K to P.
The board may contain forbidden positions, indicated by
X in the above board. The knight may not land on
a forbidden position. In the above situation, the only
allowed way to get from K to P with 3 jumps is
via (1,1) and (2,3).
Write a program that, given a board size N, an initial
position K of the knight, a target position P
and a list of forbidden positions, computes the least number
of jumps to get from K to P while not landing
on any forbidden positions. The board size N in
the test data and the number of forbidden positions both
range from 5 to 50.
Output the value -1 if there is no way to get from K
to P without landing on any forbidden positions.
|
|
Input File Format |
The input file KNIGHT.IN contains
- the board size N on the first line,
- the initial position K of the knight on the
second line,
- the target position P on the third line,
- the number T of forbidden positions on the
fourth line, followed by T lines each
containing a forbidden position.
The input data corresponding to the chess board
shown in the example above is as follows.
5
3 2
1 5
4
1 4
2 4
3 4
4 4
On the first line is the number 5 of rows and columns.
Next is the initial position K, which is (3,2).
The target position P is given on the third line.
Next, the number of forbidden positions, 4 in this example,
is given. The list of forbidden positions follows,
one per line.
|
|
Output File Format |
The output file KNIGHT.OUT contains an integer which
indicates the number of jumps in the shortest move from
K to P. Output -1 if there is no solution.
For the above example, the output will be:
3
|
|
Task #2 Data: |
[ Set #0 |
Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 |
Set #6 ] |
|
|
Task 3: Sum Expression |
Any positive integer n that is at least 4 can be
expressed as a sum of prime numbers from 2 to n-1.
For example,
9 = 2 + 5 + 2
= 2 + 3 + 2 + 2
= 3 + 3 + 3
= 2 + 7.
(Recall that a prime is an integer p >= 2 whose
only divisors are itself and 1.)
Write a program to compute C(n), the number of
different ways to express n as a sum of primes, where
permutations of a sum are considered to be the same;
ie. 2 + 3 and 3 + 2 should be considered as one expression.
In the example above, C(9) is 4.
You may assume 4 <= n <= 96.
|
|
Input File Format |
The input text file SUM.IN contains a positive
integer n which is at most 96. For example
9
|
|
Output File Format |
Your program should produce an output text file
SUM.OUT that contains the value C(n).
For the above example, the output will be:
4
|
|
Task #3 Data: |
[ Set #0 |
Set #1 |
Set #2 |
Set #3 |
Set #4 |
Set #5 |
Set #6 ] |
|
|
| Design by |
|
Home