Каталог по темам

Задачи

Страница: << 30 31 32 33 34 35 36 >> [Всего задач: 277]

Задача 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

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

Задача 102891

[Катаем кубик ]

Темы:	[	Построение перечислителя	]
Темы:	[	Кратчайшие пути в графах	]

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

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

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

Входные данные
Во входном файле через пробел записаны координаты начального и конечного полей и 6 чисел, написанных на передней (в начальный момент), задней, верхней, правой, нижней и левой гранях кубика соответственно. Координаты полей указываются в стандартной шахматной нотации (см. пример). Начальное и конечное поля различны.

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

Пример входного файла
e2 e3 0 8 1 2 1 1

Пример выходного файла
5 e2 d2 d1 e1 e2 e3

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

Задача 102892

[Иванушка и царевна ]

Тема:

[

Кратчайшие пути в графах

]

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

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

Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну).

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

Входные данные
Первая строка входного файла содержит три целых числа: N – количество кочек в болоте (3 ≤ N ≤ 10), I – количество оборотов веревки (1 ≤ I ≤ 6) и S – номер кочки, на которой в начальный момент стоит Иванушка (1 ≤ S ≤ N). Каждая из следующих N строк содержит вещественные координаты одной из кочек, записанные через пробел. Известно, что никакой отрезок, соединяющий две кочки, не проходит через центр болота, имеющий по соглашению координаты (0, 0).

В следующих N строках записана матрица N × N, составленная из вещественных чисел. Число в i-й строке и j-м столбце этой матрицы означает количество водорослей, цепляющихся за ноги Иванушки при прыжке с i-й кочки на j-ю.

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

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

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

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

Задача 102897

[Покрытие путями ]

Тема:

[

Паросочетания

]

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

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

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

Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.

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

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

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

Страница: << 30 31 32 33 34 35 36 >> [Всего задач: 277]