Home
18th NOI
Committee
Eligibility
Rules & Regulations
Programme
Coding Environment
Instructions (PDF)
About NOI
About NOI
Acknowledgment
About IOI
Competition
Problem Sets
Results
Support
Contacts

Tasks Archive : 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 05 (Prelim) | 04 | 03 | 02 | 01 | 00 | 99 | 98

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 Techsailor Group