13.5. Диспетчер процессов (5)

В любой момент времени операционная система может исполнять произвольное количество независимых процессов, и время, за которое каждый процесс будет выполнен, не зависит от того, сколько процессов выполнялось одновременно с ним. Однако одновременно могут выполняться только независимые процессы. В некоторых случаях процесс A может использовать данные, полученные процессом B (и произвольным количеством других процессов). Тогда к моменту старта процесса A все процессы, от которых он зависит, уже должны отработать.

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

Ввод из файла INPUT.TXT. В первой строке находится число N (2  N  20) — количество процессов, которые нужно выполнить. Во второй строке через пробел записаны N чисел от 1 до 1000; i-е число - это время в миллисекундах, требуемое для исполнения i-го процесса. Далее идут N строк, описывающих зависимости между процессами. В каждой из них находятся по N символов 'Y' и 'N' (заглавных латинских букв). Символ 'Y' в i-й из этих строк на j-м месте означает, что для запуска i-го процесса требуется завершить j-й. Символ 'N' означает, что i-й процесс не зависит от j-го напрямую.

Вывод в файл OUTPUT.TXT.В единственной строке вывести минимальное время в миллисекундах, требуемое для выполнения всех процессов, или –1, если при заданной таблице зависимостей группу процессов нельзя выполнить.

Примеры

Ввод 1 Ввод 2

3 2

100 200 300 10 10

NNN NY

NNN YN

YYN

Вывод 1 Вывод 2

500 -1

13.6. Жизнь на Марсе (7)

При высадке на Марс было основано N поселений. Каждое из них равномерно расширялось во все стороны на L марсианских миль в месяц. Постепенно поселения начали сливаться друг с другом, получая общее название. Какое минимальное время с момента высадки потребуется для того, чтобы на Марсе осталось не более K поселений?

Ввод из файла INPUT.TXT. В первой строке задаются через пробел три целых положительных значения: начальное количество поселений N (1 ≤ N ≤ 1000), число K (1 ≤ K ≤ 10, K< N) и скорость роста поселений L (1 ≤ L ≤ 100). Далее в следующих N строках содержатся через пробел целые координаты поселений X_i , Y_i (-1000 ≤ X_i , Y_i ≤ 1000) в марсианских милях.

Вывод в файл OUTPUT.TXT.В единственной строке вывести с точностью до 2 знаков минимальное время в месяцах с момента высадки, необходимое для того, чтобы в результате слияния осталось не более K поселений.

Ограничения. Время работы на одном тесте до 2 с. Объем используемой памяти: 64 мегабайта.

Пример

Ввод

3 2 1

-1 1

2 1

2 5

Вывод

1.50

13.7. Шпионские страсти (9)

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

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

Ввод из файла INPUT.TXT. Первая строка содержит три целых положительных числа N, A и B, разделённых пробелом: N – количество агентов, включая резидента, A – номер начального агента, а B – номер конечного агента, то есть резидента. Далее следуют N строк, описывающих связи агентов в виде матрицы стоимости C_ij. В i-й строке задаются через пробел стоимости передачи информации от агента с номером i агентам с номерами 1, 2, …, N соответственно в виде целых положительных чисел, то есть значения C_i1, C_i2,…, C_iN. Бесплатной передачи информации между агентами не существует. Если i-й агент не связан с j-м, то в соответствующем месте ставится 0. Связи каждого агента с самим собой заполняются нулями, то есть главная диагональ матрицы стоимостей состоит из нулей.

Ограничения: N ≤ 50, 0 ≤ C_ij ≤ 10000, время 2 с.

Вывод в файл OUTPUT.TXT. В единственной строке выводится минимальная суммарная стоимость передачи информации по двум непересекающимся цепочкам агентов. Если таких цепочек не находится, в файл OUTPUT.TXT выводится строка со словом No.

Примеры

Ввод 1 Ввод 2

4 1 4 4 1 3

0 2 3 9 0 5 2 0

1 0 0 6 2 0 4 7

1 2 0 5 0 1 0 0

0 0 0 0 3 7 0 0

Вывод 1 Вывод 2

16 No

13.8. Учебный план (6)

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

Ввод из файла INPUT.TXT. В первой строке задается число пар дисциплин N (1 ≤ N ≤ 300). В каждой из следующих N строк указываются через пробел два натуральных числа X_i , Y_i (X_i , Y_i ≤ 1000), определяющих номера дисциплин. Первая дисциплина должна изучаться раньше второй.

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

Примеры

Ввод 1 Ввод 2

7 8

1 2 1 2

1 3 1 3

2 5 2 5

3 4 3 4

4 2 4 2

3 2 3 2

6 4 6 4

5 3

Вывод 1 Вывод 2

Yes No

1 6 3 4 2 5 2 5 3 4 2

13.9. Морские дьяволы (6)

Полигон для тренировки морских десантников представляет собой площадку в форме прямоугольника с водоемами и задается матрицей размером M x N. Каждый элемент матрицы содержит либо символ '@', обозначающий участок водной поверхности, либо символ '.' (точка), обозначающий участок суши. Подразделение морских дьяволов находится в клетке, соответствующей левому верхнему углу матрицы. Ему поставлена задача достичь участка, соответствующего правому нижнему углу матрицы. Десантники могут передвигаться в направлениях вдоль сторон полигона, не выходя за его пределы. Они планируют преодолеть как можно меньше клеток, занятых водой. Если это можно сделать по-разному, то предпочтительнее такой вариант, когда путь включает меньшее количество клеток суши.

Ввод из файла INPUT.TXT. В первой строке содержатся числа M и N (1  M, N  50), разделенные пробелами. В следующих M строках находится матрица, представляющая полигон, по N подряд идущих символов в строке. Гарантируется, что левый верхний и правый нижний углы матрицы соответствуют участкам суши.

Вывод в файл OUTPUT.TXT. В единственной строке вывести через пробел наименьшее число клеток K, которое подразделение должно преодолеть по воде, и для найденного значения K минимальное число клеток по суше L, включая начальную и конечную клетки.

Примеры

Ввод 1 Ввод 2

7 7 7 6

..@@... .@@@..

..@@@.. ......

@.@@..@ @.@@.@

@@@...@ @@@..@

..@.... ..@...

..@...@ ..@...

....@.. ....@.

Вывод 1 Вывод 2

1 14 0 12

13.10. Детали (6)

Некоторое предприятие выпускает двигатели для автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия заключается в том, что одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей. Генеральный директор поставил перед предприятием задачу: за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке. Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.

Ввод из файла INPUT.TXT. Первая строка содержит число n (1 ≤ n ≤ 100000) – количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂ … p_n , определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд. Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера. Сумма всех чисел k_i не превосходит 200000. Известно, что не существует циклических зависимостей в производстве деталей.

Вывод в файл OUTPUT.TXT. В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел – номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Примеры

Ввод 1 Ввод 2 Ввод 3

3 2 4

100 200 300 2 3 2 3 4 5

1 2 1 2 2 3 2

0 0 1 3

2 2 1 0

2 1 3

Вывод 1 Вывод 2 Вывод 3

300 2 5 2 9 3

2 1 2 1 3 2 1

14. Игры двух лиц

Игры, в которых участвуют два игрока, широко известны. Как правило, такие игры являются антагонистическими: выигрыш одного игрока означает проигрыш другого.

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

1. Определена исходная позиция (в картах или домино это не так).

2. Оба игрока имеют полную информацию о текущей позиции (снова в картах или домино это не выполняется).

3. Ходы делаются в пределах правил, но по желанию игроков (в нардах и других играх с костями это не так).

Примерами детерминированных игр являются шашки, шахматы, крестики-нолики.

Сложные игры вроде шахмат имеют с первых ходов много вариантов продолжения. Из-за этого трудно сформулировать беспроигрышный "алгоритм игры”. Мы опишем общий подход к программированию таких игр [1].

С другой стороны есть большое количество более простых игр с известной стратегией. Это значит, что один из игроков может гарантировать себе наилучший результат при любой игре соперника. Главное в этих играх – найти методику выбора ходов в зависимости от позиции и ответных ходов противника. Такие игры будут рассмотрены во второй части раздела [3].

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

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

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

Назовем игроков ПЛЮС и МИНУС. Выбор хода каждого игрока соответствует выбору одного из сыновей вершины, которая описывает текущую позицию. В дереве игры уровни вершин, в которых выбираются ходы игроков ПЛЮС и МИНУС, чередуются. Рассмотрим простейший способ построения оценочной функции позиций с точки зрения одного из игроков, например, игрока ПЛЮС.

Присвоим листьям, соответствующим выигрышным позициям, оценку +1, ничейным 0, проигрышным -1. Пусть некоторая вершина дерева A, сыновями которой являются только листья, соответствует ходу игрока ПЛЮС. Очевидно, он должен выбрать одного из сыновей с масимальным значением оценки, поэтому примем это максимальное значение в качестве оценки вершины A. Отцовская для A вершина B соответствует ходу игрока МИНУС. Поскольку оценки в листьях устанавливались для игрока ПЛЮС, игрок МИНУС должен наоборот выбирать сына с минимальной оценкой, предполагая, что его противник сделает лучший ход, то есть оценкой вершины B станет минимум оценок сыновей. В этом и состоит принцип минимакса. Он получен в предположении, что каждый игрок стремится к наивысшему результату при условии наилучших ходов противника.

Таким образом, корень дерева получит оценку +1, 0 или –1, что предопределяет результат игры. На практике все обстоит сложнее. В сложных играх дерево настолько велико, что не поддается подобным расчетам. Например, в шахматах белые могут сделать 20 вариантов первого хода, на каждый из которых может быть 20 вариантов ответа противника, то есть после полного первого хода может получиться 400 различных позиций. Приходится дерево игры строить не до конечных позиций, а в листьях прибегать к статической оценке. С каждым сделанным ходом дерево достраивается вниз. Чем глубже строится дерево игры и чем точнее статические оценки, тем сильнее игрок, будь то человек или программа. Шахматист применяет неявные статические оценки, используя теорию, интуицию, пристрастие к определенным позициям, антипатии противника по отношению к некоторым позициям и т. п.