Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям

Содержание книги «Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям»:

• 5 Введение
• 11 Глава 1. Начало работы
  • 11 1.1. Начало работы с автоматической тестирующей системой (robot judge)
    • 12 1.1.1. Автоматический судья Programming Challenges
    • 13 1.1.2 Автоматический судья Universidad de Valladolid
    • 14 1.1.3. Ответы тестирующих систем (судей)
  • 15 1.2. Выбор оружия
    • 16 1.2.1. Языки программирования
    • 18 1.2.2. Чтение наших программ
    • 19 1.2.3. Стандартный ввод/вывод
  • 21 1.3. Советы по программированию
  • 24 1.4. Элементарные типы данных
  • 27 1.5. О задачах
  • 27 1.6. Задачи
    • 27 1.6.1. Задача 3n+1
    • 28 1.6.2. Сапер
    • 30 1.6.3. Путешествие
    • 31 1.6.4. LCD-дисплей
    • 33 1.6.5. Графический редактор
    • 35 1.6.6. Интерпретатор
    • 36 1.6.7. Проверка на шах
    • 39 1.6.8. Австралийское голосование
  • 40 1.7. Подсказки
  • 40 1.8. Замечания
• 42 Глава 2. Структуры данных
  • 42 2.1. Элементарные структуры данных
    • 43 2.1.1. Стеки (Stacks)
    • 43 2.1.2. Очереди (Queues)
    • 45 2.1.3. Словари (Dictionaries)
    • 47 2.1.4. Очереди по приоритету (Priority queues)
    • 48 2.1.5. Множества (Sets)
  • 49 2.2. Объектные библиотеки
    • 49 2.2.1. Стандартная библиотека шаблонов C++ (C++ Standard Template Library)
    • 50 2.2.2. Пакет java.util для Java
  • 51 2.3. Пример разработки программы: сборы на войну
  • 53 2.4. Что касается колоды
  • 54 2.5. Строковый ввод/вывод
  • 56 2.6. Победа на войне
  • 57 2.7. Тестирование и отладка
  • 59 2.8. Задачи
    • 59 2.8.1. Jolly Jumpers
    • 60 2.8.2. Руки в покере
    • 62 2.8.3. Харталы (Hartals)
    • 63 2.8.4. Дешифратор
    • 64 2.8.5. Расположить по порядку
    • 67 2.8.6. Числа Эрдеша
    • 68 2.8.7. Табло соревнований
    • 70 2.8.8. Yahtzee
  • 72 2.9. Подсказки
  • 72 2.10. Замечания
• 73 Глава 3. Строки
  • 73 3.1. Коды символов
  • 75 3.2. Представление строк
  • 76 3.3. Пример разработки программы: корпоративные переименования
  • 79 3.4. Поиск шаблонов
  • 80 3.5. Управление строками
  • 81 3.6. Завершение программы
  • 82 3.7. Функции библиотеки для работы со строками
  • 84 3.8. Задачи
    • 84 3.8.1. WERTYU
    • 85 3.8.2. Где Waldorf?
    • 86 3.8.3. Обычная перестановка
    • 87 3.8.4. Дешифратор II
    • 88 3.8.5. Автоматизированное судейство
    • 90 3.8.6. Осколки файлов
    • 92 3.8.7. Дублеты
    • 93 3.8.8. Fmt
  • 94 3.9. Подсказки
  • 95 3.10. Замечания
• 96 Глава 4. Сортировка
  • 96 4.1. Приложения сортировки
  • 98 4.2. Алгоритмы сортировки
  • 100 4.3. Пример разработки программы: рейтинг ухажеров
  • 102 4.4. Функции библиотеки сортировки
  • 104 4.5. Рейтинг ухажеров
  • 106 4.6. Задачи
    • 106 4.6.1. Семья Вито
    • 107 4.6.2. Стопки оладий
    • 108 4.6.3. Мост
    • 110 4.6.4. Подремать подольше
    • 112 4.6.5. Задача сапожника
    • 113 4.6.6. CDVII
    • 114 4.6.7. Сортировка Шелла
    • 116 4.6.8. Футбол
  • 118 4.7. Подсказки
  • 119 4.8. Замечания
• 120 Глава 5. Арифметика и алгебра
  • 120 5.1. Машинная арифметика
  • 121 5.2. Высокоточные целые числа
  • 123 5.3. Высокоточная арифметика
  • 128 5.4. Системы счисления и соответствующие переходы
  • 130 5.5. Вещественные числа
    • 131 5.5.1. Работа с вещественными числами
    • 132 5.5.2. Простые дроби
    • 133 5.5.3. Десятичные дроби
  • 134 5.6. Алгебра
    • 134 5.6.1. Работа с полиномами
    • 135 5.6.2. Нахождение корней
  • 136 5.7. Логарифмы
  • 137 5.8. Математические библиотеки
  • 138 5.9. Задачи
    • 138 5.9.1. Начала арифметики
    • 139 5.9.2. Изменение порядка и сложение
    • 140 5.9.3. Дилемма археолога
    • 141 5.9.4. Единицы
    • 142 5.9.5. Игра в умножения
    • 143 5.9.6 Коэффициенты полинома
    • 144 5.9.7. Числовая система Штерна-Броко (Stern-Brocot)
    • 146 5.9.8. Попарно суммируемые числа
  • 147 5.10. Подсказки
  • 147 5.11. Замечания
• 148 Глава 6. Комбинаторика
  • 148 6.1. Базовые методики счета
  • 150 6.2. Рекуррентные соотношения
  • 151 6.3. Биномиальные коэффициенты
  • 153 6.4. Другие счетные последовательности
  • 156 6.5. Рекурсия и индукция
  • 157 6.6. Задачи
    • 157 6.6.1. Сколько чисел?
    • 158 6.6.2. Сколько частей земли?
    • 159 6.6.3. Счет
    • 160 6.6.4. Выражения
    • 162 6.6.5. Нумерация полного дерева
    • 163 6.6.6. Монах-математик
    • 164 6.6.7. Самоописывающая последовательность
    • 165 6.6.8. Шаги
  • 166 6.7. Подсказки
  • 166 6.8. Замечания
• 167 Глава 7. Теория чисел
  • 167 7.1. Простые числа
    • 168 7.1.1. Поиск простых чисел
    • 169 7.1.2. Подсчет простых чисел
  • 170 7.2. Делимость
    • 171 7.2.1. Наибольший общий делитель
    • 173 7.2.2. Наименьшее общее кратное
  • 173 7.3. Арифметика остатков
  • 175 7.4. Сравнимости
    • 176 7.4.1. Операции со сравнимостями
    • 176 7.4.2. Решение линейных сравнимостей
    • 177 7.4.3. Диофантовы уравнения
  • 178 7.5. Библиотеки по теории чисел
  • 178 7.6. Задачи
    • 178 7.6.1. Света, больше света
    • 179 7.6.2. Числа Кармайкла
    • 180 7.6.3. Задача Евклида
    • 181 7.6.4. Делители факториалов
    • 182 7.6.5. Сумма четырех простых чисел
    • 183 7.6.6. Числа Смита
    • 184 7.6.7. Шарики
    • 185 7.6.8. Переупаковка
  • 187 7.7. Подсказки
  • 187 7.8. Замечания
• 188 Глава 8. Поиск с возвратом
  • 188 8.1. Поиск с возвратом
  • 190 8.2. Построение всех подмножеств
  • 192 8.3. Построение всех перестановок
  • 193 8.4. Пример разработки программы: задача восьми ферзей
  • 195 8.5. Поиск с отсечением вариантов
  • 198 8.6. Задачи
    • 198 8.6.1. Слоны
    • 199 8.6.2. Задача про пятнашки
    • 201 8.6.3. Шеренга
    • 202 8.6.4. Станции техобслуживания
    • 203 8.6.5. Перетягивание каната
    • 205 8.6.6. Эдемский сад
    • 207 8.6.7. Color hash
    • 209 8.6.8. Больший квадрат
  • 211 8.7. Подсказки
  • 212 8.8. Замечания
• 213 Глава 9. Обходы графов
  • 213 9.1. Особенности графов
  • 216 9.2. Структуры данных для графов
  • 219 9.3. Обход графа: в ширину
    • 219 9.3.1. Поиск в ширину
    • 221 9.3.2. Использование обхода
    • 221 9.3.3. Нахождение путей
  • 223 9.4. Обход графа: в глубину
    • 224 9.4.1. Обнаружение циклов
    • 225 9.4.2. Связные компоненты
  • 226 9.5. Топологическая сортировка
  • 228 9.6. Задачи
    • 228 9.6.1. Раскраска двумя цветами
    • 229 9.6.2. Колеса
    • 231 9.6.3. Экскурсовод
    • 233 9.6.4. Лабиринт из косых
    • 234 9.6.5. Лесенки ступенек редактирования
    • 235 9.6.6. Башни из кубиков
    • 237 9.6.7. От заката до рассвета
    • 238 9.6.8. И снова ханойские башни!
  • 240 9.7. Подсказки
• 241 Глава 10. Графовые алгоритмы
  • 241 10.1. Теория графов
    • 241 10.1.1. Свойства степеней
    • 242 10.1.2. Связность
    • 243 10.1.3. Циклы в графах
    • 244 10.1.4. Планарные графы
  • 245 10.2. Минимальные остовные деревья
  • 248 10.3. Кратчайшие пути
    • 248 10.3.1. Алгоритм Дейкстры (Dijkstra)
    • 250 10.3.2. Кратчайшие пути между всеми парами вершин
  • 253 10.4. Потоки в сети и паросочетания в двудольных графах
  • 256 10.5. Задачи
    • 256 10.5.1. Веснушки
    • 257 10.5.2. Ожерелье
    • 259 10.5.3. Пожарное депо
    • 260 10.5.4. Железные дороги
    • 262 10.5.5. Война
    • 264 10.5.6. Экскурсовод
    • 266 10.5.7. Большой обед
    • 267 10.5.8. Задача про постановщика задач
  • 269 10.6. Подсказки
• 270 Глава 11. Динамическое программирование
  • 270 11.1. Не нужно жадничать
  • 271 11.2. Стоимость редактирования
  • 275 11.3. Восстановление пути
  • 277 11.4. Варианты стоимости редактирования
  • 280 11.5. Пример разработки программы: оптимизация лифта
  • 284 11.6. Задачи
    • 284 11.6.1. Умнее ли больший?
    • 285 11.6.2. Различные подпоследовательности
    • 286 11.6.3. Веса и меры
    • 287 11.6.4 Однонаправленная задача коммивояжера
    • 289 11.6.5. Распил брусьев
    • 290 11.6.6. Заполнение парома
    • 292 11.6.7. Палочки для еды
    • 293 11.6.8. Приключения в дороге: часть IV
  • 294 11.7. Подсказки
  • 294 11.8. Замечания
• 295 Глава 12. Сетки
  • 295 12.1. Прямолинейные сетки
    • 296 12.1.1. Обход
    • 298 12.1.2. Двойственные графы и представления
  • 298 12.2. Треугольные и гексагональные сетки
    • 298 12.2.1. Треугольные решетки
    • 300 12.2.2. Гексагональные решетки
  • 303 12.3. Пример разработки программы: Вес тарелки
  • 305 12.4. Упаковка кругов
  • 306 12.5. Широта и долгота
  • 307 12.6. Задачи
    • 307 12.6.1. Муравей на доске
    • 308 12.6.2. Моноцикл
    • 311 12.6.3. Звезда
    • 312 12.6.4. Пчела Майя
    • 313 12.6.5. Ограбление
    • 315 12.6.6.(2/3/4)-D Квад/Прям/Куб...?
    • 317 12.6.7. Дермубский треугольник
    • 318 12.6.8. Авиалинии
  • 320 12.7. Подсказки
• 321 Глава 13. Геометрия
  • 321 13.1. Прямые
  • 325 13.2. Треугольники и тригонометрия
    • 325 13.2.1. Прямоугольные треугольники и теорема Пифагора
    • 325 13.2.2. Тригонометрические функции
    • 327 13.2.3. Решение треугольников
  • 328 13.3. Окружности
  • 331 13.4. Пример разработки программы: быстрее пули
  • 334 13.5. Библиотеки тригонометрических функций
  • 335 13.6. Задачи
    • 335 13.6.1. Суслик и собака
    • 336 13.6.2. Проблема с канатами в Канатово
    • 337 13.6.3. Рыцари Круглого стола
    • 338 13.6.4. Шоколадное печенье
    • 339 13.6.5. Именинный пирог
    • 340 13.6.6. Самая большая/маленькая коробка
    • 341 13.6.7. Это интегрирование?
    • 342 13.6.8. Насколько она большая?
  • 344 13.7. Подсказки
• 345 Глава 14. Вычислительная геометрия
  • 345 14.1. Отрезки и пересечения
  • 347 14.2. Многоугольники и вычисления углов
  • 348 14.3. Выпуклые оболочки
  • 352 14.4. Триангуляция: алгоритмы и смежные задачи
    • 352 14.4.1. Алгоритм Ван Гога
    • 354 14.4.2 Подсчет площади
    • 355 14.4.3. Относительное положение точки
  • 357 14.5. Алгоритмы для сеток
    • 358 14.5.1. Запросы на значение области
    • 358 14.5.2. Решетчатые многоугольники и теорема Пика
  • 360 14.6. Геометрические библиотеки
  • 360 14.7. Задачи
    • 360 14.7.1. Пасем первокурсников
    • 361 14.7.2. Задача о ближайших точках
    • 362 14.7.3. Резня бензопилой
    • 364 14.7.4. Теплее - холоднее
    • 364 14.7.5. Useless Tile Packers
    • 366 14.7.6. Радиолокация
    • 367 14.7.7. Деревья моего острова
    • 369 14.7.8. Вкусное молоко
  • 371 14.8. Подсказки
• 372 Приложение A
  • 372 А.1. ACM International Collegiate Programming Contest
    • 373 A.1.1. Подготовка
    • 375 A.1.2. Стратегия и тактика
  • 377 А.2. International Olympiad in Informatics (Международная олимпиада по информатике)
    • 377 A.2.1. Участие
    • 378 A.2.2. Формат
    • 379 A.2.3. Подготовка
  • 380 А.3. Topcoder.com
  • 381 A.4. Аспирантура
  • 382 А.5. Благодарности за задачи
• 387 Послесловие В. М. Кирюхина
• 391 Список рекомендуемой литературы
• 394 Предметный указатель