AIOJ

This page briefly introduces simulation algorithms.

Introduction

Simulation means using a computer to simulate the operations required by a problem.

Simulation problems usually feature a large amount of code, many operations, and complicated ideas. Because they require a lot of code, errors that are difficult to find often occur, and making a mistake during a contest wastes a considerable amount of time.

Techniques

When writing a simulation problem, following the suggestions below may improve your solving speed:

Before writing code, write down the process to be implemented on paper as completely as possible.
In the code, modularize each part as much as possible by writing it as a function, struct, or class.
Concepts that may be used repeatedly can be converted uniformly to simplify processing. For example, if a problem gives you “YY-MM-DD hour:minute”, extract it into a function and convert it to seconds; this reduces confusion between concepts.
Debug in blocks. The advantage of modularization is that each part can be debugged separately.
Keep your thoughts clear when writing code. Do not write whatever comes to mind; follow the steps written on paper.

In fact, the steps above are also helpful when solving other types of problems.

Detailed Example

Climbing Worm

A worm of negligible length is at the bottom of a well $n$ inches deep. It climbs $u$ inches upward each time, but must rest once before climbing again. While resting, it slips $d$ inches. It then repeats the process of climbing and resting. What is the minimum number of climbs needed for the worm to climb out of the well? If the worm reaches the top of the well exactly after a climb, we also consider it to have climbed out.

Solution Idea

Simply simulate the worm's process of climbing the well with a program. Use a loop to repeat the process; exit when the climbing distance is greater than or equal to the depth of the well.

Reference Code

C++

#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;  // Exit the infinite loop when the condition is met
    dist -= d;
  }
  std::cout << time << '\n';  // Output the result
  return 0;
}

Python

u, d, n = map(int, input().split())
time = dist = 0
while True:  # Enumerate with an infinite loop
    dist += u
    time += 1
    if dist >= n:  # Exit the infinite loop when the condition is met
        break
    dist -= d
print(time)  # Output the result

Java

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;  // Exit the infinite loop when the condition is met
            }
            dist -= d;
        }
        System.out.println(time);   // Output the result
        input.close();
    }
}

Simulation

Introduction

Techniques

Detailed Example

Exercises