Excavated intersections (Problems of Mathematical olympiad category P, part 42)
Abstract
In the next part of the cycle of interesting tasks from the Mathematical Olympiad of category P (programming), we will get acquainted with one practical problem from the national round of the 45th year of the Ministry of Defense (the school year 1995/96). The task was to determine the number of different routes between two points in the regular rectangular road network, in which, however, some intersections are impassable. To effectively solve this problem, we will use a relatively well-known programming technique of dynamic programming. We will show the different ways in which such a solution can be implemented, as well as the fact that these methods may differ in terms of the resulting time complexity. The same principles apply to solving many other tasks using dynamic programming.Downloads
Published
2021-08-31
How to Cite
Töpfer, P. (2021). Excavated intersections (Problems of Mathematical olympiad category P, part 42). MATHEMATICS–PHYSICS–INFORMATICS, 30(3), 220–227. Retrieved from https://mfi.upol.cz/index.php/mfi/article/view/555
Issue
Section
Informatics
License
Autoři, kteří publikují v tomto časopise, souhlasí s následujícími body:
- Autoři si ponechávají copyright a garantují časopisu právo prvního publikování, přitom je práce zároveň licencována pod Creative Commons Attribution licencí, která umožňuje ostatním sdílet tuto práci s tím, že přiznají jejího autora a první publikování v tomto časopisu.
- Autoři mohou vstupovat do dalších samostatných smluvních dohod pro neexkluzivní šíření práce ve verzi, ve které byla publikována v časopise (například publikovat ji v knize), avšak s tím, že přiznají její první publikování v tomto časopisu.
Obsah časopisu podléhá licenci Creative Commons Uveďte autora 3.0 Česko
