Читать онлайн «Московские олимпиады по информатике»

МОСКОВСКИЕ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ Под редакцией Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина Москва Издательство МЦНМО 2006 УДК 519. 671 Издание осуществлено при поддержке ББК 22. 18 Департамента образования г. Москвы М82 и Московского института открытого образования Московские олимпиады по информатике / Под ред. Е. В. Ан- М82 дреевой, В. М. Гуровица и В. А. Матюхина — М. : МЦНМО, 2006. — 256 с: ил. ISBN 5-94057-233-2 Книга предназначена для школьников, учителей информатики, студентов и просто любителей решать задачи по программированию. В ней приведены задачи Московских олимпиад по информатике (командных, заочных и личных туров) последних лет. Большинство задач приведены с подробными разборами и комментариями. olympiads. ru/books. Книга снабжена тематическим рубрикатором, в котором задачи упорядочены по темам и сложности. В качестве дополнительного материала читатель найдет в книге статьи о поиске в глубину и методе рекурсивного спуска, а также о том, зачем и как можно учить школьников программированию. УДК 519. 671, ББК 22. 18 Авторы задач и текстов решений: Е. В. Андреева, В. Ю. Антонов, М. А. Бабен- ко, К-А. Батузов, Б. О. Василевский, В. М. Гуровиц, Ю. Е. Егоров, Р. А. Жуйков, Д. Н. Королёв, А. П. Лахно, Я. А. Леонов, А. А. Лунёв, В. А. Матюхин, П. И. Мит- ричев, А. А. Петров, А. О. Тимофеев, М. О. Трухина, А. В. Фонарев, Е. А. Шавлюгин, СВ. Шедов, А. Ю. Юрьев. ISBN 5-94057-233-2 © МЦНМО, 2006 ОГЛАВЛЕНИЕ Введение 6 Условия и решения задач 6 118 Олимпиада I. Заочный тур 2002—2003 учебного года 9 118 Задача I-A. Таймер 9 118 Задача I-B. Домой на электричках 10 118 Задача I-C. Клад 11 119 Задача I-D. Забавная игра 12 119 Задача 1-Е. Целые точки 13 120 Задача 1-Е Степень 14 121 Задача I-G. Игра с фишками 15 121 Задача I-H. Раскопки 17 122 Задача 1-Е Деревни 18 123 Олимпиада II. Заочный тур 2003—2004 учебного года 20 — Задача П-А. Подсчет баллов 20 — Задача П-В. Великая сеча 21 — Задача П-С. Водостоки 22 — Задача II-D. Коллекционирование этикеток 23 — Задача П-Е. Еловая аллея 24 — Задача П-Е Шашки 25 — Задача II-G. Мышка с колесиком 28 — Задача П-Н. «Левый лабиринт» 30 — Задача П-Е Дремучий лес — 2 31 — Задача II-J. Анаграммер 32 — Олимпиада III. Личная олимпиада 2003—2004 учебного года 34 125 Задача III-А. Наибольшее произведение 34 125 Задача Ш-В. Покупка билетов 34 130 Задача III-C. Вырезанные фигуры 36 133 Задача III-D. Квадрат 39 141 Задача III-E. Поле чудес 40 144 Задача Ш-Е Детская игра со спичками 41 147 Задача III-G. Реклама 42 154 Олимпиада IV. Командная олимпиада 2003—2004 учебного года ... 44 — Задача IV-A. Перегоны 44 — Задача IV-B. Сломанный калькулятор 45 — Задача IV-C. Операции с валютой 46 — Задача IV-D. Двухтуровая олимпиада 47 — Задача IV-E. Черно-белые палиндромы 48 — 4 Оглавление Задача IV-F. Луч света в темном царстве 49 — Задача IV-G. Распаковка строки 51 — Задача IV-H. Дремучий лес 52 — Олимпиада V. Заочный тур 2004—2005 учебного года 53 158 Задача V-A. Автобусная экскурсия 53 158 Задача V-B. Сапер 54 158 Задача V-C.