Computer Programming Olympiad Final Round Question Paper

Programming Olympiad Final Round Question Paper

** Download Programming Final Round 2017 PO Finals Day 1 & Day 2 Question Paper & Solution
** Not to be used before 14 August 2017

Related : Computer Programming Olympiad School Round 2 Question Paper 2017 : www.southafricain.com/9866.html

Instructions

1. This paper is for ALL candidates.
2. All answers must be TYPED or PASTED on your Answer Sheet. Handwritten Answer Sheets will be disqualified.

Sample Questions

SAPO Finals 2017 Day1 & Day 2
Cape Town, South Africa, 7 October 2017

Day 1

Problem A. Towers :
Input file: standard input
Output file: standard output
Time limit (C++): 2 seconds
Time limit (Java): 4 seconds
Time limit (Python): 20 seconds
Memory limit: 256 megabytes
Java Class Name: towers
Maximum Points Available: 100

Alison just got a job at a telecommunications company. The company has various cellular towers positioned in a straight line and her job is to determine the minimum signal strength these towers must output to reach all cities.

N points are given on a straight line denoting the x-coordinates of the cities. M points are also given denoting the x-coordinates of the cellular towers. All the cities and cellular towers have y-coordinate of 0.

Each tower works by sending and receiving signals from cities no more than a distance r away. Your task is to determine the minimal r such that, for each city, there exists a cellular tower a distance no more than r away.

If r = 0 then the cellular tower only provides signal at the exact point where it is located. A signal tower may provide signal for several different cities.

Input :
The first line consists of two space-separated positive integers N and M (1 N;M 106) where N is the number of cities and M is the number of cellular towers.

The second line consists of a sequence of N integers a1; a2; : : : ; aN (??109 ai 109) denoting the coordinates of the cities. Any number of cities may be given at the same point. All coordinates ai are given in non-decreasing order.

The third line consists of a sequence ofM integers b1; b2; : : : bM (??109 bi 109) denoting the coordinates of the cellular towers. Any number of cellular towers may be given at the same point. All coordinates bi are given in non-decreasing order.

Output :
Output a single integer r denoting the minimum signal strength each tower can output to ensure that each city will be covered.

Scoring :
Subtask 1 (5 points): There is only one city (N = 1) and 1 M 25
Subtask 2 (10 points): There is only one cellular tower (M = 1)
Subtask 3 (15 points): 1 N;M 1 000
Subtask 4 (15 points): 1 N 1 000
Subtask 5 (15 points): 1 M 1 000
Subtask 6 (40 points): No further restrictions

Problem B. Stargazing :
Input file: standard input
Output file: standard output
Time limit (C++): 2 seconds
Time limit (Java): 4 seconds
Time limit (Python): 20 seconds
Memory limit: 256 megabytes
Java Class Name: stargazing
Maximum Points Available: 100

From a young age, Saya has always enjoyed stargazing with her friends. One day, she decides to start working on a star map so she can make her own constellations.

Saya’s constellations are very simple. A star is part of a constellation if it has a Manhattan distance less than or equal to D units from any star already in that constellation.

If there are no other stars within D units, this star becomes a new constellation. If there are two or more constellations within D units, these constellations combine to form one constellation.

She starts with an empty star map. On each day that she is out stargazing, she adds a new star she likes and records its position in the sky, denoted by (Xi; Yi).

Every time she records a new star, she is curious to see what is the new size of the constellation to which that star has been added.

Over the years, she collects a total of N stars on her star map. Help her figure out the constellation size for each star at the moment they were added.

Note :
The Manhattan distance is the shortest distance between two points if you could only travel up, down, left or right along the grid. In other words, for points a and b, their Manhattan distance is jXa ?? Xbj + jYa ?? Ybj (where j:::j is the absolute value function. It essentially makes a number positive if it’s negative).

Input :
The first line contains two space-separated integers N and D (0 D 106), the total number of stars and the maximum Manhattan constellation distance (as defined above), respectively.
The next N lines contain Xi and Yi (0 Xi; Yi 106), the X and Y position of the ith star Saya records.
Each star has unique coordinates.

Output :
Output N numbers, each on a new line, where the ith number is the constellation size of the constellation the ith star was added to.

Scoring :
Subtask 1 (15 points): 0 Xi; Yi;D 100, 1 N 100, constellations will grow but no two
constellations will ever merge.
Subtask 2 (15 points): 0 Xi; Yi;D 100, 1 N 100
Subtask 3 (30 points): 1 N 100 000, 1 D 100
Subtask 4 (40 points): 1 N 100 000

Day 2

Problem A. Cave
Input file: standard input
Output file: standard output
Time limit (C++): 3 seconds
Time limit (Java): 6 seconds
Time limit (Python): 30 seconds
Memory limit: 128 megabytes
Java Class Name: cave
Maximum Points Available: 100

For reasons unknown, Bruce finds himself waking up in a large cave. Fortunately, he seems to have a map of the layout of the cave, as well as K sticks of dynamite to blast his way to the exit.

As Bruce is afraid of the dark, he wishes to escape as quickly as possible, and has thus asked you to write a program which will determine his shortest escape route.

The cave is modeled as an N by M grid of cells. Each cell is either solid or empty. A valid escape route consists of Bruce taking a number of steps from his starting location to finish at the exit.

In each step, Bruce can move from his current cell to an adjacent empty cell. If he has at least one stick of dynamite left, he may instead use a stick of dynamite to move to an adjacent solid cell. The length of the escape route is the number of steps it consists of.

Input :
The first line contains three space-separated integers N (1 N 500), M (1 M 500), and K (1 K 50).
The following N lines each contain M characters, depicting the cave. ‘.’ denotes an empty cell. ‘#’ denotes a solid cell. ‘S’ denotes the empty cell where Bruce starts, and occurs exactly once in the input. ‘E’ denotes the empty cell where Bruce can exit the cave, and occurs exactly once in the input.

Output :
A single integer, which is the length of the shortest valid escape route. If there is no such escape route, output -1 instead.

Scoring :
Subtask 1 (10 points): N = 1
Subtask 2 (10 points): There is no cell of type ‘#’.
Subtask 3 (25 points): K = 0
Subtask 4 (20 points): K = 1
Subtask 5 (35 points): No further restrictions

Problem B. Tigers :
Input file: standard input
Output file: standard output
Time limit (C++): 2 seconds
Time limit (Java): 4 seconds
Time limit (Python): 20 seconds
Memory limit: 64 megabytes
Java Class Name: tigers
Maximum Points Available: 100

Alexandra was walking through the Siberian forest one day when she suddenly noticed she was being watched. Up atop a cliff face in front of her was Boris the Siberian Tiger, lingering ominously.

Alexandra is best friends with Boris, but she knows that Boris might decide to eat her if he feels hungry. Alexandra would therefore like to work out how many ways Boris can jump down the cliff face to the ground to eat her so she can plan her escape if necessary.

The cliff consists of N ledges. Ledge i is hi units above the ground and is xi units to the right of Alexandra (and can be considered a single point on the cliff face). Boris starts at the highest ledge, and repeatedly jumps down to a ledge strictly lower (or directly to the ground) until he reaches the ground.

Specifically, if Boris is on ledge i, he may jump directly to the ground, or to any ledge j which has height hj < hi and jxj ?? xij L, where L is Boris’s jumping range.

Alexandra would like to know the number of ways Boris can jump between ledges to reach the ground. Since the answer to Alexandra’s question may be large, you should output the the remainder of the answer when divided by 109 + 7. Help Alexandra avoid being eaten by Boris.

Input :
The first line consists of two space-separated integers, N (1 N 100 000) and L (0 L 100 000).
The next N lines contain two integers each. On the ith of these lines is xi (0 xi 100 000) and hi (1 hi 1 000 000), describing the position of the ith ledge (where 1 i N).
It is guaranteed that the heights of the ledges will be distinct.

Output :
Output a single integer denoting the number of ways Boris can jump between ledges to reach the ground, modulo 109 + 7.

Scoring :
Subtask 1 (10 Points): N 6
Subtask 2 (15 Points): N 100 000;L = 100 000
Subtask 3 (35 Points): N 1 000
Subtask 4 (40 Points): N 100 000

Author : Brightlin

Computer Programming Olympiad Final Round Question Paper

Programming Olympiad Final Round Question Paper

Instructions

Sample Questions

Day 1

Day 2

Leave a Reply Cancel reply

Search the site :

Categories