Contest Python: ACSL › Unit 10 — What Does This Program Do? (Arrays)
Exercises: Unit 10 — What Does This Program Do? (Arrays)
Most exercises here are short-answer, just like the Junior What Does This Program Do? – Arrays questions on an ACSL contest.
- Short-answer (marked short answer): a program is given, either in Python or in ACSL pseudocode.
Trace it by hand and write down exactly what it outputs.
For pseudocode, use ACSL's rules: arrays use round brackets and start at the position the program uses,
FORincludes its end value, andintrounds down. Every program outputs exactly one line; when it outputs several values, they are separated by one space. - Predict, then verify (programming): a program is given in ACSL pseudocode.
First trace it on the sample input and write down your prediction.
Then translate it into a complete Python program that reads the input with
input(), run it on the sample, and compare. Save it as a.pyfile and run it from a terminal:python my_solution.py < assets/ex8/1.in.
Each exercise is marked with the lowest ACSL division it belongs to. This unit is the Junior Contest 3 category; Intermediate and Senior students can use it as array-tracing drill. Exercises marked Challenge are extra practice for when you want more.
Exercise 1: Squares Minus Threes
INPUT n
FOR i = 1 TO n
A(i) = i * i - 3 * i
NEXT i
s = 0
FOR i = 1 TO n
IF A(i) > 0 THEN
s = s + A(i)
END IF
NEXT i
OUTPUT s, A(3)Input. n = 6
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 2: Bigger Than Its Position
A = [7, 3, 9, 3, 8, 1, 6]
count = 0
total = 0
for i in range(len(A)):
if A[i] > i:
count = count + 1
total = total + i
print(count, total)Input. None: the program reads no input.
What exactly does the program print? Work it out by hand first; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 3: Mirror Differences
A(1) = 5, A(2) = 8, A(3) = 1, A(4) = 6, A(5) = 3
n = 5
FOR i = 1 TO n
B(i) = A(i) - A(n + 1 - i)
NEXT i
OUTPUT B(1), B(2), B(3), B(4), B(5)Input. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 4: Highest and Lowest From Zero
This array starts at position 0.
A(0) = 4, A(1) = 9, A(2) = 2, A(3) = 9, A(4) = 1, A(5) = 2
big = A(0)
bpos = 0
small = A(0)
spos = 0
FOR i = 1 TO 5
IF A(i) >= big THEN
big = A(i)
bpos = i
END IF
IF A(i) < small THEN
small = A(i)
spos = i
END IF
NEXT i
OUTPUT bpos, spos, big - smallInput. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 5: One Pass of Swaps
A = [6, 2, 8, 5, 1, 7]
swaps = 0
for i in range(len(A) - 1):
if A[i] > A[i + 1]:
t = A[i]
A[i] = A[i + 1]
A[i + 1] = t
swaps = swaps + 1
print(A[0], A[2], A[5], swaps)Input. None: the program reads no input.
What exactly does the program print? Work it out by hand first; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 6: Round the Circle
A(1) = 3, A(2) = 7, A(3) = 2, A(4) = 9, A(5) = 4
FOR k = 1 TO 2
t = A(1)
FOR i = 1 TO 4
A(i) = A(i + 1)
NEXT i
A(5) = t
NEXT k
OUTPUT A(1), A(3), A(5)Input. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 7: Shifting the Wrong Way
A(1) = 4, A(2) = 1, A(3) = 6, A(4) = 3, A(5) = 8
FOR i = 2 TO 5
A(i) = A(i - 1)
NEXT i
s = 0
FOR i = 1 TO 5
s = s + A(i)
NEXT i
OUTPUT sInput. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: a number
Exercise 8: Leaders From the Right (predict, then verify)
A leader is a value that is strictly bigger than every value to its right. The last value is always a leader, because nothing is to its right. This ACSL program scans the array from right to left, counting the leaders and keeping the biggest value seen so far.
INPUT n
FOR i = 1 TO n
INPUT A(i)
NEXT i
count = 1
best = A(n)
FOR i = n - 1 TO 1 STEP -1
IF A(i) > best THEN
count = count + 1
best = A(i)
END IF
NEXT i
OUTPUT count, best- Predict: trace the program by hand on the sample input and write down what it outputs, before you look at the sample output.
- Verify: translate the program into Python and run it on the sample input.
The first input line holds n; the second line holds the n numbers, separated by spaces.
Print the number of leaders and the largest value, separated by one space.
Constraints
1 <= n <= 100- each value is a whole number from
-1000to1000
Sample Input
8
5 9 3 9 4 7 2 3Sample Output
3 9How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.
Exercise 9: Tally of Values
parts = input().split()
A = []
for piece in parts:
A.append(int(piece))
C = [0, 0, 0, 0, 0, 0, 0]
for i in range(len(A)):
C[A[i]] = C[A[i]] + 1
most = 0
for v in range(1, 7):
if C[v] > C[most]:
most = v
print(most, C[most], C[4])Input
3 1 4 1 5 2 6 5 3 5What exactly does the program print? Work it out by hand first; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 10: Running Totals in Place
A(1) = 2, A(2) = 5, A(3) = 1, A(4) = 4, A(5) = 3
FOR i = 2 TO 5
A(i) = A(i) + A(i - 1)
NEXT i
OUTPUT A(3), A(5), A(5) - A(2)Input. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 11: Reverse, Then Weigh
A(1) = 9, A(2) = 4, A(3) = 7, A(4) = 1, A(5) = 6, A(6) = 3, A(7) = 8
n = 7
FOR i = 1 TO int(n / 2)
t = A(i)
A(i) = A(n + 1 - i)
A(n + 1 - i) = t
NEXT i
s = 0
FOR i = 1 TO n
s = s + i * A(i)
NEXT i
OUTPUT A(1), A(4), sInput. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 12: The Heaviest Row
grid = []
for r in range(4):
row = []
for c in range(4):
row.append((r + 2 * c) % 5)
grid.append(row)
best = 0
where = 0
for r in range(4):
total = 0
for c in range(4):
total = total + grid[r][c]
if total > best:
best = total
where = r
print(where, best)Input. None: the program reads no input.
What exactly does the program print? Work it out by hand first; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 13: Both Diagonals
FOR r = 1 TO 4
FOR c = 1 TO 4
A(r, c) = r * c - (r + c)
NEXT c
NEXT r
d1 = 0
d2 = 0
FOR i = 1 TO 4
d1 = d1 + A(i, i)
d2 = d2 + A(i, 5 - i)
NEXT i
OUTPUT d1, d2Input. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 14: Frame and Middle (predict, then verify)
A grid of whole numbers has a frame (the boxes in its first row, last row, first column or last column) and a middle (every other box). This ACSL program adds up the frame and the middle separately.
INPUT rows, cols
FOR r = 1 TO rows
FOR c = 1 TO cols
INPUT A(r, c)
NEXT c
NEXT r
edge = 0
inner = 0
FOR r = 1 TO rows
FOR c = 1 TO cols
IF r == 1 || r == rows || c == 1 || c == cols THEN
edge = edge + A(r, c)
ELSE
inner = inner + A(r, c)
END IF
NEXT c
NEXT r
OUTPUT edge, inner- Predict: trace the program by hand on the sample input and write down what it outputs, before you look at the sample output.
- Verify: translate the program into Python and run it on the sample input.
The first input line holds rows and cols, separated by one space.
Each of the next rows lines holds one row of the grid: cols numbers separated by spaces.
Print the frame total and the middle total, separated by one space.
Constraints
1 <= rows <= 20and1 <= cols <= 20- each value is a whole number from
-1000to1000
Sample Input
3 4
1 2 3 4
5 6 7 8
9 1 2 3Sample Output
38 13How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.
Exercise 15: Mirror Across the Diagonal
A = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
for r in range(3):
for c in range(r + 1, 3):
t = A[r][c]
A[r][c] = A[c][r]
A[c][r] = t
print(A[0][2], A[2][1], A[1][0])Input. None: the program reads no input.
What exactly does the program print? Work it out by hand first; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 16: Equal Neighbours
FOR r = 1 TO 4
FOR c = 1 TO 4
A(r, c) = (r * c) % 3 + r
NEXT c
NEXT r
h = 0
v = 0
FOR r = 1 TO 4
FOR c = 1 TO 3
IF A(r, c) == A(r, c + 1) THEN
h = h + 1
END IF
IF A(c, r) == A(c + 1, r) THEN
v = v + 1
END IF
NEXT c
NEXT r
OUTPUT h, vInput. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 17: Pascal's Triangle (predict, then verify)
In Pascal's triangle, each row starts and ends with 1, and every other number is the sum of the two numbers just above it.
This ACSL program builds rows 0 to n in a 2D array P, where P(r, c) is the number in row r at place c (both counted from 0).
It outputs P(n, k) and the sum of row n.
INPUT n, k
FOR r = 0 TO n
FOR c = 0 TO n
P(r, c) = 0
NEXT c
NEXT r
P(0, 0) = 1
FOR r = 1 TO n
P(r, 0) = 1
FOR c = 1 TO r
P(r, c) = P(r - 1, c - 1) + P(r - 1, c)
NEXT c
NEXT r
s = 0
FOR c = 0 TO n
s = s + P(n, c)
NEXT c
OUTPUT P(n, k), s- Predict: trace the program by hand on the sample input and write down what it outputs, before you look at the sample output.
- Verify: translate the program into Python and run it on the sample input.
The input is one line holding n and k, separated by one space.
Print P(n, k) and the sum of row n, separated by one space.
Constraints
0 <= k <= n <= 30
Sample Input
5 2Sample Output
10 32How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output line by line.
Exercise 18: Marking Multiples
FOR i = 1 TO 30
F(i) = 0
NEXT i
FOR i = 2 TO 30
IF F(i) == 0 THEN
FOR j = 2 * i TO 30 STEP i
F(j) = F(j) + 1
NEXT j
END IF
NEXT i
count = 0
best = 0
where = 0
FOR i = 1 TO 30
IF F(i) == 2 THEN
count = count + 1
END IF
IF F(i) > best THEN
best = F(i)
where = i
END IF
NEXT i
OUTPUT count, best, whereInput. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.
Exercise 19: The Snake Grid
k = 1
FOR r = 1 TO 4
IF r % 2 == 1 THEN
FOR c = 1 TO 4
A(r, c) = k
k = k + 1
NEXT c
ELSE
FOR c = 4 TO 1 STEP -1
A(r, c) = k
k = k + 1
NEXT c
END IF
NEXT r
s = 0
FOR i = 1 TO 4
s = s + A(i, i) - A(i, 5 - i)
NEXT i
OUTPUT A(3, 2), sInput. None: the program reads no input.
What exactly is output? Trace it by hand, using ACSL's rules; write the output exactly as it appears.
How this is checked: Checked by comparing your answer with the expected answer.
Answer format: Exactly the one line the program outputs: values separated by one space, strings without quotation marks, and letters in the case the program prints them.