#- > обозначает территорию грядки. Символ . соответствует незанятой территории. Других символов в исходном файле нет. В выходной текстовый файл вывести количество грядок на садовом участке.

Пример файла исходных данных: 5 10

##......##

.#..#...#. .###-##

........#.

Выходной файл для данного примера имеет вид:

214. Спуск с горы.

3 8 8 10 2 7 4 4 4 5 2 6 5

На рисунке показан числовой треугольник. Написать алгоритм-программу, которая находит максимальную сумму чисел в вершинах треугольника при движении сверху вниз по ребрам треугольника, т.е. из каждой вершины можно двигаться вниз налево или вниз направо. Например, для данного треугольника маршрут движения по узлам 7, 8, 1, 7, 2 дает сумму 25. Результаты расчетов сохранить в текстовом файле.

Исходные данные представлены в текстовом файле, имеющем следующую структуру. Первая строка: л - число уровней в треугольнике. Вторая и следующие строки содержат описание треугольника.

Пример файла исходных данных:

8 10 2 7 4 4

4 5 2 6 5

Пример файла выходных данных:

7 3 8 7 5

215. Перестановка корзин. Даны 2л корзин с шарами и В, расположенные в ряд, как на рисунке < 5).

\A\B\B\A\ \ \A\B\A\B\ Два места под корзины пустые. Другие п - 1 корзина содержат шары А и п - 1 корзина - шары В.

Составьте алгоритм-программу, которая бы переставляла корзины с шарами А с одной стороны, а корзины с шарами В с другой стороны. Правила перемещения корзин: разрешается переставлять на пустые места любые две смежные (пара) непустые корзины, сохраняя их первоначальный порядок.

Исходные данные представлены: в текстовом файле со следующей структурой. Первая строка: 2л - число корзин с пустыми местами. Вторая строка: \А 2? \ В \А \А 5 \А \ В\ - исходное расположение корзин. Расчетные данные сохранить в текстовом файле со следующей структурой. Каждая строка - состояние корзин после каждой перестановки.

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

музея показан ниже на рисунке.

11 6 11 б 3 10

7 9 6 13 5 7

1 10 12 7 13 13

13 11 10 8 10 14 13

Цифровая карта Карта перекрытий

Площадь музея состоит из клеток: л рядов и т столбцов. В каждой клетке такой матрицы (цифровая карта) проставляется число, в котором кодируется наличие стен уданной клетки. Значение числа в каждой клетке является суммой чисел: 1 (клетка имеет стену на западе), 2 (клетка имеет стену на севере), 4 (клетка имеет стену на востоке), 8 (клетка имеет стену на юге). Например, еслив клетке стоит число 11 (11 = 8 + 2+1), то клетка имеет стену с южной

стороны, с северной и с западной.

Исходные данные представляются в текстовом файле со следующей структурой. Первая строка: п, т - размерность сетки.

Вторая строка, третья и следующие строки содержат описание матрицы цифровой карты по строкам. Расчетные данные сохранить в текстовом файле со следующей структурой. Число в первой строке - количество комнат в музее. Вторая строка - площадь каждой комнаты.

Пример файла исходных данных:

4 7

11 6 11 6 3 10 6

7 9 6 13 5 7 5

1 10 12 7 13 13 5

13 11 10 8 10 14 13

Пример файла выходных данных:

9 6 3 2 8.

217. Переворот бокалов. На столе стоят в ряд пронумерованных слева направо от 1 до N. Первоначально все бокалы стоят дном вниз. Над бокалами можно выполнять операцию переворот . За один переворот ровно М(1 < Л/< N] любых бокалов переворачиваются что те бокалы, которые стояли дном вниз, оказываются перевернутыми вверх дном, а остальные из Мбокалов ставятся вниз дном.

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

Исходные данные N, Мзадаются в текстовом файле. Результаты последовательных переворотов сохранить в текстовом

218. Течение воды. Все улицы в некотором городе имеют направление с севера на юг улиц) или с запада на восток (т улиц), как на рисунке. Для каждого перекрестка улиц задается высота его над уровнем моря: /.j], i = \,М.j = \,N - матрица высот над уровнем моря. Требуется написать алгоритм-программу, который находит путь от перекрестка А до перекрестка В или в обратном направлении. Путь должен проходить по таким улицам, которые не ведут к возвышенностям (уровень при движении не должен возрастать).

Исходные данные представлены в текстовом файле со следующей структурой. Первая строка: М, N - размерность матрицы и

улиц. Вторая строк а: А = (ia,ja),B = (ib,jb\ - координаты двух перекрестков. Третья и следующие строки определяют значения элементов матрицы: высот H{i,j],i = \,M,j- \,N. Результаты расчетов сохранить в выходном текстовом файле со следующей структурой. Каждая строка - координаты и высоты перекрестков, через которые пролегает маршрут.

219. Бомба. Требуется составить алгоритм-программу для определения наименьшей окружности (центр и минимальный радиус), охватывающей не менее к из я заданных точек на плоскости. Исходные точки на плоскости (х{,у\), (х2,у2),..., (х„,уп) задаются в текстовом файле. Резулытаты: расчетов (координаты: центра окружности, радиус ее и точки (*,-, у,), попадающие в окружность) сохранить в текстовом файле. Решите эту же задачу, но искомая окружность должна включать все заданные точки

220. Ханойская башня. Задача о ханойской башне проиллюстрирована на следующем рисунке:

А

и

Имеются три колышка Д, В, С. На колышек^ нанизано п дисков радиуса 1, 2,..., и (каждый с отверстием в середине) таким образом, что диск радиуса сверху. Задача состоит в том, чтобы переместить все диски на колышек образом, чтобы диск радиуса был опять сверху. За один раз разрешается перемещать только один диск с любого колышка на любой другой (можно пользоваться кольппком В). При этом должно вьтолня-ться следующее условие: на каждом колышке ни в какой момент никакой диск не может находиться выше диска с меньшим номером. Составить рекурсивную алгоритм-программу требуемых

перемещений дисков. Результаты расчетов: состояние каждого

колышка на каждом шаге перекладывания дисков сохранять в текстовом файле.

221. Числа. Дана последовательность п различных между собой целых чисел а{, а2,..., а„. Трансформацией называется следующая последовательность действий: некоторые из чисел увеличивают-

В

С

ся на если в последовательности оказываются два одинаковьгх числа, то одно из них исключается из последовательности. Выполним данную трансформацию к раз, с целью достигнуть минимального количества чисел в последовательности Составить которая вычисляетр - количество чисел, оставшихся в последовательности. Исходные данные п, кп последовательность а„ задаются в текстовом файле. Найденное число р сохранить в текстовом файле. Пример файла исходных данных:

7 1 15 8 3.

Пример файла выходных данных:

222. Знакомства. Имеется п человек, где 1 1000. Каждому из них приписано некоторое число, которое определяет количество человек, с которыми ему предписано познакомиться. При этом знакомство взаимно, т.е. если человек с номером знакомится с человеком с то и человек с знакомится с че-

ловеком с номером Составить алгоритм-программу, задача которой состоит в следующем. Необходимо организовать знакомства, чтобы после их реализации участники могли быть разбиты на 2 команды таким образом, что в команде находятся

участники, знакомые друг с другом (каждый знает а во

второй - только незнакомые (никто никого не знает). При этом

численность первой команды должна быть максимальна. В случае невозможности реализации знакомств в выходной файл записать ответ NO .

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

Формат файла выходных данных. В первой строке выходного файла находится численность первой команды или В слу-

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

номера людей, которым необходимо познакомиться. Приведем

примеры расчетов для конкретных исходных данных.

Пример входного файла:

Пример выходного файла:

1

а

223. Обмен. Каждому из п жителей одного городка шериф присвоил личный номер - целое число от 1 до п и сообщил его, а затем поручил секретарше разослать по почте жетоны с личными номерами. Но она разложила их по конвертам случайным образом. Для восстановления когда у жителя находится жетон с его номером, необходимо организовать обмен жетонами. Каждый житель может обменять в один день жетон, который находится у него, на другой только с одним другим жителем. В один день обмениваться жетонами могут любое количество пар жителей. Составить алгоритм-программу поиска минимального количества дней т, необходимых для того, чтобы все жители получили свои жетоны.

Формат файла входных данных. Первая строка содержит целое число п, \<п< 1000, равное количеству жителей городка. Следующие п строк содержат по одному числу - номеру жетона, т.е. в (/+ 1)-й строке, соответствующей /-му жителю, находится номер того жетона, который он получил по почте. Выходной файл данных содержит одну строку с найденным числом дней т.

224. Кокосы. В газетах 9 октября 1926 года сообщалось о кораблекрушении судна в Индийском океане. Пять человек и одна обезьянка спаслись на необитаемом острове. В первый день пребывания на острове они собирали кокосы. Среди ночи один из них проснулся и решил разделить кокосы. Он разделил кокосы на пять равных частей. Однако остался один кокос, который он отдал обезьянке. Свою часть он взял с собой и пошел досыпать. Далее второй, третий, четвертый и пятый поступили аналогичным образом и каждый раз оставался один кокос, который они с удовольствием отдавали обезьянке. Напрашивается вопрос: сколько было кокосов? Однако мы решим несколько другую задачу (обратную). Составить алгоритм-программу поиска максимально возможного числа людей и одной обезьянки, которые могут проделать рассмотренную ночную операцию, если изначально известно количество собранных кокосов?

Исходные данные задаются в текстовом файле, который содержит последовательность целых чисел, каждое из которых является числом собранных кокосов. Последовательность чи-

заканчивается числом 1 - признак конца данных. Результаты расчетов числа людей и одной обезьянки для каждого случая исходных данных сохранить в выходном текстовом файле. Приведем примеры расчетов для конкретных исходных данных.

225. Быстрый Фил. Фил работает в последнюю смену. После работы ровно в 2:00 утра Фил уезжает домой с автомобильной стоянки. Его маршрут пролегает по дороге, на которой установлены один или несколько светофоров. Фил всегда удивлялся, что, выбирая определенную скорость движения по маршруту и не изменяя ее, он мог иногда доехать к дому без задержки на светофорах, т.е. все светофоры он проезжал на зеленый свет. Скорость движения в городской черте не должна превосходить 60 миль/ч. Однако Фил не любил и тихо ездить. Минимальная скорость его движения 30 миль/ч. Составьте алгоритм-программу, которая находит все целочисленные скорости (в с которыми Фил может

двигаться домой без остановки на светофорах, начало движения с автомобильной стояки ровно в 2:00 утра. В этот момент времени

все светофоры сбрасываются в зеленый цвет.

Исходные данные задаются в текстовом файле, в котором приводится набор данных для описания режимов работы светофоров. Последнее число в файле (-1), является признаком конца данных в файле. Первое число п каждого набора определяет количество светофоров на маршруте. Далее следуют п наборов чисел: Length-GreenYellowRed {LGYI для каждого светофора, где L - положительное действительное число, указывающее место расположения светофора от начала маршрута Фила; G, Y, R - интервал продолжительности времени в секундах непрерывного цвета светофора: зеленого, желтого и красного. Результаты расчетов допустимых целочисленных скоростей движения Фила сохранить в выходном текстовом файле:

10.7 10 2 75 12.5 12 5 57 17.93 15 4 67

- 1

226. Парламент. Парламент состоит из N делегатов. Делегаты должны разделиться на группы (фракции), количество депутатов в каждой группе отличается от количества депутатов в любой другой группе. Каждый день каждая фракция посылает одного представителя в президиум. Парламент начинает работу в том случае, когда состав президиума отличен от составов президиумов предыдущих дней.

Составьте алгоритм-программу, которая бы определяла оптимальное число фракций и количество делегатов в каждой из них так, чтобы парламент мог работать как можно дольше. Число делегатов задается в исходном текстовом файле. Рассчитанные значения количества делегатов в каждой фракции, сортированные по возрастанию, сохранить в выходном текстовом файле. Приведем примеры оптимальных расчетов для N= i и N = 31.

227. Кот и Лиса. Дан ориентированный граф (X, U, Ф), вершины которого являются позициями в следующей игре. Участвуют два игрока - Кот и Лиса. Они двигают фишку из позиции в позицию по дугам графа. Множество позиций разделено на два подмножества Х= К и Л. В позициях /Iход делает Лиса, а в позициях К- Кот. Если игра находится в позиции х X, владелец этой позиции выбирает произвольную выходящую дугу (х, у) е Uи двигает фишку из х в у. Игра начинается в некоторой позиции. Лиса выигрывает, если фишка оказалась в фиксированной вершине Z 6 X. Если за любое количество ходов фишка не попадает в эту позицию z 6 X, то выигрывает Кот.

Составить которая определяет все вы-

игрышные стартовые позиции для Лисы при оптимальной стратегии обеих сторон. Считаем, что Х= {1, 2,..., п), \<п< 1000.

Исходные данные представлены в текстовом файле, имеющем следующую структуру.

Первая строка: п, т, z, где п - число вершин, т - число дуг, Z- заключительная позиция.

Со второй строки записаны: ЬъЬг .., Ьп иху}\ х^ ... хтУп v где Ь, -~ 1 если вершина i принадлежит Лисе; = 0, если вершина i принадлежит Коту; - список дуг графа, - начальная вершина, yt - конечная вершина соответствующей дуги. Все параметры - целые числа, разделенные пробелами.

Пример входного файла:

7 12 7

0 1 0 0 0 1 0 12 14 13

2 4 2 5

3 1 3 6 3 7

4 3 4 6

Результат представить в текстовом в котором записать п

целых чисел С], с2 ., с„, где = 1, если позиция / выигрышная для

Лисы; иначе с, = 0.

Для примера результаты расчетов представляются строкой: 0 10 0 111

228. Ящик с молоком. Ящик имеет п х п ячеек для бутылок с молоком. Мистер Смит для каждого столбца и каждой строки заготовил отдельный листок бумаги, где записал наличие или отсутствие в

ячейке бутылки молока: 1 - ячейка занята молоком, 0 - ячейка

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

Испорченные цифры 1 и 0 были заменены цифрой 2. Составить

которая по таким записям восстанавливает исходное расположение бутылок с молоком, т.е. определить, какие записи относятся к строкам, а какие - к столбцам. Исходные испорченные записи по строкам и столбцам задаются в текстовом

файле. Результаты сохранить в текстовом файле.

Пример.

229. Длина объединения. Текстовый файл содержит целые числа: й), b\, а2, hi,..., ап, Ьп. Эта последовательность определяет на оси ОХп отрезков. Составить алгоритм-программу, которая определяет длину объединения всех отрезков. Результаты расчетов сохранить в текстовом файле. Исходные данные представлены в текстовом файле со следующей структурой. Первая строка: п - количество отрезков. Вторая строка, третья строка и т.д: а,-, Ь, - параметры соответствующего отрезка. Результаты расчетов сохранить в текстовом

Пример файла исходных данных:

з

-1 1

О 1.

Пример файла вьжодньгх данных:

230. Площадь объединения. Условие данной задачи - это условие предыдущей задачи, где вместо отрезков на прямой рассматриваются прямоугольники на плоскости, стороны которых параллельны осям координат. Составить алгоритм-программу определения площади объединения таких прямоугольников.

231. Прямоуголъныеобласти. Условие данной задачи - это условие предыдущей задачи. Однако требуется составить алго-

определения количества областей, на которые границы прямоугольников разбивают плоскость.