Carry out the steps the statement describes
Some statements describe a process in full: what there is at the start, and what happens in each step. They then ask how things stand at the end, or how many steps it takes for something to happen. When the number of steps is small enough, the direct method is the right one. We keep the current state in variables, apply the rule for one step, and repeat. A program that does this is a simulation.
Writing a simulation means reproducing the statement's rules exactly. Before writing one, check that it is fast enough by multiplying the number of steps by the work in one step.
You get a non-negative integer num. In one step, divide it by 2 if it is even, or subtract 1 if it is odd. Return how many steps it takes to reach 0.
Constraints
Sample 1 · Input
num = 14
Output
6
Sample 2 · Input
num = 8
Output
4
From 14 the values are 14, 7, 6, 3, 2, 1, 0, which is six steps. The state is the current number and the count of steps so far, and the loop applies one step at a time until the number is 0:
def number_of_steps(num):
steps = 0
while num > 0:
if num % 2 == 0:
num //= 2
else:
num -= 1
steps += 1
return steps
print(number_of_steps(14))
print(number_of_steps(8))Output: 6 and 4, the two samples.
A while loop fits because the statement says when the process ends, not how many steps it has. We should be sure that it does end. Every step makes the number smaller, by halving it or by subtracting 1, and a whole number that keeps getting smaller must reach 0.
We can also bound the number of steps. Subtracting 1 from an odd number leaves an even number, so two subtractions never come in a row: there is a halving between them. Every step makes the number smaller, and each halving divides it by 2, so after 19 halvings the number is at most . By then it is 1 or 0, so there are at most 19 halvings. With at most one subtraction before each halving and one more to take 1 to 0, that is at most steps. Trying every allowed input gives a maximum of 38, far inside any time limit.
A process with several values
Most processes have more than one value to keep track of. The next one has three amounts, and each step changes a different pair of them.
Farmer John has three buckets of milk, each with a capacity and a current amount. He pours bucket 1 into bucket 2, then 2 into 3, then 3 into 1, then 1 into 2 again, and so on, 100 pours in all. Each pour moves as much milk as it can, stopping when the source bucket is empty or the target bucket is full. Print how much milk each bucket holds after the 100th pour.
Line of mixmilk.in holds the capacity and the amount of bucket . Print the three final amounts to mixmilk.out, one per line.
Constraints
Sample · Input
10 3 11 4 12 5
Output
0 10 2
There are only 100 pours and each one changes two numbers, so simulating them directly is fast enough. Before writing code, we work the first five pours of the sample by hand, writing A, B and C for buckets 1, 2 and 3.
| Pour | From → to | Amount poured | A | B | C |
|---|---|---|---|---|---|
| start | 3 | 4 | 5 | ||
| 1 | A → B | 3: A is empty | 0 | 7 | 5 |
| 2 | B → C | 7: B is empty and C is full | 0 | 0 | 12 |
| 3 | C → A | 10: A is full | 10 | 0 | 2 |
| 4 | A → B | 10: A is empty | 0 | 10 | 2 |
| 5 | B → C | 10: B is empty and C is full | 0 | 0 | 12 |
Each row is computed the same way. A pour stops when the source is empty or the target is full, so the amount it moves is the smaller of two numbers: the milk in the source and the free space in the target.
In pour 1, bucket A holds 3 and bucket B has free, so 3 moves. In pour 2, B holds 7 and C has free, so 7 moves.
The state is the three amounts. We keep them in a list milk, beside a list cap of the capacities, with the buckets numbered 0, 1 and 2. That numbering gives a short way to say which bucket pours into which. Counting the pours from 0, pour goes from bucket i % 3 to bucket (i + 1) % 3. The remainders run 0, 1, 2, 0, 1, 2 and so on, so the pours go round the three buckets, and bucket 2 pours back into bucket 0.
# For the USACO judge, uncomment these two lines:
# sys.stdin = open("mixmilk.in")
# sys.stdout = open("mixmilk.out", "w")
cap = [0, 0, 0]
milk = [0, 0, 0]
for i in range(3):
cap[i], milk[i] = map(int, input().split())
for i in range(100):
a, b = i % 3, (i + 1) % 3
amount = min(milk[a], cap[b] - milk[b])
milk[a] -= amount
milk[b] += amount
for value in milk:
print(value)On the sample input, the program prints 0, 10 and 2.
The order of the three lines inside the loop matters. amount is computed first, from the two buckets as they stand before the pour, and only then do both buckets change. Suppose we dropped the variable and wrote the min expression out twice, first subtracting it from milk[a] and then adding it to milk[b]. By the second line milk[a] is already 0, so the min is 0 as well: in pour 1, bucket A would lose its 3 and bucket B would gain nothing.
This is one of the older USACO problems that use files, so a submission to USACO needs the two lines that point standard input and output at mixmilk.in and mixmilk.out, which the listing carries as comments.
Build the next state from the old one
In Mixing Milk each pour changed two numbers. In other processes a step computes many new values at once, and each of them has to be computed from the old values, not from new values computed a moment earlier. Pascal's triangle is built that way, one row at a time.
Return the first numRows rows of Pascal's triangle. Each row starts and ends with 1, and every value in between is the sum of the two values diagonally above it.
Constraints
Sample 1 · Input
numRows = 5
Output
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Sample 2 · Input
numRows = 1
Output
[[1]]
The state is the current row, and one step turns it into the next row:
The highlighted inner values are , and , each the sum of two neighbours in the old row, and a 1 goes on each end.
def generate(num_rows):
rows = [[1]]
for _ in range(num_rows - 1):
prev = rows[-1]
inner = [prev[j] + prev[j + 1] for j in range(len(prev) - 1)]
rows.append([1] + inner + [1])
return rows
for row in generate(5):
print(*row)Output, one row per line: the five rows of the first sample.
The inner loop is the third row of the Loop bounds table: range(len(prev) - 1) pairs each position of the old row with the one after it. The new row is built in a list of its own while prev stays as it was, so every sum reads two old values.
Without the separate list the sums go wrong. Suppose we tried to turn the old row into the new one in place: add a 1 to the end of [1, 3, 3, 1], then replace each inner position , from left to right, by the sum of positions and . Position 1 becomes , which is right. Position 2 should become , but position 1 now holds 4, so it becomes , and position 3 goes wrong after it:
So when every new value depends on old values, we build the new state separately and replace the old one afterwards, as the listing does. The same holds when a whole grid changes in one step: build the next grid from the current one, then swap them.
Move on a grid with direction arrays
Many simulations move a marker around a grid: a robot or a piece on a board. The state is the marker's row r, its column c and the direction it faces. An if branch for each of the four directions would work, but there is a shorter way. We number the directions and store how each one changes the row and the column in two lists, dr and dc.
| d | Direction | dr[d] | dc[d] | From row 1, column 1 we reach |
|---|---|---|---|---|
0 | right | 0 | 1 | row 1, column 2 |
1 | down | 1 | 0 | row 2, column 1 |
2 | left | 0 | -1 | row 1, column 0 |
3 | up | -1 | 0 | row 0, column 1 |
With d as the current direction, one step forward leads to row r + dr[d] and column c + dc[d], whichever direction that is. The directions are listed in clockwise order, so turning is arithmetic on d. A right turn is d = (d + 1) % 4: from direction 3, up, it gives , right. A left turn is three right turns, d = (d + 3) % 4.
You get a positive integer . Return an grid holding the numbers 1 to in clockwise spiral order, starting at the top-left corner.
Constraints
Sample 1 · Input
n = 3
Output
[[1,2,3],[8,9,4],[7,6,5]]
Sample 2 · Input
n = 1
Output
[[1]]
A marker starts in the top-left corner facing right and repeats three steps times:
- Write the next number in the current cell.
- If the cell ahead is outside the grid or already filled, turn right.
- Step forward.
The grid starts full of zeros, so a filled cell is one that does not hold 0.
def generate_matrix(n):
grid = [[0] * n for _ in range(n)]
dr, dc = [0, 1, 0, -1], [1, 0, -1, 0]
r = c = d = 0
for value in range(1, n * n + 1):
grid[r][c] = value
nr, nc = r + dr[d], c + dc[d]
if not (0 <= nr < n and 0 <= nc < n) or grid[nr][nc] != 0:
d = (d + 1) % 4
nr, nc = r + dr[d], c + dc[d]
r, c = nr, nc
return grid
for row in generate_matrix(3):
print(*row)Output, one row per line: 1 2 3, 8 9 4, 7 6 5.
In the if, the bounds test has to come first. or stops as soon as its left side is true, so grid[nr][nc] is read only for a cell inside the grid. Written the other way round, the test would read grid[0][3] at the top-right corner of the sample and raise IndexError.
The loop runs once for each cell, times. After the last number the marker turns and steps once more, onto a cell that is filled or outside the grid, but the loop has ended and nothing is read or written there.
Read a grid in spiral order
The next problem asks for the opposite. The grid is given, and we list its values along the same path.
You get a grid matrix with rows and columns. Return all of its values in clockwise spiral order: along the top row, down the right column, back along the bottom row, up the left column, and then the same again one ring further in.
Constraints
Sample 1 · Input
matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output
[1,2,3,6,9,8,7,4,5]
Sample 2 · Input
matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output
[1,2,3,4,8,12,11,10,9,5,6,7]
The marker walk works here too, with a second grid to record which cells have been visited. The spiral is regular enough to do without one. It is made of straight legs: along the top row, down the right column, back along the bottom row and up the left column. So we keep four boundaries, top, bottom, left and right: the first and last rows and the first and last columns that have not been listed yet. Each leg lists one row or one column and then moves that boundary inward. The walk ends when the boundaries cross.
def spiral(grid):
top, bottom = 0, len(grid) - 1
left, right = 0, len(grid[0]) - 1
out = []
while top <= bottom and left <= right:
for c in range(left, right + 1):
out.append(grid[top][c])
top += 1
for r in range(top, bottom + 1):
out.append(grid[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
out.append(grid[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
out.append(grid[r][left])
left += 1
return out
print(*spiral([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]))Output: 1 2 3 4 8 12 11 10 9 5 6 7, the second sample.
The four legs are four loops: forward along a row, forward down a column, and two loops that count down. The widget runs the walk on the second sample, the grid of 3 rows and 4 columns. Its dashed box spans rows top to bottom and columns left to right, the cells not yet listed.
The while condition is tested only at the start of an iteration, and top and right move in the middle of one. That is why the two legs that come back, along the bottom row and up the left column, have tests of their own.
Take a grid with a single row, [[1, 2, 3]]. The first leg lists 1, 2, 3 and moves top to 1, which is below bottom, still 0. Nothing is left to list. Without the test, the third leg would walk row 0 again from right to left, and the function would return 1, 2, 3, 2, 1. Setting the widget to 1 row and 3 columns and switching its guards off shows this happening. The test before the left column does the same job on a grid with a single column.
Each leg lists cells inside the box and then moves a boundary past them, so no cell is listed twice, and the walk goes on until the box is empty, so none is missed.
Skip ahead when a process repeats
The processes so far took at most a few hundred steps. The next statement asks for up to a billion rounds.
cows stand in a line, labelled 1 to from the left. One round of exercise has two steps: the cows in positions through reverse their order, and then the cows in positions through reverse theirs. The cows repeat the round times. Print the final label at each position, one per line.
swap.in holds and on the first line, and on the second, and and on the third. The answer goes to swap.out.
Constraints
Sample · Input
7 2 2 5 3 7
Output
1 2 4 3 5 7 6
In the sample, round 1 first reverses positions 2 through 5 and then positions 3 through 7:
A second round gives the expected output, 1 2 4 3 5 7 6.
We count before simulating. One round reverses two ranges of at most 100 cows each, so it moves at most 200 cows, and can be :
A judge runs roughly simple operations a second, so the direct simulation takes about 2,000 seconds, over half an hour.
The simulation can be cut short because the process repeats. Here is the sample continued by hand for four rounds:
Round 4 has put every cow back where it started. The same round applied to the same line gives the same result, so rounds 5 to 8 repeat rounds 1 to 4, and so does every group of four rounds after them. The number of rounds after which the line first returns to its starting order is its period. Here the period is 4.
Once we know the period , any multiple of rounds changes nothing, so only the remainder of matters:
For the sample, , and the answer is the line after 2 rounds. So the program simulates rounds until the line equals the starting line, counting them to find , and then simulates more.
# For the USACO judge, uncomment these two lines:
# sys.stdin = open("swap.in")
# sys.stdout = open("swap.out", "w")
def one_round(cows, a1, a2, b1, b2):
cows[a1 - 1:a2] = cows[a1 - 1:a2][::-1]
cows[b1 - 1:b2] = cows[b1 - 1:b2][::-1]
n, k = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())
start = list(range(1, n + 1))
cows = start[:]
period = 0
while True:
one_round(cows, a1, a2, b1, b2)
period += 1
if cows == start:
break
for _ in range(k % period):
one_round(cows, a1, a2, b1, b2)
for label in cows:
print(label)On the sample input, the period is 4 and the program prints 1, 2, 4, 3, 5, 7, 6.
The statement numbers positions from 1, so positions through are the indices from a1 - 1 up to, but not including, a2, and [::-1] reverses that slice. cows = start[:] copies the starting line; with cows = start the two names would be one list, and the comparison would always be true. The while True loop runs a round before it compares, because the line equals the start before any round has run. When it ends the line is back at the start, so the last loop's rounds begin from the starting line. Like Mixing Milk, this is an older USACO problem, so the listing carries the two file lines as comments.
This plan relies on two facts about the process. The first is that the line does return to its starting order. There are only finitely many orders of cows, so the rounds must sooner or later produce an order they produced before.
Say the line after round 7 is the same as the line after round 3. A round can be undone, by reversing the same two ranges in the opposite order. Undo 3 rounds on each of the two lines: the line after round 3 goes back to the start, and the line after round 7 goes back to the line after round 4. The two lines were equal, and undoing the same rounds keeps them equal, so round 4 leaves the cows in their starting order. The same argument shows that if rounds leave the same order, the line is back at the start after rounds.
The second fact is that the period is short. We ran a program over every pair of ranges for , and the longest period it found is 29,640 rounds. Finding and then running the remainder take fewer than rounds of at most 200 moves, under 12 million moves where the direct simulation needed .
Repeating without returning to the start
Mixing Milk repeats as well, in a different way. In its hand table the buckets hold 0, 0, 12 after pour 2 and again after pour 5, with the same bucket about to pour, so from pour 2 on the amounts repeat every 3 pours. But the starting amounts 3, 4, 5 never come back. The cow line returned to its start because a round can be undone. A pour cannot: pour 2 turns 0, 7, 5 into 0, 0, 12, and pour 5 turns 0, 10, 2 into the same amounts, so two different states lead to the same one and the argument above does not apply.
For a process like that, waiting for the starting state would never end. The general method is to remember every state seen so far, with the step at which it appeared, and to stop at the first state that appears twice. The Pigeonhole principle lesson works through it.
Count the steps before simulating
- Number of Steps
at most 39 steps - Each step is one test and one update.
- Mixing Milk
100 pours - Each pour is a few operations on three numbers.
- Pascal's Triangle
465 values - Row , counted from 0, has values, and for the 30 rows allowed.
- Spiral Matrix II and Spiral Matrix
one step per cell - At most cells to fill and to list.
- Swapity Swap, every round
moves - About 2,000 seconds, far past any time limit.
- Swapity Swap, with the period
under moves - Fewer than rounds of at most 200 moves, with at most 29,640.
Common simulation mistakes
A
whileloop whose update can jump past the stopping value.- Where it breaks
while n != 0: n -= 2from 5 goes 5, 3, 1, -1, -3 and never stops.- The fix
- Stop on a range,
while n > 0.
In C++, turning left with
d = (d - 1) % 4.- Where it breaks
- From direction 0 it gives , because a C++ remainder keeps the sign of the number being divided, and
dr[-1]is outside the array. Python gives 3 for the same expression. - The fix
- Turn left with
d = (d + 3) % 4, which is never negative.
Looking for the period with a loop that compares before it runs a round.
- Where it breaks
- In Swapity Swap the line equals the start before any round, so
while cows != startruns no rounds, the period stays 0, andk % perioddivides by zero. - The fix
- Run one round first, then compare.
Recall Mixing Milk asks for 100 pours. Suppose it asked for $10^{15}$ pours on the same sample. What would the buckets hold?
From pour 2 on, the amounts repeat every 3 pours: 0, 0, 12 after pours 2, 5, 8 and so on, 10, 0, 2 after pours 3, 6, 9, and 0, 10, 2 after pours 4, 7, 10. So for any pour from the second on, the amounts depend only on the pour number's remainder when divided by 3. leaves remainder 1, the same as pour 4, so the buckets would hold 0, 10 and 2. Pour 100 also leaves remainder 1, which agrees with the sample output.
