Олимпиадные задачи по программированию

Меньшиков Ф.В.

Цель этой книги - познакомить читателей с некоторыми часто встречающимися типами задач, предлагаемых на олимпиадах по программированию. В разных источниках можно найти немало олимпиадных задач, но примеры решений публикуются далеко не всегда, а без них начинающему программисту-олимпийцу подготовиться к реальным соревнованиям бывает тяжело. В этой книге опубликован детальный разбор задач, взятых из ранее проводившихся олимпиад. Кроме примеров решения, автор обращает внимание читателей на особенности языков программирования, которые часто упускают из виду, но которые очень важны для успешного решения задачи.

К книге прилагается компакт-диск с набором тестовых данных и тестирующей системой, позволяющими проверить правильность решения каждой из 90 задач.

Издательство: Питер, 2006 г.

ISBN 5-469-00765-0

Количество страниц: 316.

Содержание книги «Олимпиадные задачи по программированию»:

17 Предисловие
- 17 Структура книги
- 18 Как работать с книгой
- 19 Турбо Паскаль
- 20 Технический момент
- 21 Рекомендуемые настройки среды
- 21 Компакт-диск
- 22 Установка проверяющей системы
- 23 Работа с проверяющей системой
- 24 История создания книги
- 25 Благодарности
- 25 От издательства
26 ЧАСТЬ I. ЗАДАЧИ
26 Тренировка 1
- 26 Задача 1A. Простые числа
- 26 Задача 1B. Выражение
- 27 Задача 1C. Возрастающая подпоследовательность
- 27 Задача 1D. Треугольник и точка
- 28 Задача 1E. Степень
- 28 Задача 1F. Покер
29 Тренировка 2
- 29 Задача 2А. Простые числа (2)
- 29 Задача 2B. Перестановки
- 30 Задача 2C. Маршрут
- 30 Задача 2D. Пересечение отрезков
- 31 Задача 2E. Длинная сумма
- 31 Задача 2F. Спираль
32 Тренировка 3
- 32 Задача 3А. Разложение на простые множители
- 32 Задача 3B. Перестановки (2)
- 33 Задача 3C. Копилка
- 33 Задача 3D. Открытка и конверт
- 34 Задача 3E. Длинное произведение
- 34 Задача 3F. Змейка
35 Тренировка 4
- 35 Задача 4А. Совершенные числа
- 35 Задача 4B. Разложение на слагаемые
- 36 Задача 4C. Гангстеры
- 36 Задача 4D. Площадь многоугольника
- 37 Задача 4E. Деление длинного числа на короткое
- 37 Задача 4F. Скобки
38 Тренировка 5
- 38 Задача 5А. Дружественные числа
- 38 Задача 5B. Скобки (2)
- 39 Задача 5C. Маршрут (2)
- 39 Задача 5D. Выпуклая оболочка
- 40 Задача 5E. Системы счисления
- 40 Задача 5F. День рождения
42 Тренировка 6
- 42 Задача 6А. Закраска прямой
- 42 Задача 6B. Суммы
- 43 Задача 6C. Игра «Даты»
- 43 Задача 6D. Площадь прямоугольников
- 43 Задача 6E. Lines
- 44 Задача 6F. Покраска лабиринта
46 Тренировка 7
- 46 Задача 7А. Упорядоченные дроби
- 46 Задача 7B. Сообщение
- 47 Задача 7C. Игра умножения
- 47 Задача 7D. Прямая и квадраты
- 47 Задача 7E. Lines (2)
- 48 Задача 7F. Удаление клеток
50 Тренировка 8
- 50 Задача 8А. Несоставляемое число
- 50 Задача 8B. SMS
- 52 Задача 8C. Дерево игры
- 53 Задача 8D. Дуга на сфере
- 54 Задача 8E. Путь коня
- 54 Задача 8F. Грядки
56 Тренировка 9
- 56 Задача 9А. Диалог компьютеров
- 57 Задача 9B. Бросание кубика
- 58 Задача 9C. Игра с монетами
- 58 Задача 9D. Бассейн реки
- 60 Задача 9E. Ближайшее число
- 61 Задача 9F. Прямоугольное деление
62 Тренировка 10
- 62 Задача 10А. Анти-QuickSort
- 63 Задача 10B. Строки Фибоначчи
- 64 Задача 10C. Игра в зачеркивание
- 64 Задача 10D. Граница многоугольника
- 65 Задача 10E. Путь спелеолога
- 65 Задача 10F. Дырявая ткань
67 Тренировка 11
- 67 Задача 11А. Последовательность
- 67 Задача 11B. Провода
- 68 Задача 11C. Палиндромы
- 68 Задача 11D. Круговая площадь
- 69 Задача 11E. Гомер Симпсон
- 69 Задача 11F. Дробная арифметика
71 Тренировка 12
- 71 Задача 12А. Последовательность(2)
- 71 Задача 12B. Гирлянда
- 72 Задача 12C. Головоломка умножения
- 73 Задача 12D. Точки в многоугольнике
- 73 Задача 12E. Водопровод
- 74 Задача 12F. Химические реакции
77 Тренировка 13
- 77 Задача 13А. Двойная решетка
- 77 Задача 13B. Последовательность Фибоначчи
- 78 Задача 13C. Скобки (3)
- 78 Задача 13D. Центр тяжести
- 79 Задача 13E. Сумма произведений
- 79 Задача 13F. Статическая сложность
82 Тренировка 14
- 82 Задача 14А. Марковский цикл
- 83 Задача 14B. Д-44
- 83 Задача 14C. Упаковка символов
- 84 Задача 14D. Пирамиды
- 84 Задача 14E. Поле для крикета
- 86 Задача 14F. Электронная таблица
87 Тренировка 15
- 87 Задача 15А. Игра с калькулятором
- 87 Задача 15B. Площадь треугольника
- 88 Задача 15C. Формирование поезда
- 89 Задача 15D. Стена
- 90 Задача 15E. Семечки
- 91 Задача 15F. Умножение многочленов
92 ЧАСТЬ 2. РЕШЕНИЯ
92 Тренировка 1
- 92 Решение задачи 1А. Простые числа
- 94 Решение задачи 1B. Выражение
  - 94 Вариант 1
  - 95 Вариант 2
- 97 Решение задачи 1C. Возрастающая подпоследовательность
- 99 Решение задачи 1D. Треугольник и точка
  - 99 Вариант 1
  - 100 Вариант 2
  - 101 Вариант 3
  - 103 Вариант 4
  - 104 Вариант 5
- 105 Решение задачи 1E. Степень
- 105 Решение задачи 1F. Покер
  - 105 Вариант 1
  - 106 Вариант 2
  - 106 Вариант 3
  - 106 Сравнение алгоритмов
107 Тренировка 2
- 107 Решение задачи 2А. Простые числа (2)
- 108 Решение задачи 2B. Перестановки
  - 108 Вариант 1
  - 110 Вариант 2
  - 110 Вариант 3
  - 111 Вариант 4
- 112 Решение задачи 2C. Маршрут
- 114 Решение задачи 2D. Пересечение отрезков
  - 114 Вариант 1
  - 116 Вариант 2
- 119 Решение задачи 2E. Длинная сумма
- 121 Решение задачи 2F. Спираль
123 Тренировка 3
- 123 Решение задачи 3А. Разложение на простые множители
- 123 Решение задачи 3B. Перестановки (2)
  - 124 Вариант 1
  - 125 Вариант 2
  - 126 Вариант 3
- 126 Решение задачи 3C. Копилка
  - 126 Вариант 1
  - 127 Вариант 2
- 128 Решение задачи 3D. Открытка и конверт
  - 128 Вариант 1
  - 130 Вариант 2
- 132 Решение задачи 3E. Длинное произведение
  - 132 Вариант 1
  - 134 Вариант 2
  - 135 Вариант 3
  - 135 Сравнение алгоритмов
- 135 Решение задачи 3F. Змейка
137 Тренировка 4
- 137 Решение задачи 4А. Совершенные числа
- 137 Решение задачи 4B. Разложение на слагаемые
- 139 Решение задачи 4C. Гангстеры
  - 139 Вариант 1
  - 140 Вариант 2
- 141 Решение задачи 4D. Площадь многоугольника
  - 141 Вариант 1
  - 142 Вариант 2
- 143 Решение задачи 4E. Деление длинного числа на короткое
- 144 Решение задачи 4F. Скобки
146 Тренировка 5
- 146 Решение задачи 5А. Дружественные числа
- 147 Решение задачи 5B. Скобки (2)
- 149 Решение задачи 5C. Маршрут (2)
- 152 Решение задачи 5D. Выпуклая оболочка
- 155 Решение задачи 5E. Системы счисления
  - 156 Вариант 1
  - 157 Вариант 2
  - 158 Вариант 3
  - 158 Сравнение алгоритмов
- 158 Решение задачи 5F. День рождения
160 Тренировка 6
- 160 Решение задачи 6А. Закраска прямой
  - 160 Вариант 1
  - 161 Вариант 2
- 161 Решение задачи 6B. Суммы
- 162 Решение задачи 6C. Игра «Даты»
- 163 Решение задачи 6D. Площадь прямоугольников
- 166 Решение задачи 6E. Lines
- 169 Решение задачи 6F. Покраска лабиринта
171 Тренировка 7
- 171 Решение задачи 7А. Упорядоченные дроби
  - 171 Вариант 1
  - 172 Вариант 2
- 173 Решение задачи 7B. Сообщение
- 173 Решение задачи 7C. Игра умножения
  - 173 Вариант 1
  - 176 Вариант 2
- 177 Решение задачи 7D. Прямая и квадраты
- 177 Решение задачи 7E. Lines (2)
- 181 Решение задачи 7F. Удаление клеток
185 Тренировка 8
- 185 Решение задачи 8А. Несоставляемое число
- 186 Решение задачи 8B. SMS
- 188 Решение задачи 8C. Дерево игры
  - 188 Вариант 1
  - 190 Вариант 2
- 191 Решение задачи 8D. Дуга на сфере
  - 191 Вариант 1
  - 192 Вариант 2
  - 193 Вариант 3
- 193 Решение задачи 8E. Путь коня
- 197 Решение задачи 8F. Грядки
199 Тренировка 9
- 199 Решение задачи 9А. Диалог компьютеров
- 202 Решение задачи 9B. Бросание кубика
- 204 Решение задачи 9C. Игра с монетами
- 204 Решение задачи 9D. Бассейн реки
- 207 Решение задачи 9E. Ближайшее число
  - 207 Вариант 1
  - 209 Вариант 2
- 211 Решение задачи 9F. Прямоугольное деление
  - 211 Вариант 1
  - 212 Вариант 2
  - 213 Вариант 3
217 Тренировка 10
- 217 Решение задачи 10А. Анти-QuickSort
- 219 Решение задачи 10B. Строки Фибоначчи
- 221 Решение задачи 10C. Игра в зачеркивание
- 224 Решение задачи 10D. Граница многоугольника
- 225 Решение задачи 10E. Путь спелеолога
- 226 Решение задачи 10F. Дырявая ткань
230 Тренировка 11
- 230 Решение задачи 11А. Последовательность
  - 230 Вариант 1
  - 231 Вариант 2
- 232 Решение задачи 11B. Провода
- 232 Решение задачи 11C. Палиндромы
- 234 Решение задачи 11D. Круговая площадь
  - 234 Вариант 1
  - 235 Вариант 2
- 236 Решение задачи 11E. Гомер Симпсон
- 236 Решение задачи 11F. Дробная арифметика
239 Тренировка 12
- 239 Решение задачи 12А. Последовательность (2)
  - 239 Вариант 1
  - 240 Вариант 2
- 240 Решение задачи 12B. Гирлянда
  - 241 Вариант 1
  - 242 Вариант 2
  - 242 Вариант 3
- 243 Решение задачи 12C. Головоломка умножения
- 244 Решение задачи 12D. Точки в многоугольнике
- 244 Решение задачи 12E. Водопровод
  - 244 Вариант 1
  - 245 Вариант 2
- 245 Решение задачи 12F. Химические реакции
252 Тренировка 13
- 252 Решение задачи 13А. Двойная решетка
- 253 Решение задачи 13B. Последовательность Фибоначчи
  - 253 Вариант 1
  - 255 Вариант 2
- 256 Решение задачи 13C. Скобки (3)
  - 256 Вариант 1
  - 258 Вариант 2
- 261 Решение задачи 13D. Центр тяжести
- 262 Решение задачи 13E. Сумма произведений
- 262 Решение задачи 13F. Статическая сложность
266 Тренировка 14
- 266 Решение задачи 14А. Марковский цикл
  - 266 Вариант 1
  - 269 Вариант 2
- 270 Решение задачи 14B. Д-44
- 272 Решение задачи 14C. Упаковка символов
- 274 Решение задачи 14D. Пирамиды
- 275 Решение задачи 14E. Поле для крикета
- 275 Решение задачи 14F. Электронная таблица
277 Тренировка 15
- 277 Решение задачи 15А. Игра с калькулятором
  - 277 Вариант 1
  - 278 Вариант 2
- 278 Решение задачи 15B. Площадь треугольника
  - 278 Вариант 1
  - 280 Вариант 2
  - 281 Сравнение алгоритмов
- 281 Решение задачи 15C. Формирование поезда
  - 281 Вариант 1
  - 287 Вариант 2
- 289 Решение задачи 15D. Стена
- 289 Решение задачи 15E. Семечки
- 291 Решение задачи 15F. Умножение многочленов
294 Приложение А. Характеристики встроенных типов Турбо Паскаля
- 294 Целые типы
- 294 Вещественные типы
295 Приложение Б. Процедуры длинной арифметики
300 Дополнительная информация о задачах
- 300 Тренировка 1
- 301 Тренировка 2
- 301 Тренировка 3
- 302 Тренировка 4
- 303 Тренировка 5
- 303 Тренировка 6
- 304 Тренировка 7
- 304 Тренировка 8
- 305 Тренировка 9
- 306 Тренировка 10
- 306 Тренировка 11
- 307 Тренировка 12
- 308 Тренировка 13
- 308 Тренировка 14
- 309 Тренировка 15
- 309 Использованные сокращения
- 313 Авторы задач и решений