print1600. Мавританские карты

printМавританские карты

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

При раскопках в южной Мавритании были обнаружены манускрипты, в которых упоминалось об очень древней карточной игре. Ученых заинтересовало то, что в данной игре нет индивидуальной победы. Все участники стараются добиться единой победы.
Правила игры
В игре участвуют два игрока. В начале игры составляется колода карт – игроки договариваются о количестве карт в колоде, и колода смешивается из нескольких случайным образом. Затем игрокам раздаются все карты. В ходе раздачи карты раскладываются цепочками одна за другой напротив соответствующего игрока открытыми. После раздачи у игроков может быть различное количество карт. Игра состоит из последовательности ходов. За каждый ход игроки забирают друг у друга по одной карте из цепочки; выбранные карты уходят в отбой. По желанию каждый из игроков может пропустить ход, поступить так можно любое количество раз. Игра заканчивается, когда цепочки карт обоих игроков становятся абсолютно одинаковыми.
На раскопках археологам так понравилась новая игра, что они проводили многие часы за ней. Но они никак не могли оценить, насколько хорошо они научились играть в эту игру. Ваша задача написать программу, которая по заданной раздаче карт выдаст минимальное количество ходов необходимое для достижения цели.
Примечание
Пустая последовательность карт также является выигрышной.
Ввод
Первая строка входа содержит число `N` – количество наборов входных данных (`1\ ≤\ N\ ≤20`). Каждый набор состоит из двух строк. Каждая из строк начинается с числа `K` – количество карт в соответствующей цепочке; далее через пробел записаны карты, выпавшие соответствующему игроку. Общее количество карт в колоде не превышает 2000. Максимальный номинал карты не превышает 2000000000.
Вывод
Выходной файл должен содержать `N` строк. Каждая из строк должна содержать одно число – минимальное количество ходов необходимое для достижения победы в соответствующем тесте.

Пример ввода

2
3 1 2 3
4 1 3 4 5
5 1 2 3 4 5
5 1 2 3 4 5

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

2
0
Источник: Личное первенство по программированию среди студентов ИКИТ, апрель 2011

loading