--->
4 задач
<---
Источники
| Максимальное время работы на одном тесте: | 2 секунды |
Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает Ri, и для всех j сумма чисел ее j-го столбца не превышает Cj.
Вам задана таблица Z размера MxN, в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.
Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R1, R2, ..., RM. Далее идет срока, содержащая N целых неотрицательных чисел C1, C2, ..., CN. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит -1.
Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.
2 2 1 10 1 10 -1 -1 -1 1
0 1 1 1
В маленьком провинциальном городке есть маленькая школа, в которой учатся не совсем большие дети. После занятий они бегут на автобусную остановку, откуда автобус развозит их по домам.
По дороге от школы до остановки есть N перекрестков, соединенных улицами. Школьники с улицы на улицу переходят только на перекрестках.
Все школьники, как известно, любят мороженое. Известная компания Cold-N-Icy, производящая мороженое, решила воспользоваться этим. Она хочет разместить киоски с мороженым на некоторых перекрестках таким образом, чтобы любой путь школьника от школы до остановки проходил хотя бы через один перекресток, на котором установлен киоск.
Так как установка и содержание киоска — дорогое дело, то компания решила привлечь Вас для того, чтобы определить минимальное число киосков, которое необходимо установить.
Помогите компании Cold-N-Icy найти это минимальное число.
В первой строке входного файла находится число перекрестков N (1 ≤ N ≤ 100).
В каждой из последующих N строк находится информация о перекрестках, соединенных улицами между собой. Перекрестки нумеруются, начиная с единицы. В начале i-той строки находится число Ki – количество мест (перекрестков, школы или остановки), соединенных улицами с i-тым перекрестком. Далее идет Ki мест, разделенных пробелами. Для обозначения перекрестков используются их номера, школа обозначается как school, остановка обозначается как station.
Если перекресток i находится в списке перекрестка j, то обратное также верно.
Гарантируется, что от школы до остановки всегда существует путь.
Выведите одно число — минимальное число киосков, которые планируется установить.
2 2 school station 2 station school
2