07/04/2025 04:53:34

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1242. Задача Тамерлана

Ограничения: время – 5s/10s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На доске размером

$N\ times\ M$ разложено несколько монет разного номинала. В клетке может лежать не более одной монеты. Можно поставить шахматного коня на любую клетку доски, в том числе занятую монетой, и затем, делая ходы по шахматным правилам, собирать монеты на клетках. В конце путешествия конь должен вернуться на начальную клетку. За выполнение каждого хода нужно заплатить одну денежную единицу. Можно проходить по клеткам доски несколько раз и собрать не все монеты. Допустимо также круговое путешествие в 0 ходов, при котором конь не двигается с начальной клетки. Выигрыш в этой задаче определяется как разница между стоимостью собранных монет и количеством ходов, сделанных конем.

Напишите программу, вычисляющую максимальный выигрыш и последовательность ходов, которая позволит его получить.

Первая строка ввода содержит три целых числа – размеры доски

$N$ и

$M$ (

$4\ ≤\ N,\ M\ ≤\ 100$ ) и количество монет

$K$ (

$1\ ≤\ K\ ≤\ 15$ ). Далее следует

$K$ строк, содержащих по три целых числа – номера строки

$r_i$ (

$1\ ≤\ r_i\ ≤\ N$ ) и столбца

$c_i$ (

$1\ ≤\ c_i\ ≤\ M$ ) клетки, в которой находится

$i$ -я монета, и номинал монеты

$a_i$ (

$1≤\ a_i\ ≤\ 100$ ).

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

Пример ввода

Пример вывода

19
4 6 3 4 2 6 3 8 5 7 6 5 4 6

26/09/2009	Южно-Уральская открытая олимпиада, личное первенство (E)
04/07/2013	Лето 2013-4 (E)
08/07/2020	Летние сборы - 5 (D)