Solving a problem by doing its steps
Suppose you put 100 yen in a bank that adds 1% interest once a year and drops any fraction of a yen. How many years until you have 1,000 yen? You could look for a formula, but you don't need one. Start at 100, add one year of interest, check whether you have reached 1,000, and repeat. The number of times you repeated is the answer.
You have written this kind of loop before. The halving loop changed n and steps on every pass, and the answer was whatever steps held when the loop stopped. The bank needs the same loop with a different rule inside.
Many judge problems are like this, only with a longer story. Two bears put on weight every year. Three people pass cookies around. Each problem describes a process that moves in steps, and asks how things stand at the end, or how many steps it takes to get there. When the problem says exactly what happens in each step, you can solve it by doing the steps: a loop where one pass is one step of the story. This is called a simulation, and it needs nothing beyond the loops you already know.
The work is in getting the story into the loop correctly. For each simulation in this lesson, we will answer four questions:
- Which numbers describe the process at a given moment?
- How do they change in one step, and in what order?
- When does the process stop?
- How can you check that the program does what the story says?
Definition
State
The state of a process is the set of values that describe it completely at one moment. The state now and the rule for one step are enough to work out the state after the step.
Choosing the state
Here is a short problem to practise the first question on.
Limak the bear weighs and his brother Bob weighs , with . Every year Limak's weight triples and Bob's weight doubles.
After how many full years is Limak strictly heavier than Bob?
Constraints
Sample 1 · Input
4 7
Output
2
Sample 2 · Input
4 9
Output
3
Sample 3 · Input
1 1
Output
1
The state is Limak's weight and Bob's weight, which decide when to stop, and the number of years that have passed, which is the answer. Three numbers, then: a, b and years. The story mentions no other quantity that changes, so these three are the whole state.
Before writing code, run the process by hand on the first sample, 4 7, with one row for each moment you check whether Limak is heavier yet.
years | a (Limak) | b (Bob) | Limak heavier? |
|---|---|---|---|
| 0 | 4 | 7 | no, keep going |
| 1 | 12 | 14 | no, keep going |
| 2 | 36 | 28 | yes, stop and print 2 |
After one year Limak weighs and Bob weighs , so Bob is still heavier. After two years they weigh 36 and 28, and Limak has passed him. The table ends on the expected output, 2, so this reading of the story agrees with the first sample.
The table as a loop
Each row of the table becomes one pass of a while loop. The condition is the question in the last column, turned around: the loop keeps going while Limak is not yet heavier, that is, while a <= b.
a, b = map(int, input().split())
years = 0
while a <= b:
a = a * 3
b = b * 2
years = years + 1
print(years)Changing a before b makes no difference here, because Limak's new weight depends only on his old weight and Bob's only on Bob's.
The condition is checked only before each pass, never in the middle of the body. On 4 7, the first pass sets a to 12 while b is still 7, so for one line Limak is heavier. The loop carries on to the end of the pass, where b doubles to 14, and only then checks a <= b again. One pass is one whole year of the story.
Checking the program against a hand trace
A program that passes one sample can still be wrong, and a wrong final number does not show which step went wrong. A better check is to make the program show its state after every step, then compare those lines with a trace done by hand. The first line where they disagree points at the step the program gets wrong.
For the second sample, 4 9, the hand trace gives 12 and 18 after the first year, then 36 and 36, then 108 and 72. In the second year the weights are equal, and the problem asks for Limak to be strictly heavier, so the process keeps going. One print line inside the loop shows the state after each year.
a, b = map(int, input().split())
years = 0
while a <= b:
a = a * 3
b = b * 2
years = years + 1
print("after year", years, ":", a, b)
print(years)The three printed lines match the hand trace, and the answer is 3. With while a < b, the loop would stop at 36 and 36, and the trace would end after its second line with a wrong answer of 2.
The extra lines are for you only. Delete the trace before submitting, because the judge compares every printed line and would mark the extra ones Wrong Answer.
Updating several values at once
In Bear and Big Brother each value changed on its own. In the cookie exchange every new value depends on the old values of the others.
Three people have , and cookies. In one action, all three at the same moment split their cookies into two halves and give one half to each of the other two people.
They repeat the action until someone holds an odd number of cookies. How many actions do they perform? The answer may be infinite; then print -1.
Constraints
Sample 1 · Input
4 12 20
Output
3
Sample 2 · Input
14 14 14
Output
-1
Sample 3 · Input
454 414 444
Output
1
Take one action from the first sample, 4, 12 and 20. The first person gives away all 4 and receives half of each other person's cookies, . In general, the first person ends with , the second with and the third with . So after one action the three counts are 16, 12 and 8.
A first attempt writes the three rules as three lines: a = (b + c) // 2, then b = (a + c) // 2, then c = (a + b) // 2. By the time b is computed, a is already 16. The first line replaced the old 4, so b becomes where the rule needs , and the program prints 1 instead of 3. A line overwrote a value that a later line still needed. This is the bug to look for whenever one step changes several values.
The story says the three people act at the same moment, so every new value must come from the old state. Changing several variables as if at one moment is a simultaneous update. Python does it in one line, a, b, c = (b + c) // 2, (a + c) // 2, (a + b) // 2. It works out all three values on the right side first, while a, b and c still hold the old counts, and only then gives the three names their new values.
The exchange with a simultaneous update
Here is the full program, with every new count computed from the old state.
a, b, c = map(int, input().split())
count = 0
while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
a, b, c = (b + c) // 2, (a + c) // 2, (a + b) // 2
count = count + 1
print(count)Python details
The comma on the left of = is the same one that reads two numbers in a, b = map(int, input().split()): several names receive several values at once.
Step through the exchange
Pick a start in the diagram and step through the program one line at a time. The last start, marked (bug), runs the three-line version on 4 12 20: step to the line where b picks up the new a.
Asserting that the total stays the same
A hand trace checks a few steps on one input. A second check runs after every step, on whatever input you give the program: look for a quantity the story never changes, and assert that it stays the same. In the cookie exchange, each person gives away all their cookies and the other two receive them, so the total is the same after every action. On 4 12 20 it is 36 throughout.
Here is the three-line version again, with the total saved before the loop and checked after each action.
a, b, c = map(int, input().split())
total = a + b + c
count = 0
while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
a = (b + c) // 2
b = (a + c) // 2
c = (a + b) // 2
assert a + b + c == total
count = count + 1
print(count)After the first action the counts are 16, 18 and 17, which add up to 51, so the assertion stops the program at the first wrong step instead of letting it print 1. With the simultaneous update in its place, the total stays 36 and the program prints 3. A passing assert prints nothing, so it can stay in a submission; a failing one ends the program, and the judge reports Runtime Error instead of Wrong Answer.
Knowing when to stop
Both simulations so far stop on a condition the story gives: Limak becomes heavier, someone holds an odd number of cookies. Some processes instead run for a number of steps the statement gives, such as 100 rounds, and then a counting for loop does the stopping. A condition has to be exactly right, and the loop also has to stop soon enough. The bank from the start of the lesson asks for both, with a target as large as .
Takahashi keeps 100 yen in a bank that pays 1% interest once a year, compounded. Any fraction of a yen is dropped after each year.
In how many years does the balance first reach yen or more?
Constraints
Sample 1 · Input
103
Output
3
Sample 2 · Input
1000000000000000000
Output
3760
Sample 3 · Input
1333333333
Output
1706
The state is the balance and the number of years. One year adds 1% of the balance, rounded down, which is balance // 100.
On the first sample the balance goes from 100 to 101, 102 and 103 in three years, and 103 has reached , so the answer is 3. The words " yen or more" decide the condition: the loop keeps going while balance < x, and stops as soon as the balance equals .
x = int(input())
balance = 100
years = 0
while balance < x:
balance = balance + balance // 100
years = years + 1
print(years)can be , but that does not make the loop long, because the loop counts years, not yen. You can estimate the number of years before running anything. Growing by 1% a year doubles the balance in about 70 years (). Getting from 100 to means multiplying by , which is about 53 doublings (). So the loop needs roughly passes. Dropping the fractions slows the growth a little, and the program prints 3760. A few thousand passes take about a millisecond.
A process that never stops
The cookie exchange asks for -1 when the actions go on forever, and the exchange program from Updating several values at once never finishes on the second sample, 14 14 14. Traced by hand, each person gives away 14 and receives , so after the action everyone has 14 again. The state has not changed, it is all even, and the same action repeats on every pass.
The condition tests only the current counts, so this loop cannot tell that the counts have repeated. When each state follows from the one before by a fixed rule, a state that repeats sends the process round the same passes forever. Noticing a repeat for any start would mean storing the states seen so far, which a set makes easy.
For this problem, the hand trace already tells us enough. When all three counts are equal, every action leaves them equal and unchanged, so if they are also even, the exchange never stops, and the program checks for that case before the loop. The Deeper read below shows that this is the only endless case, and that every other start stops within 30 actions.
a, b, c = map(int, input().split())
if a == b == c and a % 2 == 0:
print(-1)
else:
count = 0
while a % 2 == 0 and b % 2 == 0 and c % 2 == 0:
a, b, c = (b + c) // 2, (a + c) // 2, (a + b) // 2
count = count + 1
print(count)Deeper read: how many actions the exchange can take
Take the gap between two people, say . After one action the first person has and the second , so the new gap is
Each action halves every gap and reverses its sign. An action only happens when all three counts are even, and the difference of two even numbers is even, so each halving is exact.
If the counts are not all equal, some gap is not zero. That gap is at most in size, and , so it can be halved exactly fewer than 30 times before it becomes odd. An odd gap means one of the two people has an odd count and the other an even one, so the exchange has stopped. If all the gaps are zero instead, every count is the same and stays the same forever, which is the case the program checks first.
Common mistakes
Updating
a, then computing the newbfrom the already changeda.- Where it breaks
- In the cookie exchange,
a = (b + c) // 2followed byb = (a + c) // 2gives 16, 18 and 17 after the first action on4 12 20, so the program prints 1 instead of 3. - The fix
- Compute every new value from the old state: one Python line
a, b, c = ..., or new variablesna,nb,ncin C++ that are copied back after all three are known.
Getting the stopping boundary wrong by one comparison.
- Where it breaks
- With
while a < b, Bear and Big Brother stops at 36 and 36 on4 9and prints 2. Limak is not strictly heavier yet, so the answer is 3. - The fix
- Turn the statement's words into the condition: keep going while Limak is not strictly heavier,
a <= b.
Keeping the fractions the problem says to drop.
- Where it breaks
balance = balance * 1.01grows a little too fast, so the interest problem prints 3703 for1000000000000000000instead of 3760.- The fix
- Stay in integers and round down each year:
balance + balance // 100in Python,balance + balance / 100on along longin C++.
Recall In Bear and Big Brother, with `a = 5` and `b = 10`, how many years does it take, and what are the weights each year?
Two years. After one year the weights are 15 and 20, so Bob is still heavier. After two years they are 45 and 40, and Limak is strictly heavier.
Recall Why does a C++ program for the cookie exchange need the extra variables `na`, `nb` and `nc`?
All three people act at the same moment, so each new count must come from the old counts. Assigning a first would destroy the old a that the new b and c still need, so the new values are computed into separate variables before any old one is replaced.
Key terms
| Term | Meaning |
|---|---|
| simulation | Solving a problem by carrying out the process it describes, one step per pass of a loop. |
| state | The values that describe the process completely at one moment, such as a, b and years. |
| hand trace | A table of the state after each step, worked out on paper, to compare with the program. |
| simultaneous update | Changing several variables as if at one moment, every new value computed from the old ones. |
| stopping condition | The condition that ends the simulation, taken from the statement's exact words. |
