Каталог по источникам

Задачи

Страница: << 40 41 42 43 44 45 46 >> [Всего задач: 272]

Задача 102791

[Навстречу друг другу ]

Тема:

[

Динамическое программирование в игровых задачах

]

Сложность: 3+

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

Правила игры
Играют два игрока. За первым игроком закреплена область, включающая левую верхнюю клетку, за вторым – правую нижнюю. Игроки ходят по очереди. Делая ход, игрок перекрашивает свою область:
    А) в любой из шести цветов;
    Б) в любой из шести цветов, за исключением цвета своей области и цвета области противника.
В результате хода к области игрока присоединяются все прилегающие к ней области выбранного цвета, если такие имеются. Если после очередного хода окажется, что области игроков соприкасаются, то игра заканчивается.

Задание
Напишите программу, которая для каждого из пунктов (А и Б) определяет минимально возможное число ходов, по прошествии которых игра может завершиться.

Входные данные
Цвета пронумерованы цифрами от 1 до 6. Первая строка входного файла содержит целые числа M и N – размеры поля (1 ≤ M,N ≤ 50). Далее следует описание раскраски поля – M строк по N цифр (от 1 до 6) в каждой без пробелов. Первая цифра файла соответствует цвету левой верхней клетки игрового поля. Количество одноцветных областей не превосходит 50.

Выходные данные
В выходной файл выведите искомое количество ходов для каждого из пунктов. Если ваша программа решает только один из пунктов, выведите произвольное целое число в качестве ответа на другой пункт.

Пример входного файла
4 3
122
221
143
132

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

Прислать комментарий     Решение

Задача 102885

[Ориентация графа ]

Тема:

[

Обход графа в глубину

]

Сложность: 3+

Задан неориентированный граф с N вершинами, пронумерованными целыми числами от 1 до N. Напишите программу, которая последовательно решает следующие задачи:
    а) выясняет количество компонент связности графа;
    б) находит и выдает все такие ребра, что удаление любого из них ведет к увеличению числа компонент связности;
    в) определяет, можно ли ориентировать все ребра графа таким образом, чтобы получившийся граф оказался сильно связным (ориентированный граф называется сильно связным, если из любой его вершины можно пройти в любую другую, двигаясь по ребрам вдоль стрелок);
    г) ориентирует максимальное количество ребер, чтобы получившийся граф оказался сильно связным;
    д) определяет минимальное количество ребер, которые следует добавить в граф, чтобы ответ на пункт в) был утвердительным.

Входные данные
Во входном файле записано целое число N (1 ≤ N ≤ 100) и список ребер графа, заданных номерами концевых вершин.

Выходные данные
Ваша программа должна вывести в выходной файл последовательно ответы на пункты a)-д) в следующем формате:
    в первой строке запишите ответ на пункт а);
    во второй строке запишите количество ребер из ответа на пункт б), а в последующих строках выдайте сами эти ребра;
    в следующую строку выведите сообщение «NOT POSSIBLE», если требуемым в пункте в) способом ориентировать граф невозможно, иначе выведите сообщение «POSSIBLE»;
    далее выведите максимальное количество ребер графа, которые можно ориентировать (пункт г); в последующие строки выведите список этих ребер;
    в качестве ответа на пункт д) выведите количество ребер, которые следует добавить в исходный граф, а далее выведите сами эти ребра.
Ребра задаются указанием номеров своих концевых вершин, а при выводе ответа на пункт г) должна быть указана их ориентация (вначале выводится номер начальной вершины, затем – номер конечной). Если ответ на пункт а) отличен от единицы, то пункты в) и г) решать не следует и ответы на них не выводятся. Баллы за пункт в) в случае утвердительного ответа на него начисляются лишь в том случае, если программа правильным образом ориентировала ребра графа (пункт г).

Пример входного файла
4
1 2
2 4
3 4
4 1

Пример выходного файла
1
1
3 4
NOT POSSIBLE
3
1 2
2 4
4 1
1
1 3

Прислать комментарий     Решение

Задача 102886

[Кратеры на Луне ]

Темы:	[	Обход графа в глубину	]
Темы:	[	Динамическое программирование на графах без циклов	]

Сложность: 3+

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

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

Входные данные
Первая строка входного файла содержит целое число N – количество кратеров, отмеченных на карте (1 ≤ N ≤ 500). Следующие N строк содержат описания кратеров с номерами от 1 до N. Описание каждого кратера занимает отдельную строку и состоит из трех целых чисел, принадлежащих диапазону [-32768, 32767] и разделенных пробелами. Первые два числа представляют собой декартовы координаты его центра, а третье – радиус. Все кратеры различны.

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

Пример входного файла
4
0 0 30
-15 15 20
15 10 5
10 10 10

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

Прислать комментарий Решение

Задача 102887

[Электронная таблица ]

Темы:	[	Обход графа в глубину	]
	[	Динамическое программирование (прочее)	]
	[	Синтаксический разбор (прочее)	]

Сложность: 3+

Имеется таблица M × N, в каждой ячейке которой записано либо целое число, либо арифметическая формула. В формулах могут присутствовать целые числа, знаки *, /, +, -, (, ), пробелы и ссылки на значения из других ячеек таблицы, записываемые в виде {НомерCтроки, НомерCтолбца} (например, {1,10}). Требуется вычислить значения во всех ячейках заданной таблицы.

Входные данные:
В первой строке входного файла записаны целые числа M и N (1 ≤ M, N ≤ 20). В каждой из последующих M строк содержится описание очередной строки таблицы. Описание состоит из целых чисел и арифметических формул, разделенных символами | (ASCII-код 124). Все числа принадлежат диапазону [-32768, 32767], а длина каждой формулы не превышает 100 символов.

Выходные данные:
Выведите в выходной файл значения всех ячеек таблицы. Значения ячеек каждой строки таблицы должны быть записаны через пробел в отдельной строке выходного файла. Все значения следует выводить с точностью до двух знаков после десятичной точки. Если значение ячейки вычислить невозможно, вместо него следует вывести символ - (ASCII-код 45).

Пример входного файла
2 3
1      |    {1, 1   }*10        +3 |     -{1,2}/{2,2}
{2,3} |             0                     |           {2,1}

Пример выходного файла
1.00 13.00 -
- 0.00 -

Прислать комментарий     Решение

Задача 102889

[Хамелеон ]

Темы:	[	Обход графа в ширину	]
Темы:	[	Генерация объектов по номеру и номера по объекту	]

Сложность: 3+

Игра «Хамелеон» происходит в квадрате 3 × 3, в клетках которого находятся 8 фишек с буквами этого слова, а одна из клеток пуста. За один ход разрешается одну из фишек переместить на соседнюю пустую клетку. Цель игры – достигнуть расположения фишек, указанного на рисунке.

Х	А	М
Е	Л	Е
О	Н

Напишите программу, которая определяет план достижения цели за минимально возможное число ходов, либо сообщает, что цели достичь нельзя.

Входные данные
Во входном файле находится матрица 3 × 3, составленная из больших букв русского алфавита.

Выходные данные
Ваша программа должна вывести в первую строку выходного файла искомое число ходов, а в последующие – их список. Каждый ход задается координатами той фишки, которая перемещается. Если плана не существует, выведите в выходной файл сообщение «Нет решения».

Пример входного файла
ХАМ Е Е ОЛН

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

Прислать комментарий Решение

Страница: << 40 41 42 43 44 45 46 >> [Всего задач: 272]