Меньшиков Ф. - Олимпиадные задачи по программированию [2006, DjVu, RUS] + Code

Содержание

Предисловие 17

Структура книги 17

Как работать с книгой 18

Турбо Паскаль 19

Технический момент 20

Рекомендуемые настройки среды 21

Компакт-диск 21

Установка проверяющей системы 22

Работа с проверяющей системой 23

История создания книги 24

Благодарности 25

От издательства 25

Часть 1. Задачи 26

Тренировка 1 26

Задача 1 A. Простые числа 26

Задача 1 B. Выражение 26

Задача 1 C. Возрастающая подпоследовательность 27

Задача 1 D. Треугольник и точка 27

Задача 1 E. Степень 28

Задача 1 F. Покер 28

Тренировка 2 29

Задача 2 A. Простые числа (2) 29

Задача 2 B. Перестановки 29

Задача 2 C. Маршрут 30

Задача 2 D. Пересечение отрезков 30

Задача 2 E. Длинная сумма 31

Задача 2 F. Спираль 31

Тренировка 3 32

Задача 3 A. Разложение на простые множители 32

Задача 3 B. Перестановки (2) 32

Задача 3 C. Копилка 33

Задача 3 D. Открытка и конверт 33

Задача 3 E. Длинное произведение 34

Задача 3 F. Змейка 34

Тренировка 4 35

Задача 4 A. Совершенные числа 35

Задача 4 B. Разложение на слагаемые 35

Задача 4 C. Гангстеры 36

Задача 4 D. Площадь многоугольника 36

Задача 4 E. Деление длинного числа на короткое 37

Задача 4 F. Скобки 37

Тренировка 5 38

Задача 5 A. Дружественные числа 38

Задача 5 B. Скобки (2) 38

Задача 5 C. Маршрут (2) 39

Задача 5 D. Выпуклая оболочка 39

Задача 5 E. Системы счисления 40

Задача 5 F. День рождения 40

Тренировка 6 42

Задача 6 A. Закраска прямой 42

Задача 6 B. Суммы 42

Задача 6 C. Игра ?Даты? 43

Задача 6 D. Площадь прямоугольников 43

Задача 6 E. Lines 43

Задача 6 F. Покраска лабиринта 44

Тренировка 7 46

Задача 7 A. Упорядоченные дроби 46

Задача 7 B. Сообщение 46

Задача 7 C. Игра умножения 47

Задача 7 D. Прямая и квадраты 47

Задача 7 E. Lines (2) 47

Задача 7 F. Удаление клеток 48

Тренировка 8 50

Задача 8 A. Несоставляемое число 50

Задача 8 B. SMS 50

Задача 8 C. Дерево игры 52

Задача 8 D. Дуга на сфере 53

Задача 8 E. Путь коня 54

Задача 8 F. Грядки 54

Тренировка 9 56

Задача 9 A. Диалог компьютеров 56

Задача 9 B. Бросание кубика 57

Задача 9 C. Игра с монетами 58

Задача 9 D. Бассейн реки 58

Задача 9 E. Ближайшее число 60

Задача 9 F. Прямоугольное деление 61

Тренировка 10 62

Задача 10 A. Анти-QuickSort 62

Задача 10 B. Строки Фибоначчи 63

Задача 10 C. Игра в зачеркивание 64

Задача 10 D. Граница многоугольника 64

Задача 10 E. Путь спелеолога 65

Задача 10 F. Дырявая ткань 65

Тренировка 11 67

Задача 11 A. Последовательность 67

Задача 11 B. Провода 67

Задача 11 C. Палиндромы 68

Задача 11 D. Круговая площадь 68

Задача 11 E. Гомер Симпсон 69

Задача 11 F. Дробная арифметика 69

Тренировка 12 71

Задача 12 A. Последовательность (2) 71

Задача 12 B. Гирлянда 71

Задача 12 C. Головоломка умножения 72

Задача 12 D. Точки в многоугольнике 73

Задача 12 E. Водопровод 73

Задача 12 F. Химические реакции 74

Тренировка 13 77

Задача 13 A. Двойная решетка 77

Задача 13 B. Последовательность Фибоначчи 77

Задача 13 C. Скобки (3) 78

Задача 13 D. Центр тяжести 78

Задача 13 E. Сумма произведений 79

Задача 13 F. Статическая сложность 79

Тренировка 14 82

Задача 14 A. Марковский цикл 82

Задача 14 B. Д-44 83

Задача 14 C. Упаковка символов 83

Задача 14 D. Пирамиды 84

Задача 14 E. Поле для крикета 84

Задача 14 F. Электронная таблица 86

Тренировка 15 87

Задача 15 A. Игра с калькулятором 87

Задача 15 B. Площадь треугольника 87

Задача 15 C. Формирование поезда 88

Задача 15 D. Стена 89

Задача 15 E. Семечки 90

Задача 15 F. Умножение многочленов 91

Часть 2. Решения 92

Тренировка 1 92

Решение задачи 1 A. Простые числа 92

Решение задачи 1 B. Выражение 94

Вариант 1 94

Вариант 2 95

Решение задачи 1 C. Возрастающая подпоследовательность 97

Решение задачи 1 D. Треугольник и точка 99

Вариант 1 99

Вариант 2 100

Вариант 3 101

Вариант 4 103

Вариант 5 104

Решение задачи 1 E. Степень 105

Решение задачи 1 F. Покер 105

Вариант 1 105

Вариант 2 106

Вариант 3 106

Сравнение алгоритмов 106

Тренировка 2 107

Решение задачи 2 A. Простые числа (2) 107

Решение задачи 2 B. Перестановки 108

Вариант 1 108

Вариант 2 110

Вариант 3 110

Вариант 4 111

Решение задачи 2 C. Маршрут 112

Решение задачи 2 D. Пересечение отрезков 114

Вариант 1 114

Вариант 2 116

Решение задачи 2 E. Длинная сумма 119

Решение задачи 2 F. Спираль 121

Тренировка 3 123

Решение задачи 3 A. Разложение на простые множители 123

Решение задачи 3 B. Перестановки (2) 123

Вариант 1 124

Вариант 2 125

Вариант 3 126

Решение задачи 3 C. Копилка 126

Вариант 1 126

Вариант 2 127

Решение задачи 3 D. Открытка и конверт 128

Вариант 1 128

Вариант 2 130

Решение задачи 3 E. Длинное произведение 132

Вариант 1 132

Вариант 2 134

Вариант 3 135

Сравнение алгоритмов 135

Решение задачи 3 F. Змейка 135

Тренировка 4 137

Решение задачи 4 A. Совершенные числа 137

Решение задачи 4 B. Разложение на слагаемые 137

Решение задачи 4 C. Гангстеры 139

Вариант 1 139

Вариант 2 140

Решение задачи 4 D. Площадь многоугольника 141

Вариант 1 141

Вариант 2 142

Решение задачи 4 E. Деление длинного числа на короткое 143

Решение задачи 4 F. Скобки 144

Тренировка 5 146

Решение задачи 5 A. Дружественные числа 146

Решение задачи 5 B. Скобки (2) 147

Решение задачи 5 C. Маршрут (2) 149

Решение задачи 5 D. Выпуклая оболочка 152

Решение задачи 5 E. Системы счисления 155

Вариант 1 156

Вариант 2 157

Вариант 3 158

Сравнение алгоритмов 158

Решение задачи 5 F. День рождения 158

Тренировка 6 160

Решение задачи 6 A. Закраска прямой 160

Вариант 1 160

Вариант 2 161

Решение задачи 6 B. Суммы 161

Решение задачи 6 C. Игра ?Даты? 162

Решение задачи 6 D. Площадь прямоугольников 163

Решение задачи 6 E. Lines 166

Решение задачи 6 F. Покраска лабиринта 169

Тренировка 7 171

Решение задачи 7 A. Упорядоченные дроби 171

Вариант 1 171

Вариант 2 172

Решение задачи 7 B. Сообщение 173

Решение задачи 7 C. Игра умножения 173

Вариант 1 173

Вариант 2 176

Решение задачи 7 D. Прямая и квадраты 177

Решение задачи 7 E. Lines (2) 177

Решение задачи 7 F. Удаление клеток 181

Тренировка 8 185

Решение задачи 8 A. Несоставляемое число 185

Решение задачи 8 B. SMS 186

Решение задачи 8 C. Дерево игры 188

Вариант 1 188

Вариант 2 190

Решение задачи 8 D. Дуга на сфере 191

Вариант 1 191

Вариант 2 192

Вариант 3 193

Решение задачи 8 E. Путь коня 193

Решение задачи 8 F. Грядки 197

Тренировка 9 199

Решение задачи 9 A. Диалог компьютеров 199

Решение задачи 9 B. Бросание кубика 202

Решение задачи 9 C. Игра с монетами 204

Решение задачи 9 D. Бассейн реки 204

Решение задачи 9 E. Ближайшее число 207

Вариант 1 207

Вариант 2 209

Решение задачи 9 F. Прямоугольное деление 211

Вариант 1 211

Вариант 2 212

Вариант 3 213

Тренировка 10 217

Решение задачи 10 A. Анти-QuickSort 217

Решение задачи 10 B. Строки Фибоначчи 219

Решение задачи 10 C. Игра в зачеркивание 221

Решение задачи 10 D. Граница многоугольника 224

Решение задачи 10 E. Путь спелеолога 225

Решение задачи 10 F. Дырявая ткань 226

Тренировка 11 230

Решение задачи 11 A. Последовательность 230

Вариант 1 230

Вариант 2 231

Решение задачи 11 B. Провода 232

Решение задачи 11 C. Палиндромы 232

Решение задачи 11 D. Круговая площадь 234

Вариант 1 234

Вариант 2 235

Решение задачи 11 E. Гомер Симпсон 236

Решение задачи 11 F. Дробная арифметика 236

Тренировка 12 239

Решение задачи 12 A. Последовательность (2) 239

Вариант 1 239

Вариант 2 240

Решение задачи 12 B. Гирлянда 240

Вариант 1 241

Вариант 2 242

Вариант 3 242

Решение задачи 12 C. Головоломка умножения 243

Решение задачи 12 D. Точки в многоугольнике 244

Решение задачи 12 E. Водопровод 244

Вариант 1 244

Вариант 2 245

Решение задачи 12 F. Химические реакции 245

Тренировка 13 252

Решение задачи 13 A. Двойная решетка 252

Решение задачи 13 B. Последовательность Фибоначчи 253

Вариант 1 253

Вариант 2 255

Решение задачи 13 C. Скобки (3) 256

Вариант 1 256

Вариант 2 258

Решение задачи 13 D. Центр тяжести 261

Решение задачи 13 E. Сумма произведений 262

Решение задачи 13 F. Статическая сложность 262

Тренировка 14 266

Решение задачи 14 A. Марковский цикл 266

Вариант 1 266

Вариант 2 269

Решение задачи 14 B. Д-44 270

Решение задачи 14 C. Упаковка символов 272

Решение задачи 14 D. Пирамиды 274

Решение задачи 14 E. Поле для крикета 275

Решение задачи 14 F. Электронная таблица 275

Тренировка 15 277

Решение задачи 15 A. Игра с калькулятором 277

Вариант 1 277

Вариант 2 278

Решение задачи 15 B. Площадь треугольника 278

Вариант 1 278

Вариант 2 280

Сравнение алгоритмов 281

Решение задачи 15 C. Формирование поезда 281

Вариант 1 281

Вариант 2 287

Решение задачи 15 D. Стена 289

Решение задачи 15 E. Семечки 289

Решение задачи 15 F. Умножение многочленов 291

Приложение А. Характеристики встроенных типов

Турбо Паскаля 294

Целые типы 294

Вещественные типы 294

Приложение Б. Процедуры длинной арифметики 295

Дополнительная информация о задачах 300

Тренировка 1 300

Тренировка 2 301

Тренировка 3 301

Тренировка 4 302

Тренировка 5 303

Тренировка 6 303

Тренировка 7 304

Тренировка 8 304

Тренировка 9 305

Тренировка 10 306

Тренировка 11 306

Тренировка 12 307

Тренировка 13 308

Тренировка 14 308

Тренировка 15 309

Использованные сокращения 309

Авторы задач и решений 313

1. Система проверки

2. Тренировки

3. Дополнительные материалы:
На русском языке:
Материалы сайта "Олимпиады по информатике. Сайт в Санкт-Петербурге" (оригинал находится по адресу http://neerc.ifmo.ru/school/).

Материалы телекоммуникационного проекта "Задача в неделю" за 2002-2003 и 2003-2004 учебные годы. Рассылка проекта: job.education.zvn на http://subscribe.ru
Сайт проекта: http://zvn.uriit.ru/, http://attend.to/zvn.

Материалы сайта Вологодских олимпиад школьников по информатике (официальный сайт http://www.uni-vologda.ac.ru/olympiads/school/informatics/).

Материалы сайта Вологодской межвузовской олимпиады по программированию (официальный сайт http://www.uni-vologda.ac.ru/olympiads/interuni/).

Задачи Всероссийской индивидуальной студенческой олимпиады - 2003 г., г. Воронеж (официальный сайт олимпиады-2004: http://www.main.vsu.ru/~pmmmo/SiteRoss2004/).
На английском языке:
Материалы сайта Северо-восточного европейского полуфинала чемпионата мира по программированию ACM (официальный сайт http://neerc.ifmo.ru/).

Материалы сайта Центрального европейского полуфинала чемпионата мира по программированию ACM 1999 года (официальный сайт http://contest.felk.cvut.cz/99cerc/).

Задачи Юго-восточного европейского полуфинала чемпионата мира по программированию ACM 1999 года (официальный сайт http://www.acm.ro/).

Материалы сайта Юго-западного европейского полуфинала чемпионата мира по программированию ACM 1997 года (официальный сайт http://www.informatik.uni-ulm.de/acm/Regionals/1997/).

Материалы Центрального четвертьфинала NEERC (г. Рыбинск) (официальный сайт http://www.rgata.ru/p0.php).

Материалы сайта Дальневосточного четвертьфинала NEERC (официальный сайт http://imcs.dvgu.ru/acm/).

Материалы сайта Чемпионата Урала - 1999 (организатор - Уральский государственный университет, официальный сайт http://contest.ur.ru/ural99/).

Материалы сайта Чемпионата Урала - 2000 (официальный сайт http://contest.psu.ru/ на момент написания этих строк не работал больше года).

Материалы Северного четвертьфинала NEERC - 2002 (официальный сайт http://neerc.ifmo.ru/subregions/northern.html).

Задачи Московского четвертьфинала NEERC - 2003 (официальный сайт http://acm.msu.ru/2003/).

Материалы соревнования 22 сентября 2001 года, проходившего в университете Ватерлоо (Канада) (официальный сайт http://plg.uwaterloo.ca/~acm00/).

Задачи онлайн-соревнования "Return of the AZTECS" (оригинал http://online-judge.uva.es/contest/data/0069/problemset/).