В некоторой организации компьютеры пользователей объединены в локальную сеть. Также в этой организации есть несколько сетевых принтеров. В конце года пользователи начинают активно печатать различные годовые отчеты и делать это практически одновременно. Системный администратор знает схему сети и пропускную способность каждого кабеля. Пропускная способность измеряется в Мбит/с. Требуется по заданной схеме и пропускной способности определить максимальный поток данных, который может обработать данная локальная сеть. Считается, что во время годового отчета пользователи настолько заняты, что передают данные только на принтеры (не скачивают файлы из Интернета или с компьютеров других пользователей).
Сначала вводится число \(N\) (натуральное, не превышает 100) – количество объектов в сети. Затем следует \(N\) чисел, задающих вид каждого объекта: 1 – компьютер, 2 – принтер, 3 – хаб. Затем следует \(N\) строк по \(N\) чисел в каждой – пропускная способность проводов, соединяющих объекты сети. Число 0 означает отсутствие провода между какими-то объектами. Пропускная способность существующего провода – натуральное число, не превышает 1000. Гарантируется, что в сети есть хотя бы один компьютер и хотя бы один принтер.
Выведите единственное число – максимальный поток данных, который может передаваться по данной сети.
3 1 2 3 0 0 10 0 0 20 10 20 0
10
4 1 3 3 2 0 10 0 0 10 0 5 0 0 5 0 10 0 0 10 0
5
В стране Олимпия очень развита живопись. Картиной считается любой прямоугольник, который состоит из черных и белых единичных квадратов. Художник Олимпус решил радикально улучшить свои картины. Для этого он планирует к белому и черному цветам добавить еще и серый оттенок. По его задумке, граница между каждыми черным и белым квадратом должна содержать серую линию, чтобы образовался эффект плавного перехода.
Однако, перед началом работы, он обнаружил, что серая краска очень дорого стоит. Чтобы сэкономить деньги художник решил оценить, не выгоднее ли сначала перекрасить некоторые белые квадраты в черные, а черные в белые для того, чтобы минимизировать расходы на краску.
Напишите программу, которая по информации о существующей картине определяет минимальную сумму денег, которые понадобятся на ее улучшение.
Формат входных данных
Первая строка входного файла содержит пять натуральных чисел N, M, w, b, g. 1≤N, M≤70 – высота и ширина картины, 1≤w,b,g≤1000 – цена рисования одного белого единичного квадрата, черного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M литер. Литера B соответствует черному квадрату, а W – белому.
Формат выходных данных
Единственная строка выходного файла должна содержать одно целое число, которое есть минимальной суммой затрат на улучшение картины.
3 2 10 12 1 BW WB BW
7
В компанию по обслуживанию компьютеров поступило \(N\) заявок от клиентов. В компании есть \(S\) сотрудников разной квалификации. Руководитель компании знает, какие из заявок каждый сотрудник способен выполнить (возможно, каждый сотрудник может выполнить несколько заявок, также верно, что одну и ту же заявку способны выполнить несколько сотрудников). Каждый сотрудник в какой-то момент времени может выполнять не более одной заявки. Для выполнения каждой заявки достаточно ровно одного сотрудника.
Определите максимальное количество заявок, которые можно начать выполнять при оптимальной загрузке сотрудников.
Cначала вводятся числа \(N\) и \(S\) (натуральные, не превышают 100), затем вводится \(S\) строк по \(N\) чисел в каждой – сведения о квалификации сотрудников. Если в \(j\)-й позиции \(i\)-й строки находится 0, то \(i\)-й сотрудник не способен выполнить данную заявку, если 1 – то способен.
Выведите единственное число – максимальное количество заявок, которое можно начать выполнять.
2 2 1 1 1 1
2
3 3 1 0 0 0 1 0 0 0 1
3
Петя занимается разведением дракончиков. У него есть \(M\) зеленых дракончиков и \(K\) желтых. У Пети есть \(N\) двухместных аквариумов для дракончиков и \(M+K–2N\) одноместных.
Петя, понаблюдав некоторое время за своими дракончиками, установил, что некоторые пары дракончиков не могут жить вместе (будучи помещенными в один аквариум они тут же начинают драться), а также некоторые дракончики совершенно не переносят одиночества и поэтому не могут жить в одноместном аквариуме.
Петя хочет с использованием своих знаний так разместить дракончиков по аквариумам, чтобы в каждом двухместном аквариуме обязательно был один зеленый дракончик и один желтый, и при этом драконы, не переносящие одиночества, обязательно были бы помещены в двухместный аквариум, и в двухместном аквариуме никогда не оказывалось бы двух драконов, которые не могут жить вместе.
Вводятся числа \(M, K, N\) (\(M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200\)). Будем считать, что зеленые дракончики пронумерованы числами от \(1\) до \(M\), а желтые – числами от \(M+1\) до \(M+K\).
Далее идет число \(T\) (\(0 ≤ T ≤ MK\)) – количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет \(T\) пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе – желтого). Далее идет число \(Q\) (\(0 ≤ Q ≤ M + K\))– количество дракончиков, не переносящих одиночества. Далее идет \(Q\) чисел, задающих номера этих драконов.
В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие \(N\) строк выведите \(N\) пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.
2 1 1 1 1 3 1 1
NO
2 2 1 1 1 3 1 2
YES 2 4
На сырном заводе во Флатландии живут мыши. Они очень любят сыр и часто уничтожают запасы сыра, приготовленные для отправки в магазин.
Всего на заводе живет \(m\) мышей. Для \(i\)-й мыши известна ее скорость поедания сыра \(s_i\), мышь может съесть \(s_i\) грамм сыра в час.
Недавно мышам стал известен план работы завода на ближайшее время. Планируется изготовить \(n\) головок сыра. Про каждую головку известны \(r_i\) к началу какого часа она будет изготовлена, \(d_i\) в начале какого часа она начнет портиться, и \(p_i\) вес головки сыра в граммах.
Мыши решили съесть весь сыр. В любой момент времени каждая мышь может есть некоторую головку сыра. Мыши существа брезгливые, и одну и ту же головку сыра не могут есть одновременно несколько мышей. При этом в любой момент времени мышь может решить прекратить есть головку сыра и приняться за другую, в том числе ту, которую ранее ела другая мышь.
Мыши не любят есть сыр после того как он начал портиться. Но оставлять сыр недоеденным мыши не могут. Они решили организовать поедание сыра таким образом, чтобы величина \(t\), такая что какую-либо головку все еще продолжают есть через \(t\) часов после того как она начала портиться, была минимальна. Помогите мышам выяснить, как это сделать.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n \le 30\), \(1 \le m \le 30\)). Следующие \(n\) строк содержит по три целых числа: \(p_i\), \(r_i\) и \(d_i\) (\(1 \le p_i \le 10^5\), \(0 \le r_i \lt d_i \le 10^7\)). Далее следуют \(m\) строк, каждая из которых содержит по одному целому числу \(s_j\) (\(1 \le s_j \le 10^5\)).
Выведите одно вещественное число — искомое минимальное \(t\). Ваш ответ должен отличаться от правильного не больше чем на \(10^{-4}\).
Комментарий к примеру тестов
В первом примере мышам следует организовать поедание сыра следующим образом. Сначала первая мышь начинает есть первую головку сыра. Когда появляется вторая головка, она перестает есть первую и начинает есть вторую (в этот момент от первой осталось 9 граммов). Вторая мышь принимается есть первую головку сыра. Через 2.5 часа первая мышь доедает вторую головку сыра (на 0.5 часа позже чем она начала портиться) и снова начинает есть первую (вторая мышь за это время съела еще 5 граммов от первой головки и от нее осталось 4 грамма). Таким образом еще за час первая мышь доедает первую головку, также на 0.5 часа позже чем она начала портиться.
Во втором примере мышь успевает съесть сыр до того как он начинает портиться
2 2 13 0 4 10 1 3 4 2
0.5
1 1 1 0 1 1
0.0