---> 4 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 Отображать по:
Максимальное время работы на одном тесте: 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 
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

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

По дороге от школы до остановки есть 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

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест