Российская система образования в области точных наук по праву считается одной из лучших в мире. В стране сложилась уникальная система поиска и подготовки молодых талантливых математиков, физиков и программистов. Ее качество подтверждается высшими наградами, которые ежегодно завоевывают российские школьники на международных соревнованиях. Так, на четырех из последних шести международных олимпиад по информатике абсолютное первое место занимали школьники из России, обогнав свыше двухсот конкурентов более чем из пятидесяти стран мира. Основу такой подготовки ребят обеспечивают российские педагоги-энтузиасты высочайшей квалификации. Те, кто не ударился в коммерцию с приходом рыночных отношений, а остался верен своему делу — прививать ребятам любовь к знаниям. Те, кто работает не за деньги и славу, а потому что не мыслят без этой работы своей жизни.
Однако для качественной подготовки школьников к мировым первенствам усилий этих педагогов-одиночек было бы недостаточно. Международные олимпиады имеют свою специфику, свои правила, на них встречаются определенные классы задач, которые обязательно нужно уметь решать. Школьники, прошедшие через эти соревнования, знают, что полноценную подготовку к ним обеспечивают учебно-тренировочные сборы, проводимые два раза в год — две недели летом и одна неделя зимой. Участники этих сборов — победители Всероссийской олимпиады по информатике — слушают лекции по информатике и тренируются по 4–6 часов в день в решении олимпиадных задач. Большое внимание уделяется оценке эффективности алгоритмов, методам тестирования программ, технике работы с компьютером, умению внимательно читать условия задач и анализировать приведенные в них ограничения.
Преподавателями на этих сборах работают победители предыдущих международных олимпиад, «нюхавшие порох» и имеющие за спиной большой багаж знаний и опыт решения задач по информатике. Тем самым, знания передаются по эстафете от одних ребят к другим, постоянно дополняясь и обобщаясь. Сейчас уже можно говорить о сложившейся школе по отбору и подготовке национальной сборной России, ее особенностях и традициях, проявляющихся как в методике проведения сборов, так и в тематике задач и круге лекций, читаемых школьникам. Родоначальником традиций этой школы по праву можно назвать замечательного петербургского преподавателя Антона Суханова.
В данной книге авторы попытались собрать те задачи, которые использовались для тренировок национальной сборной России. Задачи поделены на шесть глав. Первые пять из них посвящены следующим темам: динамическое программирование, перебор с возвратом, алгоритмы на графах, вычислительная геометрия и комбинаторные алгоритмы. Конечно, некоторые из задач книги можно было бы отнести сразу к нескольким из перечисленных тем. Например, геометрические задачи на поиск кратчайшего пути обычно сводятся к нахождению кратчайшего пути в графе. В таких случаях мы старались либо выявить «доминирующую» тему, либо включить задачу в более позднюю из глав. Наконец, шестая глава составлена из тех задач, которые нельзя отнести ни к одной из первых пяти. Решение большей части из них не требует знания указанных тем, несколько же задач используют идеи сразу несколько тем. Например, для решения задачи 6.12 необходимо владение синтаксическим анализом, динамическим программированием и алгоритмами на графах.
К большинству задач в этой книге даны комментарии о способе их решения. Естественно, каждая задача может быть решена различными способами. Мы стремились указать тот из них, который нам представляется наиболее правильным и простым для программирования. Когда при создании книги возник вопрос о том, вынести ли комментарии в конец книги или вставить их сразу вслед за условиями, было решено остановиться на втором варианте. Это удобнее для преподавателей, а тому, кто упражняется в решении задач, авторы настоятельно рекомендуют подумать над задачей и попытаться запрограммировать ее самому, прежде чем читать комментарии. Конечно, разбивка задач на главы уже является определенной подсказкой, но это сделано сознательно, чтобы обеспечить возможность целенаправленной проработки нужных тем.
Ко всем задачам приведены подробные форматы входного и выходного файлов. Этим мы преследовали две цели. Во-первых, это упрощает преподавателям использование задач на кружках по программированию. Во-вторых, это позволяет нам предоставить к задачам тесты и тестирующие программы — их можно получить на . Все входные данные подразумеваются корректными, и их проверка не требуется.
В представленной книге мы не ставим своей целью научить программированию или основным алгоритмам, предполагая, что читатель с этим уже достаточно знаком. В ряде мест была использована терминология языка программирования Turbo Pascal. Авторы старались приводить ссылки на литературу каждый раз, когда упоминаются стандартные концепции или алгоритмы, которые они не считают возможными пояснить в рамках этой книги. Для лучшего понимания материала, приведенного здесь, мы рекомендуем ознакомиться с работами [Вирт 89], [Липский 88], [Окулов 98], [Шень 95] или обращаться к ним по мере необходимости. Тем, кому задачи, приведенные ниже, покажутся слишком сложными, мы советуем начать со сборников задач по информатике [Брудно 90], [Бадин 95] и [Шень 95].
Авторы будут рады всем пожеланиям, отзывам и замечаниям по содержанию этой книги. Пишите нам по адресу onzi@narod.ru.
Мы выражаем благодарность своим друзьям Антону Суханову, Илье Миронову, Марку Сандлеру и Дмитрию Васюре, вместе с которыми нам довелось тренировать сборную команду России. Формулировки ряда оригинальных задач, приведенных в этой книге, принадлежат им. Кроме того, они участвовали в разработке программ-решений, тестов и тестирующих программ.
Мы хотим поблагодарить также членов жюри Всероссийской олимпиады по информатике Алексеева А.В., Андрееву Е.В., Волченкова С.Г., Кирюхина В.М., Лелюха В.Д., Овсянникова А.П., Овсянникову Т.В., Окулова С.М., Прохорова В.В., Романовского И.В., Серегина И.А., чьи задачи или идеи задач могли быть здесь использованы. Спасибо жюри Московской городской студенческой олимпиады по программированию за электронную версию условия задачи 2.5.
Особую признательность хотелось бы выразить декану факультета информатики Вятского государственного педагогического университета Окулову Станиславу Михайловичу за любезное разрешение использовать сайт http://informatics.vspu.kirov.ru/anton для размещения тестов к задачам, приведенным ниже. Отдельное спасибо лаборатории вычислительных методов МГУ и Панкратьеву Евгению Васильевичу за предоставленную возможность использования их компьютерной техники при подготовке ряда глав этой книги.
Один из авторов благодарит своих друзей Дмитрия и Татьяну, напоминавших ему в процессе работы над изданием о необходимости употребления не только духовной, но и физической пищи. Спасибо им за вкусные обеды, без которых многие строки этой книги были бы написаны в голодном состоянии, от чего читатель бы, разумеется, не выиграл.
И, наконец, выражаем огромную благодарность нашим учителям Окулову Станиславу Михайловичу и Андреевой Елене Владимировне за то, что они открыли для нас удивительный мир искусства программирования, красотой которого мы не устаем восхищаться и поныне. Учитель, перед именем твоим смиренно преклоним колени…