Страница: 1 Отображать по:
#598
Маджонг
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя недавно узнал о существовании игры маджонг. Она ему показалась настолько интересной, что он играет в нее целыми днями. Для этой игры необходима прямоугольная доска размером m  n полей и набор фишек разных цветов. При этом фишек каждого цвета в наборе должно быть ровно две. В начале игры фишки располагаются на доске произвольным образом.

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

Например, на рисунке показан пример позиции в игре, когда можно сделать два хода: снять две фишки четвертого цвета, поскольку они являются самыми левыми в своих горизонталях, либо снять две фишки первого цвета, поскольку они являются самыми верхними в своих вертикалях.

Цель игры состоит в том, чтобы сделать как можно больше ходов.

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

Входные данные

Первая строка входного файла содержит размеры доски: два целых числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 300, хотя бы одно из этих чисел четно). Далее следуют \(m\) строк по \(n\) чисел в каждой, \(j\)-е число в \(i\)-й из этих строк представляет собой номер цвета \(j\)-й слева фишки в \(i\)-й горизонтали. Цвета пронумерованы натуральными числами от 1 до \(n\)*\(m\) / 2. На доске ровно две фишки каждого цвета.

Выходные данные

В первой строке выходного файла выведите \(k\) — максимальное количество ходов, которое может сделать Петя из заданной начальной позиции. Во второй строке выходного файла выведите разделенные пробелами \(k\) чисел — номера цветов фишек в том порядке, в котором они должны сниматься с доски. Если возможных ответов несколько, выведите любой.

Примеры
Входные данные
1 2
1 1
Выходные данные
1
1
Входные данные
4 1
1
2
2
1
Выходные данные
2
2 1
#600
Цепочка слов
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Будем называть цепочкой слов длины n последовательность слов \(w_1\), \(w_2\), …, \(w_n\), такую, что для всех \(i\) от 1 до \(n\) – 1 слово \(w_i\) является собственным префиксом слова \(w_i\)+1.

Слово \(u\) длины \(k\) называется собственным префиксом слова \(v\) длины \(l\), если \(l\) > \(k\) и первые \(k\) букв слова \(v\) совпадают со словом \(u\). Например, «program» является собственным префиксом слова «programmer».

Задано множество слов \(S\) = {\(s_1\), \(s_2\), …, \(s_m\)} и последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)]. Требуется найти такие числа \(l\) и \(r\) (\(l\) ≤ \(r\)), что \(s_x\)[\(l\)], \(s_x\)[\(l\) + 1], …, \(s_x\)[\(r\) – 1], \(s_x\)[\(r\)] является цепочкой слов, и количество слов в цепочке (число \(r\) – \(l\) + 1) максимально.

Входные данные

Первая строка входного файла содержит целое число \(m\) (1 ≤ \(m\) ≤ 250 000). Каждая из следующих \(m\) строк содержит по одному слову из множества \(S\).

Все слова не пусты, имеют длину, не превосходящую 250 000 символов, и состоят только из строчных букв латинского алфавита. Суммарная длина всех слов не превосходит 250 000.

Следующая строка содержит число \(k\) (1 ≤ \(k\) ≤ 250 000). Последняя строка входного файла содержит \(k\) чисел — последовательность чисел \(x\)[1], \(x\)[2], …, \(x\)[\(k\)] (для всех \(i\) выполнено 1 ≤ \(x\)[\(i\)] ≤ \(m\)).

Выходные данные

Выведите в первой строке выходного файла два числа: \(l\) и \(r\). Если оптимальных ответов несколько, выведите любой из них. Разделяйте числа пробелом.

Примеры
Входные данные
3
zngs
rjzr
zng
3
3 1 1
Выходные данные
1 2
Входные данные
6
gjnuitvaowpy
gjnuitvaowpym
gjnuitvaowp
rjzrociinzeco
tgbotnzepnvm
aigqbzpnerv
9
2 3 1 2 3 1 2 3 1
Выходные данные
2 4
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест