What Does This Program Do? - Branching

In Contest 1, WDTPD problems use only IF/THEN/ELSE statements - no loops yet. You’re given pseudocode and input values, and you need to determine the output. The skill is careful line-by-line tracing.

ACSL pseudocode syntax

ACSL uses its own pseudocode that looks like a mix of BASIC and Python. Here’s what you need to know:

INPUT: a, b

IF a > b THEN
    a = a - b
ELSE
    b = b - a
END IF

OUTPUT: a, b

Key syntax rules:

• Variables are single letters or short names (no underscores)
• IF ... THEN ... ELSE ... END IF - the END IF is always explicit
• = is assignment (not comparison)
• Comparison operators: >, <, >=, <=, ==, !=
• Logical operators: AND, OR, NOT
• INPUT: reads values, OUTPUT: prints values
• Integer division uses INT() - e.g., $\text{INT}(7/2)=3$
• MOD gives the remainder - e.g., $7\mathrm{mod}2=1$

The variable table method

The fastest and most reliable way to trace branching programs is to make a table of variables and update it line by line.

Example:

INPUT: x = 15, y = 4

a = x MOD y
b = INT(x / y)
IF a > b THEN
    c = a + b
ELSE
    c = a * b
END IF
OUTPUT: c

Build your table:

Answer: 9

Why this works: You never have to hold values in your head. Every variable has a column, and you can verify each step.

Try it: trace this program

Step through line by line. Watch how the variables change at each IF/ELSE branch.

1INPUT: a, b2a = 103b = 254IF a > b THEN5    x = a - b6ELSE7    x = b - a8END IF9OUTPUT: x

Nested IF statements

ACSL problems often nest conditions inside other conditions. Trace them outside-in.

Example:

INPUT: a = 7, b = 3, c = 5

IF a > c THEN
    IF b > c THEN
        x = a + b + c
    ELSE
        x = a - b + c
    END IF
ELSE
    IF b > c THEN
        x = a + b - c
    ELSE
        x = a - b - c
    END IF
END IF
OUTPUT: x

Trace:

1. Is $a>c$? $7>5$? YES, enter first block
2. Is $b>c$? $3>5$? NO, enter ELSE
3. $x=a-b+c=7-3+5=9$

Answer: 9

Speed tip: Before computing anything, determine which path through the IFs you take. Mark the path first, then compute only the relevant line.

Chained IF (no ELSE)

Watch out for multiple IFs in sequence (not nested). Each one is checked independently.

Example:

INPUT: a = 7, b = 3

IF a > b THEN
    a = a - b
END IF
IF a > b THEN
    b = b + a
END IF
OUTPUT: a, b

Trace:

1. Is $a>b$? $7>3$? YES, so $a=7-3=4$
2. Is $a>b$? $4>3$? YES, so $b=3+4=7$

Answer: 4 7

The trap: Many students think the second IF uses the original value of $a$ ($7$). It doesn’t - it uses the updated value ($4$). In chained IFs, earlier statements affect later ones.

Operator precedence

ACSL follows standard math precedence:

1. Parentheses (innermost first)
2. NOT
3. *, /, INT(), MOD
4. +, -
5. >, <, >=, <=, ==, !=
6. AND
7. OR

Examples:

• $x=3+4\times 2=3+8=11$ (not $14$)
• $y=10\mathrm{mod}3+1=1+1=2$ (MOD before addition)
• $z=\text{NOT}(3>5)\text{AND}(4<6)$ evaluates as $\text{NOT FALSE AND TRUE}$, which is $\text{TRUE AND TRUE}$, which is $\text{TRUE}$

Common ACSL tricks in branching

1. Swapping with a temp variable:

temp = a
a = b
b = temp

This swaps a and b. Recognize the pattern instantly.

2. Min/max selection:

IF a > b THEN
    max = a
ELSE
    max = b
END IF

3. Absolute value:

IF x < 0 THEN
    x = -x
END IF

4. Divisibility check:

IF x MOD 3 == 0 THEN
    OUTPUT: "divisible"
END IF

Common mistakes

1. Not updating variables between chained IFs. Always use the current value, not the original.
2. Confusing = (assignment) and == (comparison). a = 5 sets $a$ to $5$. a == 5 checks if $a$ is $5$.
3. Misreading nested IFs. When IFs are deeply nested, indent your trace to match the nesting level.
4. Misunderstanding INT(). ACSL defines $\text{INT}(x)$ as the greatest integer $\le x$ (the floor function). So $\text{INT}(7/2)=3$, and $\text{INT}(-7/2)=-4$ (not $-3$, because $-4\le -3.5$).

Contest strategy

• Read the entire program first to understand the structure
• Build a variable table before executing any lines
• Mark which branch you take at each IF before computing
• After finding your answer, quickly re-trace to verify
• Typical time: 60-90 seconds per problem