Published in journal "Software systems and computational methods", 2012-1 in rubric "Educational software systems", pages 17-27.
Resume: The article contains the solution of all nine Olympiad tasks. The subjects of those tasks are related to the construction of rational data structures, integer arithmetic, computational geometry, graph computations, heuristics sele ction and extremes finding. An algorithm of finding the maximum bandwidth on graph edges for two nonintersecting paths if given. This algorithm with almost no change can be used to find two nonintersecting paths on a graph of minimum total cost. The article discloses a way to determine the possibility of a non-rotating separation of a flat geometric figure in a polygon shape cut. One of the problems has significantly increased the dimen sion of the source data com pared to the known problem. The article suggests a solution with two different ways of solving the task, depending on the dimension of the original data. The rest of the tasks are alike to well known, but require a different solution. Those are the problem of placing queens on the chessboard and the problem of optimum sawing lumber.
Keywords: Software, international, olympaid, internet-olympaid, student, programming, informatics, problem, algorithm, solution
1. Men'shikov, F. V. Olimpiadnye zadachi po programmirovaniyu / F. V. Men'shikov. – SPb.: Piter, 2003. – 315 s.
2. Porublev, I. N. Algoritmy i programmy. Reshenie olimpiadnykh zadach / I. N. Porublev, A. B. Stavrovskiy. – M.: Izd. dom «Vil'yams», 2007. –480 s.
3. Skiena, S. S. Olimpiadnye zadachi po programmirovaniyu. Rukovodstvo po podgotovke k sorevnovaniyam / S. S. Skiena, M. A. Revilla. – M.: KUDITs-OBRAZ, 2005. – 416 s.
7. http://ru.wikipedia.org/wiki/Dvoichnyy poisk.
Correct link to this article:
just copy this link to clipboard