Unit 0 — ACSL Foundations

The problem: Pairs That Make the Target

This is the kind of programming problem you meet on an ACSL contest. Read it now; by the end of this unit you will write a program that solves it.

A row of number cards lies on the table. Two cards at different positions form a pair. How many pairs add up to exactly the target number T? Also report the first such pair: the one whose first card is furthest to the left, and, among those, whose second card is furthest to the left.

Input

The first line holds two integers, N and T. The second line holds the N card values, separated by spaces.

Output

Print two lines. The first line is the number of pairs whose values add up to T. The second line is the first such pair, as its two values in left-to-right order, separated by one space. If there is no such pair, the second line is NONE.

Sample Input

6 9
4 5 1 8 3 6

Sample Output

3
4 5

The three pairs are 4 5, 1 8 and 3 6.

Constraints

1 <= N <= 1000
Every card value is between -1000 and 1000.
-2000 <= T <= 2000

To solve it you need three skills, one per lesson: how an ACSL contest works and how a program is judged (Lesson 1), how to read input like 6 9 into numbers (Lesson 2), and how to try every pair and keep the one you want (Lesson 3).

You will learn

How ACSL works: its divisions, its four contests, and its two kinds of problems (short answers and programs).
Read a contest problem statement, and run a program with input you type or read from a file with <.
Read contest input with input(), split() and int(), for a fixed count of values or until a 0 arrives.
Keep pairs together as tuples, and solve small problems by complete search: try every candidate or every pair.

Lesson 1 — How ACSL works

The American Computer Science League (ACSL) runs a contest season for school students. A season has four contests, spread over the school year, from fall to spring. You take each contest at your school, during that contest's window.

Each contest tests a few topics, which ACSL calls categories. For example, Contest 1 includes Computer Number Systems and Recursive Functions. This book follows the season: after this Foundations unit come four parts, Contest 1 to Contest 4, each with one unit per category and a practice contest at the end. Study each part in the weeks before that contest.

The divisions

ACSL has five divisions.

Division	Who it is for	Programming problem?
Elementary	younger students; one category per contest	no
Classroom	a whole class; questions from several categories	no
Junior	mostly middle-school students	yes
Intermediate	high-school students	yes
Senior	experienced high-school students; the hardest division	yes

Junior, Intermediate and Senior are a ladder: each step is harder than the one before. Every exercise in this book is marked with the lowest division it belongs to. If you are preparing for Junior, do the Junior items; an Intermediate student does the Junior and Intermediate items, and so on. Foundations starts at Junior, because it is about programming.

Two kinds of problems

A Junior, Intermediate or Senior contest has two parts.

Short-answer questions. You work with pencil and paper and write one answer for each question. A typical one says: "Given this input, what exactly does this program print?" ACSL calls these What Does This Program Do? questions.
One programming problem. You write a program that reads input and prints output. It is judged on several test inputs, and each test counts only if your output is exactly right.

Both parts want exact answers. Close does not count.

Exact answers

Predict what each line prints, then check your prediction against the output.

print(3, 4)
print("3,4")
print("The answer is", 3, 4)

Output

3 4
3,4
The answer is 3 4

Notice

print puts one space between the things you give it. If the answer should be 3 4, then 3,4 is wrong, and so is The answer is 3 4. A judge compares your output with the expected output, word for word, so print only what the problem asks for.

A short-answer question works the same way. Trace this program by hand, write down what you think it prints, and only then run it.

x = 7
y = x // 2
x = x + y
if x > 9:
    y = y * 10
print(x, y)

Output

10 30

Notice

Tracing means keeping a small table of every variable and updating it one line at a time. Here y becomes 3, then x becomes 10, so the if runs and y becomes 30. The exact answer is 10 30.

Reading a problem statement

Look back at the problem at the top of this unit. Every ACSL-style programming statement has the same parts.

The story: what is being asked, in words.
Input: exactly what arrives, line by line.
Output: exactly what to print, line by line, and what to print in the special case (here, NONE).
Sample: one input with its correct output. Work it by hand before you code.
Constraints: how big the numbers can get. They tell you which edge cases can happen (can N be 1? can values be negative?).

Read all five parts before you write any code.

Running a program with input

A contest program does not ask questions with a prompt like "Enter a number: ". It calls input() with nothing in the brackets and reads the line the judge gives it.

Here is a small complete program. It reads one line holding a whole number, such as 12345, and prints the sum of its digits.

line = "12345"
total = 0
for digit in line:
    total = total + int(digit)
print(total)

Output

Notice

A line of text is a string, and a for loop walks through it one character at a time. Each character is still text, so int(digit) turns "3" into 3 before adding it.

The example above writes the line into the code as line = "12345", so that it runs without anyone typing the input. The real program reads the line with input(). It is saved as assets/l1.py.

Try it yourself

line = input()
total = 0
for digit in line:
    total = total + int(digit)
print(total)

To run it, open a terminal in this unit's folder and type:

python assets/l1.py

The program waits. Type 12345 and press Enter; it prints 15.

You can also feed it a file instead of typing. The < sign sends the file's contents to the program as if you had typed them:

python assets/l1.py < assets/l1/1.in

The file assets/l1/1.in holds the input, and assets/l1/1.out holds the expected output. A judge does exactly this: it runs your program on each input file and compares what you print with the .out file.

Lesson 2 — Reading contest input

Every call to input() reads one whole line and gives it back as a string, without the Enter at the end. Contest input is made of integers and words, so reading it is always the same three steps: read a line, split it into pieces, and turn the number pieces into integers.

Try it yourself

line = input()
print(line)

Notice

This program waits for someone to type a line, so it is shown here without any output. In the rest of this lesson we store a line in a variable, such as line = "17 5", to stand in for input().

Splitting a line

.split() breaks a string wherever there are spaces and gives back a list of strings.

line = "17 5"
parts = line.split()
print(parts)
print(len(parts))

Output

['17', '5']
2

line = "  ACSL   is    fun  "
print(line.split())

Output

['ACSL', 'is', 'fun']

Notice

.split() ignores extra spaces, including spaces at the start and end. You always get just the words or numbers.

Turning pieces into numbers

The pieces are still text. Adding two text pieces glues them together; adding two numbers adds them.

parts = "40 2".split()
print(parts[0] + parts[1])
a = int(parts[0])
b = int(parts[1])
print(a + b)

Output

402
42

Notice

"40" + "2" is "402", but 40 + 2 is 42. Call int(...) on every piece that is a number before you do arithmetic with it. Forgetting this is one of the most common contest mistakes.

A line can mix words and numbers. Keep the word as a string and convert only the number.

line = "Ada 95"
parts = line.split()
name = parts[0]
score = int(parts[1])
print(name, score + 5)

Output

Ada 100

Several lines

Each call to input() reads the next line. A program that reads a name on the first line and two numbers on the second looks like this:

Try it yourself

name = input()
parts = input().split()
width = int(parts[0])
height = int(parts[1])
print(name, width * height)

Notice

input().split() reads a line and splits it in one step.

Reading a fixed count

Many problems start with a count N and then give N more lines. Read N first, then loop N times. To try the idea here, we keep the lines of an input in a list and walk through it; the real program calls input() instead.

lines = ["3", "Ada 95", "Ben 78", "Cy 86"]
n = int(lines[0])
for k in range(n):
    parts = lines[k + 1].split()
    name = parts[0]
    score = int(parts[1])
    if score >= 80:
        print(name)

Output

Ada
Cy

Notice

Line 0 holds the count, so the student lines are at positions 1 to n, which is why the loop reads lines[k + 1].

The same program, reading real input:

Try it yourself

n = int(input())
for k in range(n):
    parts = input().split()
    name = parts[0]
    score = int(parts[1])
    if score >= 80:
        print(name)

Sometimes all N values sit on one line after the count. Then you split that one line and convert each piece.

first = "4"
second = "8 3 12 5"
n = int(first)
parts = second.split()
values = []
for position in range(n):
    values.append(int(parts[position]))
print(values)
print(max(values), min(values))

Output

[8, 3, 12, 5]
12 3

Notice

Build a list of integers first; then max, min, loops and comparisons all work on real numbers.

Reading until 0

Some problems do not tell you the count. Instead, the input ends with a special value, often 0, that is not part of the data. This is the "repeat until done" loop from your Python book: read one value before the loop, and read the next one at the end of the loop.

lines = ["12", "7", "5", "0"]
position = 0
value = int(lines[position])
count = 0
while value != 0:
    count = count + 1
    position = position + 1
    value = int(lines[position])
print(count)

Output

Notice

The 0 stops the loop and is never counted. If the first value is already 0, the loop body never runs and the count is 0.

Put it together: this program reads integers, one per line, until it reads 0. It prints how many values came before the 0, their total, and the largest of them. It is saved as assets/l2.py.

Try it yourself

count = 0
total = 0
largest = 0
value = int(input())
while value != 0:
    if count == 0:
        largest = value
    if value > largest:
        largest = value
    count = count + 1
    total = total + value
    value = int(input())
print(count, total, largest)

Run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

Notice

largest is set from the first value, not started at 0. Test it on assets/l2/2.in, where every value is negative: a program that starts largest at 0 would wrongly print 0.

ACSL input in this book is always integers and words. You never need decimals, so every number you read goes through int(...).

Lesson 3 — Tuples and complete search

The target problem asks for a pair of cards. Python has a neat way to keep two values together: a tuple.

Tuples

A tuple is written with round brackets and commas. You read its parts by position, just like a list.

point = (3, -4)
print(point)
print(point[0], point[1])

Output

(3, -4)
3 -4

Unpacking puts the parts of a tuple into separate variables in one line.

point = (3, -4)
x, y = point
print(x)
print(y)

Output

3
-4

Notice

There must be exactly as many names on the left as parts in the tuple.

Unlike a list, a tuple cannot be changed after it is made: point[0] = 5 is an error. That is what you want for a pair of values that belong together, such as the two cards of an answer. To "change" it, you make a new tuple, for example point = (5, -4).

A comma on the right-hand side also makes a tuple. That gives a one-line swap: Python builds the tuple (b, a) from the old values first, then unpacks it.

a = 1
b = 2
a, b = b, a
print(a, b)

Output

2 1

Lists of tuples

A list can hold tuples, and a for loop can unpack each one as it goes.

points = []
points.append((2, 5))
points.append((-1, 3))
points.append((4, -6))
for x, y in points:
    print(x + y)

Output

7
2
-2

Notice

points.append((2, 5)) has two sets of brackets: the outer ones belong to append, the inner ones make the tuple.

One more built-in helps with points: abs(n) gives the size of n without its minus sign, so abs(-6) is 6 and abs(4) is 4.

point = (4, -6)
x, y = point
print(abs(x) + abs(y))

Output

Complete search: try every candidate

Many contest problems are small enough that you can simply try every possibility and check each one. This is called complete search (or brute force). Before you look for anything clever, ask: "How many candidates are there? Can I just try them all?"

Example: which whole numbers x and y, each from 0 to 10, make 3x + 5y equal to 31?

answers = []
for x in range(11):
    for y in range(11):
        if 3 * x + 5 * y == 31:
            answers.append((x, y))
print(answers)

Output

[(2, 5), (7, 2)]

Notice

The nested loops try all 11 × 11 = 121 combinations, and each answer is stored as a tuple (x, y).

Every pair of positions

To try every pair of cards, use two loops over positions. The inner loop starts at i + 1, so each pair is tried exactly once and a card is never paired with itself.

values = [4, 5, 1, 8]
for i in range(len(values)):
    for j in range(i + 1, len(values)):
        print(i, j, values[i] + values[j])

Output

Notice

4 cards give 6 pairs. With N cards there are N × (N − 1) / 2 pairs; for N = 1000 that is 499,500, which a computer checks in a moment.

Counting and choosing the best

Complete search usually does one of two things with the candidates: count the ones that pass a test, or keep the best one. A tuple is a good way to remember the best candidate found so far.

values = [4, -7, 5, 1, -8]
count = 0
best = (values[0], values[1])
for i in range(len(values)):
    for j in range(i + 1, len(values)):
        if values[i] + values[j] > 0:
            count = count + 1
        if values[i] * values[j] > best[0] * best[1]:
            best = (values[i], values[j])
print(count)
print(best)

Output

3
(-7, -8)

Notice

best starts as a real pair (the first two cards), never as a made-up value, so it works even when every product is negative. The winning product here is -7 × -8 = 56: two negatives beat the positive pairs.

Put it together: here is a complete solution to the problem at the top of the unit. It reads N and T, reads the cards, tries every pair, counts the pairs that add up to T, and keeps the first one as a tuple. It is saved as assets/l3.py.

Try it yourself

first = input().split()
n = int(first[0])
target = int(first[1])
parts = input().split()
values = []
for position in range(n):
    values.append(int(parts[position]))
count = 0
found = (0, 0)
for i in range(n):
    for j in range(i + 1, n):
        if values[i] + values[j] == target:
            count = count + 1
            if count == 1:
                found = (values[i], values[j])
print(count)
if count == 0:
    print("NONE")
else:
    a, b = found
    print(a, b)

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

Notice

The if count == 1 test saves only the first pair found; later pairs are counted but not saved. Because i grows in the outer loop and j in the inner loop, the first pair found is the leftmost one, exactly as the problem defines "first".

Before you trust a solution, test the edges the constraints allow: no pair at all (assets/l3/2.in prints 0 and NONE), every card the same (assets/l3/3.in), and negative values (assets/l3/4.in).

Recap

An ACSL answer must match exactly, so predict each printed line before you run it.
input().split() breaks a line into pieces, and int() turns each piece into a number.
When the count is not given, keep reading until the stop value, such as 0.
for i in range(n) with for j in range(i + 1, n) visits every pair of positions exactly once.
Complete search: try every candidate, count the ones that work, and keep the best one.

You can now read a contest problem's input, search every possibility, and print the exact answer it asks for.