Олимпиадный тренинг

Задача . Игра с таблицей


Дана таблица \(A\) из \(h\) строк и \(w\) столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от \(1\) до \(h\) сверху вниз, столбцы пронумерованы от \(1\) до \(w\) слева направо.

Разрешается применять к этой таблице следующие операции:

  • выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);

  • выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу \(s\), и если да, то какие операции и в каком порядке необходимо применить.

Формат входных данных

Первая строка ввода содержит числа \(h\) и \(w\) — размеры таблицы (\(1 \leq h, w \leq 15\)).

Каждая из следующих \(h\) строк содержит по \(w\) целых чисел — таблицу \(A\) (\(0 \leq A_{i,j} \leq 10^{9}\)).

В последней строке ввода находится число \(s\) — необходимая сумма (\(1 \leq s \leq 10^{18}\)).

Формат выходных данных
Если получить таблицу с суммой чисел \(s\) из исходной невозможно, выведите строку <<NO>>.

Иначе:

  • В первой строке выведите строку <<YES>>.

  • Во второй строке выведите единственное число \(k\) — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел \(s\).

  • В каждой из следующих \(k\) строк выведите по два целых числа \(t_{j}, i_{j}\), где \(t_{j} = 1\), если очередная операция производится со строкой, и \(t_{j}=2\), если она производится со столбцом таблицы. Число \(i_{j}\) должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.

В первом примере изначально дана следующая таблица:

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}\)

Удалив третьи строку и столбец получим таблицу с суммой чисел \(8\):

\(\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}\)

Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел \(5\) из исходной.

В третьем примере изначально дана таблица:

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}\)

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел \(34\):

\(\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}\)


Примеры
Входные данныеВыходные данные
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

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя