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 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
Practice problems
- [NOIP2014] Rock-Paper-Scissors, The Big Bang Theory Edition - Universal Online Judge
- [OpenJudge 3750] World of Warcraft
- [SDOI2010] Legends of the Pig Kingdoms - LibreOJ
This page is an unofficial English translation of the original OI Wiki page (revision b469442a), machine-translated by Claude Fable 5.2 on 2026-11-16. It has been modified from the original by translation and may contain errors. It is not endorsed by OI Wiki.
Found a translation problem? Report it on GitHub.
Authors of the original page: Ir1d, i-yyi, 24OI-bot, ouuan, zirnc, NachtgeistW, leoleoasd, Enter-tainer, kenlig, StudyingFather, ksyx, H-J-Granger, shuzhouliu, zryi2003, LeiJinpeng, Tiphereth-A, shawlleyw, WException, c-forrest (full contribution history)
All content on this page is provided under the terms of CC BY-SA 4.0 and SATA; additional terms may apply.