Cheapest cooking

Authors

  • Pavel Töpfer Faculty of Mathematics and Physics, Charles University, Prague

Abstract

The article from the series dedicated to problems of Mathematical Olympiad – category P (programming) discusses different solutions of one theoretical competition problem from the regional round of the 2017/18 school year. The task is to find the cheapest way to cook food with the help of a list of instructions. The input prices of the individual ingredients are given and we can use the food prepared according to the individual recipes as input for other follow-up recipes. Algorithms solving this problem are analogous to known graph algorithms for shortest distances in evaluated graph: Bellman-Ford and Dijkstra algorithms. The article also presents a brief outline of these two graph algorithms. Besides the detailed analysis of the problem, we find in the article three basic variants of the solution with different time complexity. Two of these solutions are written in the form of a sample program.

Downloads

Published

2020-01-29

How to Cite

Töpfer, P. (2020). Cheapest cooking. MATHEMATICS–PHYSICS–INFORMATICS, 29(1), 69–77. Retrieved from https://mfi.upol.cz/index.php/mfi/article/view/487

Issue

Vol. 29 No. 1 (2020)

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.
Licence Creative Commons
Obsah časopisu podléhá licenci Creative Commons Uveďte autora 3.0 Česko