IITPSA NPC

Level 1 West, Gallagher House,

Gallagher Convention Centre,
Leading ICT Professionalism 19 Richards Drive, Midrand, South Africa
and Ethical Digital P O Box 1714, Halfway House
1685, South Africa
Transformation
Tel: +27 87 655 1679 or
+27 11 315 1319
[Link]

Programming Olympiad 2023 : Round 1

Not to be used before 24 July 2023

1. This paper is for ALL participants.

2. All answers (output) must be TYPED or PASTED on your Answer Sheet by offline participants.
Handwritten Answer Sheets will be disqualified.
3. All answers (output) must be submitted on the competition website that you received with your login
(online participants).
4. Each correct answer for question 1 earns 6 marks, question 2 earns 9 marks while a correct answer for
question 3 earns 10 marks.
5. You have 60 minutes to attempt as many questions as possible.
6. Programs should be readable, concise, and use appropriate variable names.
7. Indicate the question number, your name, surname, username and the language and version used in a
comment statement at the start of every program, e.g., e.g., “Q3 Sam King, username, Python 2.7”
8. Save your program as Qn Name Surname, e.g., Q3 Sam King
9. You may assume that the user input will satisfy the problem specification and so you do not need to
validate the input.
10. Do not write code to produce only specific answers, as the external judges may use other test cases.
11. After the contest you may be given time to print out your Answer Sheet. Do not make any changes during
this time.
12. Make sure you save the programs you have created as well as the Answer Sheet in a place where your
teacher can find them.
13. DO NOT MODIFY ANY FILES AFTER THE END OF THE CONTEST AS THIS WILL LEAD TO YOUR
DISQUALIFICATION.

Directors: A. Gwanzura (President), Ms. S.B. Goba (VP), K.W. Matthee (Treasurer),
T. Mashegoane, R. Kisten, Ms. P. Pasi, J. Singh, K.F. Chipidza,
Prof. L.A. Futcher, Ms. J.M. Overdevest, N.V. Zambezi, M.A. Parry (CEO)

Reg. No.: 1958/001036/08 VAT Reg. No.: 4760 12 1113 PBO No.: 930010177
Question 1: Circle
An important part of Data Science is data visualization. To
produce the below visualization, the first step is to
determine which points are outside the circle. Points outside
Question 2: DNA Corruption
the circle are then labelled BLUE, and points inside or on
Bongi, the astronaut, needs your help. Without the
the circle are labelled RED.
protection of the atmosphere, her DNA is being corrupted
by the sun’s radiation! Luckily, our cells come with backup
DNA. Help Bongi figure out which strands of her DNA
have been corrupted.
A strand of DNA is a string of the 4 characters: T, A, C and
G. The characters form two pairs. The first pair is (A, T).
The second pair is (G, C). If two characters are in the same
pair, they are considered opposite. That is, T is the opposite
of A, and A is the opposite of T. G is the opposite of C, and
C is the opposite of G.

Task
Write a program that takes two strings of length 5 as input.
The first string is the original DNA, and the second string is
the backup DNA. Your program must output “OK” if every
character in the backup strand of DNA is the opposite of the
corresponding character in the original strand of DNA.
The circle has a radius of 1. For a point (x, y) the distance Otherwise, output “CORRUPTED”.
to the centre is √𝑥 2 + 𝑦 2 . If the distance to the centre of a
point is more than 1 it is outside the circle. Example 1:

Task Input: ACTAG TGATC

Given the point (x, y), write a program that outputs BLUE Answer: OK
if the point lies outside the circle and outputs RED if the
point lies inside or on the circle. Explanation: Reading from left to right of the original
The first line of input contains the coordinates x and y. DNA: The opposite of A is T. The opposite of C is G. The
opposite of T is A. The opposite of A is T. The opposite
Examples of G is C. All the characters in the backup are the opposite
Input: 0.1 0.3 Answer: RED of the original. The DNA is “OK”.
Input: 0.9 0.53 Answer: BLUE
Example 2:
Test your program with the following cases:
a) 0.9 0.8 Input: GTACG CACGC
b) 0.2 0.96
Answer: CORRUPTED
c) -0.5 0.87
d) 0.83 -0.55
Explanation: The third character of the original DNA is
A. The opposite of A is T, but the third character of the
backup DNA is C. The DNA is "CORRUPTED".

Test your program with the following cases:

a) ACACA TGTCT
b) ATGGC GCCAT
c) TCGCT AGCGA
d) TTGAC TTGAC

Directors: A. Gwanzura (President), Ms. S.B. Goba (VP), K.W. Matthee (Treasurer),
T. Mashegoane, R. Kisten, Ms. P. Pasi, J. Singh, K.F. Chipidza,
Prof. L.A. Futcher, Ms. J.M. Overdevest, N.V. Zambezi, M.A. Parry (CEO)

Reg. No.: 1958/001036/08 VAT Reg. No.: 4760 12 1113 PBO No.: 930010177
 Input
Question 3: Sandpile
The first line of input is L the length of the table.
In front of you is a large sandpile on a wooden table. The The second line of input are the heights h1, h2, …, hL.
wooden table has length L. You have measured that i units
from the left the sandpile has height hi. Output

The amount of sand that falls off the table.

Example 1
3
141
Answer: 2

Example 2
3
321
Answer: 3

Example 3
4
1231
Answer: 2

Explanation of first example: The sandpile goes through

the following avalanches highlighted in red. Sand falls off
the table during the second and third avalanches.

During your measurements, you accidentally bumped the 141→222→032→040→121

table causing your sandpile to change shape and for even
some of the sand to fall on the floor!
Tests
The sandpile changes shape according to the following
avalanche rule: a) 3
3 1 2
If a height of hi is more than a unit taller than either hi+1 or
b) 5
hi-1, the height hi avalanches. Meaning that it sends one unit
1 1 6 1 1
of sand to the left and one unit of sand to the right. Note an
avalanche can trigger another avalanche, and that the edge
c) 4
of the table h0 and hL+1 have height 0. When the height h1 or
4 3 2 1
hL avalanches, one of the units of sand falls off the table.

Making use of the avalanche rule, write a program that

d) 5
will be able to tell how much sand fell off the table. (Hint:
1 7 1 7 1
The tests guarantee that no matter in which order the
avalanches occur, the amount of sand that falls off the
table is the same.)

Directors: A. Gwanzura (President), Ms. S.B. Goba (VP), K.W. Matthee (Treasurer),
T. Mashegoane, R. Kisten, Ms. P. Pasi, J. Singh, K.F. Chipidza,
Prof. L.A. Futcher, Ms. J.M. Overdevest, N.V. Zambezi, M.A. Parry (CEO)

Reg. No.: 1958/001036/08 VAT Reg. No.: 4760 12 1113 PBO No.: 930010177