Игра с таблицей
(Время: 3 сек. Память: 256 Мб Сложность: 62%)
Дана таблица A из h строк и w столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от 1 до h сверху вниз, столбцы пронумерованы от 1 до w слева направо.
Разрешается применять к этой таблице следующие операции:
- выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);
- выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).
Эти операции разрешается применить произвольное число раз в любом порядке.
Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой
чисел, равной заданному числу s, и если да, то какие операции и в каком порядке необходимо
применить.
Входные данные
Первая строка входного файла INPUT.TXT содержит числа h и w — размеры таблицы (1 ≤ h, w ≤ 15).
Каждая из следующих h строк содержит по w целых чисел — таблицу A (0 ≤ Ai,j ≤ 109).
В последней строке ввода находится число s — необходимая сумма (1 ≤ s ≤ 1018).
Выходные данные
В выходной файл OUTPUT.TXT выведите строку «NO», если получить таблицу с суммой чисел s из исходной невозможно. Иначе:
- В первой строке выведите строку «YES».
- Во второй строке выведите единственное число k — количество операций с таблицей, которые
необходимо применить, чтобы получить из неё таблицу с суммой чисел s.
- В каждой из следующих k строк выведите по два целых числа tj , ij, где tj = 1, если очередная операция производится со строкой, и tj = 2, если она производится со столбцом таблицы. Число
ij должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с
которой эта операция производится.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 3
1 2 3
2 3 1
3 1 2
8 | YES
2
1 3
2 3 |
| 2 | 2 3
2 2 2
2 2 2
5 | NO |
| 3 | 5 5
1 2 1 4 5
2 5 4 1 2
4 2 4 3 1
5 5 3 2 4
1 2 4 5 2
34 | YES
3
1 4
1 5
2 1 |
Замечание
В первом примере изначально дана следующая таблица:
Удалив третьи строку и столбец получим таблицу с суммой чисел 8:
Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел 5 из исходной.
В третьем примере изначально дана таблица:
Удалив последние две строки и первый столбец, получим таблицу с суммой чисел 34:
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
