Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Игра с таблицей

(Время: 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.TXTOUTPUT.TXT
13 3
1 2 3
2 3 1
3 1 2
8
YES
2
1 3
2 3
22 3
2 2 2
2 2 2
5
NO
35 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:


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 A. Посадка в самолет
 B. Битоническая последовательность
 C. Игра с таблицей
 D. Выбор столицы
 E. Разбиение массива
 F. Бактерии
 G. Разбиение на тройки
 H. Обходы бинарного дерева

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



продвижения сайтов естественными ссылками