Simulation

Simulation problems are about imitating real or logical processes step by step.
You’re asked to “simulate” what happens — just like running a small program inside your program!

What does simulation mean?

In competitive programming, simulation means following the rules of a problem carefully and performing each step exactly as described.

You don’t need a fancy algorithm — just replicate what happens, usually in loops.

Here is a simple example of a problem solved with simulation.

Collatz conjecture

Consider the following process.

Start with some given number \(n\).
In each step:
- If \(n\) is even, replace it with \(n/2\).
- If \(n\) is odd, replace it with \(3n+1\).
Print how many steps this process took before \(n\) became \(1\).

You might wonder does this process even must reach \(1\). Well, nobody has an answer for that, as this is a famous mathematical unsolved problem! But we can try simulating it and seeing what happens.

Solution

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;

    int steps = 0;
    while (n != 1) {
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n = 3*n + 1;
        }
        steps++;
    }

    cout << steps << "\n";
    return 0;
}

If n = 3, the program goes like this:

step	n
0	3
1	10
2	5
3	16
4	8
5	4
6	2
7	1

So the answer is 7.

When to use simulation

Simulation is perfect when:

The problem gives you a list of detailed steps or actions.
There is no mathematical shortcut.
You can just follow the process directly.

Common examples:

Games (like tic-tac-toe, snake, etc.)
Movements on a grid (robots, cars, people walking)
String transformations (editing text, rotations)
Managing objects (queues, stacks, or tasks over time)

Simulation pattern

Most simulation problems follow the same pattern:

initialize variables
while (there are still actions left) {
    read next action
    update variables according to rules
}
print final result

You’re basically “playing out” the rules one by one.

Exmple Problems

Robot on a grid

A robot starts at \((0, 0)\). It receives a string of moves made of N, S, E, W. Print its final coordinates.

Solution

#include <iostream>
#include <string>
using namespace std;

int main() {
    string moves;
    cin >> moves;

    int x = 0, y = 0;
    for (char c : moves) {
        if (c == 'N') y++;
        else if (c == 'S') y--;
        else if (c == 'E') x++;
        else if (c == 'W') x--;
    }
    cout << x << " " << y;
}

If input is NNEEWS, the robot ends up at (1, 1).

Game simulation

There are several heros in the game, each having its own strength. Each second, the weakest hero, A, damages the strongest hero, B, and reduces B’s strength by A’s strength. The game stops when some hero’s strength reaches 0. Print how many seconds the game lasted.

Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> strength(n);
    for (int &x : strength) cin >> x;

    int seconds = 0;
    while (true) {
        sort(strength.begin(), strength.end());
        if (strength[0] == 0) break;
        strength[n-1] -= strength[0];
        seconds++;
    }
    cout << seconds;
}

This simulates the entire process exactly as described.

Note

Sometimes, there is a way to skip some simulation steps, and make the whole process faster. Can you think of such a way for the previous example?

Tips for simulation problems

Follow the rules literally. Don’t try to overthink — just do what the problem says.
Use loops and conditionals to handle different cases.
Print intermediate steps while debugging to make sure your logic matches the description.
Be careful with boundaries (e.g., going off the grid or using wrong indices).
Use small test cases to manually verify your code.
Simulate the program with a pen on paper to understand what really happens and code it step-by-step.

Performance tip

Sometimes, simulation can be too slow if the process runs billions of steps. In those cases, you need to find patterns or shortcuts.

For example:

If a process repeats after some number of steps, use math to skip cycles.
If the outcome doesn’t change after a while, stop early.

Advantages

Very straightforward — no fancy algorithms needed
Easy to implement and understand
Works for almost any rule-based process

Disadvantages

Can be slow for large inputs
Easy to make small mistakes when following many steps
Debugging can take time if you don’t print intermediate results

Quick summary

Simulation means mimicking a process step by step.
Perfect for problems that describe exact rules or actions.
Focus on loops, conditionals, and updating variables.
Always check small examples manually.
When it’s too slow — look for repeating patterns!