Contest Python: ACSL › Checkpoint 3 — Contest 3 Practice

Questions: Checkpoint 3 — Contest 3 Practice

This is a practice paper modelled on ACSL Contest 3: short-answer questions from the four Contest 3 categories, then one programming problem. The Junior paper and the Intermediate/Senior paper share their first four questions, so this checkpoint holds both six-question papers.

Questions	Category	Division
1–2	Boolean Algebra	Junior and above
3–4	Data Structures	Junior and above
5–6	What Does This Program Do? – Arrays	Junior
7–8	FSAs and Regular Expressions	Intermediate and above
9	Programming problem	Junior and above

Choose your path.

Junior: Questions 1–6, then Question 9.
Intermediate or Senior: Questions 1–4 and 7–8, then Question 9. Questions 5–6 are optional extra array practice.
Classroom (no programming): Questions 1–4 and 7–8. Questions 5–6 are optional, and Question 9 is left out.
Elementary (no programming): this checkpoint is not your paper. Your Contest 3 practice test is Exercises 1–6 of Unit 8 (Boolean Algebra): six questions in 30 minutes.

Take it as a timed practice.

Put away your notes and set a timer.
Give yourself 30 minutes for the six-question paper on your path, as in the real contest. Work with pencil and paper only: no computer, no calculator. Write each answer on paper or in your notebook.
On the Junior, Intermediate or Senior path, then give yourself about 60 minutes for Question 9 (the Classroom and Elementary paths skip it). Write a complete program that reads the input with input() and prints exactly the output described. Save it as a .py file and run it from a terminal, typing the sample input or feeding it a file: python my_solution.py < sample.txt. Print nothing extra: no prompts in input(), and no words the problem did not ask for.

These times are a practice pace, not the official rules; the real limits for your division are published by ACSL at acsl.org.

How to write short answers.

Give exactly one answer, written the way the question asks for it.
For a simplified Boolean expression, write a sum of products in the book's notation: ~ NOT, * AND, + OR, with a single space around * and +. Inside a term, put the literals in alphabetical order of their variables; order the terms the same way, with X before ~X, and a shorter term first when one term runs out.
For the values that make an expression true, write each as a bracketed tuple in alphabetical order of the variables with no spaces inside, such as (1,0,1), list them in ascending binary order, and separate them with a comma and a space.
For a value popped from a stack or a queue, or a count or a path length, write it as a whole number or a letter.
For a question with lettered options, write the letters of every option that qualifies, in alphabetical order, separated by a comma and a space, such as A, E; write NONE if no option qualifies.
For a program, write exactly the one line it outputs.

When you finish, check yourself.

Short answers have no sample to test against. Mark the questions you were unsure of, then work each one again by its unit's method: redo the truth table, the tree or the trace, or test an option on short strings. Compare with a partner, or with a second attempt made without looking at the first.
The programming question is checked against its sample, and against inputs of your own made from its constraints: the smallest cases, the largest, and the tricky ones.

Then go back to the unit for any category that cost you points.

Question 1: Cut It Down

Division: Junior

Simplify the expression

A * ~B + ~(~A + C) + ~A * ~B * C

Write the answer as a sum of products with as few terms and literals as possible.

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: A sum of products: `~` NOT, `*` AND, `+` OR, with one space around each `*` and `+`; the fewest terms, then the fewest letters; letters in alphabetical order inside each term, and the terms in alphabetical order too, with a plain letter before its `~` form (as in `A * B + ~A * C`); `1` or `0` if it is always TRUE or always FALSE.

For parents and teachers: report a problem

Question 2: All the Ways to Be True

Division: Junior

Find all ordered triples (A,B,C) that make this expression true:

~(A * B) ⊕ C + A * ~(B + C)

⊕ is XOR (exclusive or). Write every triple in the form (A,B,C), in ascending binary order, separated by a comma and a space.

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: Ordered triples in counting-up order, with no spaces inside a triple, and a comma and a space between triples, as in `(0,1,0), (1,1,1)`; `NONE` if there are none.

For parents and teachers: report a problem

Question 3: Waiting in Line

Division: Junior

The statements below are carried out in order on a queue that starts empty. PUSH(x) adds x to the queue, and V = POP() removes an item from the queue and stores it in the variable V.

PUSH(6)
PUSH(1)
PUSH(9)
X = POP()
PUSH(4)
Y = POP()
PUSH(X)
PUSH(Y)
Z = POP()
Z = POP()

What is the value of Z at the end?

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Question 4: A Tree for September

Division: Junior

The letters of

SEPTEMBER

are inserted one at a time, from left to right, into a binary search tree that starts empty.

What is the internal path length of the tree? Write it as a whole number.

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Question 5: Flip and Climb

Division: Junior

A = [4, 7, 1, 8, 3, 6, 2]
n = len(A)
for i in range(n // 2):
    temp = A[i]
    A[i] = A[n - 1 - i]
    A[n - 1 - i] = temp
for i in range(1, n):
    if A[i] < A[i - 1]:
        A[i] = A[i] + A[i - 1]
print(A[n - 1] - A[0], A[3])

What exactly does the program print?

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.

For parents and teachers: report a problem

Question 6: Corner to Corner

Division: Junior

This program is written in ACSL pseudocode. % is the remainder, and A(r, c) is the item in row r and column c of the 2D array A. A FOR loop includes its end value.

FOR r = 1 TO 4
   FOR c = 1 TO 4
      A(r, c) = (r * c + r) % 5
   NEXT c
NEXT r
s = 0
FOR k = 1 TO 4
   s = s + A(k, k) - A(k, 5 - k)
NEXT k
OUTPUT s

What value does the program output?

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: a number

For parents and teachers: report a problem

Question 7: Reading the Machine

Division: Intermediate

This finite state automaton reads strings of the symbols a and b. Its initial state is S0, and its only final state is S3. Each row shows where the automaton goes from that state on each symbol.

State	on `a`	on `b`
`S0` (initial)	`S1`	`S2`
`S1`	`S0`	`S3`
`S2`	`S3`	`S0`
`S3` (final)	`S2`	`S1`

Which of these strings does the automaton accept?

A. ab
B. aabb
C. ababab
D. bbbab
E. baaab

Write the letters of every accepted string, separated by a comma and a space, or NONE.

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `B, D`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Question 8: Same Strings, Different Look

Division: Intermediate

In these regular expressions, U is union and λ is the empty string. Which of the following regular expressions describe exactly the same set of strings as

a(ba)*

A. (ab)*a
B. a(ab)*
C. (abUλ)*a
D. aUa(ba)*ba
E. ab*a*

Write the letters of every equivalent expression, separated by a comma and a space, or NONE.

How this is checked: Checked by comparing your answer with the expected answer.

Answer format: The labels of every option that qualifies, in alphabetical order, separated by a comma and a space, as in `A, C`; `NONE` if no option qualifies.

For parents and teachers: report a problem

Question 9: The Counting Line

Division: Junior

N players, numbered 1 to N, stand in a queue, with player 1 at the front and player N at the back. The game goes in rounds until the queue is empty. In each round, the player at the front leaves the front and joins the back of the queue, K − 1 times over; then the player who is now at the front leaves the game.

The input is one line: N and K, separated by one space. Print one line: the numbers of the players in the order they leave the game, separated by single spaces.

Constraints

1 <= N <= 500
1 <= K <= 500
K may be larger than the number of players left in the queue.

Sample Input

7 3

Sample Output

3 6 2 7 5 1 4

In the first round, players 1 and 2 move to the back, making the queue 3 4 5 6 7 1 2, and player 3 leaves. In the second round, players 4 and 5 move to the back, making it 6 7 1 2 4 5, and player 6 leaves.

How this is checked: Checked by running your program on 10 test inputs (1 sample, 9 hidden) and comparing its output line by line.

Your code

For parents and teachers: report a problem

Back to Checkpoint 3 — Contest 3 Practice