Checkpoint 4 — Contest 4 Practice

This is a practice paper modelled on ACSL Contest 4: short-answer questions from the four Contest 4 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. It is the last practice paper of the season.

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 string 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 4 practice test is Exercises 1–6 of Unit 12 (Graph Theory): 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. 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 "how many" question, write just the whole number, such as 6.
• For the inputs that make a circuit TRUE, write each as a bracketed tuple in the order of the INPUTS line with no spaces inside, such as (1,0,1), list them in ascending binary order, and separate them with a comma and a space; write NONE if there are none.
• For a simplified circuit, write a sum of products in the book's notation: ~ NOT, * AND, + OR, with a single space around * and +. Use the fewest terms, and then the fewest letters. 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. Write 1 or 0 alone if the circuit is always TRUE or always FALSE.
• For a program, write exactly the one line it outputs: values separated by one space, and strings without quotation marks.
• For an assembly program, write the value in the location asked for as a whole number, or every printed number in order, on one line, separated by single spaces.

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 matrix or the trace, or list the cycles and walks a second way. 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.