Skip to content

Simulation

This page briefly introduces simulation.

Overview

To simulate is to have the computer carry out the operations that the problem describes.

Simulation problems are known for their code length, their many operations and their intricate logic. Because the code is long, bugs are often hard to track down, and getting it wrong during a contest wastes a lot of time.

Tips

The following advice may help you solve simulation problems faster:

  • Before you start coding, write out the procedure you are going to implement on scratch paper, in as much detail as you can.
  • Make the code as modular as you can: put each part in a function, a struct or a class.
  • Give anything that may come up repeatedly a single uniform representation, which is easier to work with. For example, if a problem gives you times as "YY-MM-DD hh:mm", write one function that converts them to seconds; you will mix things up less often.
  • Debug piece by piece. The advantage of modular code is that each part is easy to debug on its own.
  • Keep a clear head while you code. Do not write down whatever comes to mind; follow the steps you put on paper.

In fact, these steps help with other kinds of problems as well.

Worked example

Climbing Worm

A worm of negligible length is at the bottom of a well \(n\) inches deep. Each time it climbs, it moves up \(u\) inches, but it must rest before it can climb again, and while it rests it slips down \(d\) inches. It then keeps alternating between climbing and resting. What is the minimum number of times the worm has to climb to get out of the well? If the worm is exactly at the top of the well after a climb, we also count it as out.

Approach

The problem guarantees that the worm can get out, that is, \(u\ge n\) or \(u>d\). Under this condition we can simulate directly: a loop repeats the worm's climb and exits once the height climbed is greater than or equal to the depth of the well.

Reference code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include <iostream>

int main() {
  int n = 0, u = 0, d = 0;
  std::cin >> u >> d >> n;
  int time = 0, dist = 0;
  while (true) {  // enumerate with an infinite loop
    dist += u;
    time++;
    if (dist >= n) break;  // leave the infinite loop once the condition holds
    dist -= d;
  }
  std::cout << time << '\n';  // print the result
  return 0;
}
1
2
3
4
5
6
7
8
9
u, d, n = map(int, input().split())
time = dist = 0
while True:  # enumerate with an infinite loop
    dist += u
    time += 1
    if dist >= n:  # leave the infinite loop once the condition holds
        break
    dist -= d
print(time)  # print the result
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int u = input.nextInt();
        int d = input.nextInt();
        int n = input.nextInt();
        int time = 0, dist = 0;
        while (true) {  // enumerate with an infinite loop
            dist += u;
            time++;
            if (dist >= n) {
                break;  // leave the infinite loop once the condition holds
            }
            dist -= d;
        }
        System.out.println(time);   // print the result
        input.close();
    }
}

Practice problems