Входные данные: depot.in Выходные данные: depot.out Ограничения на память: 32 MB Время на тест: 0.3 секунды Тесты к задаче:Скачать
У финской компании, выпускающей высокотехнологичное оборудование, имеется большой прямоугольный склад. На складе работают менеджер и рабочий. Стороны прямоугольника, изображающего склад на плане, в порядке их обхода называют левой, верхней, правой и нижней. Пол склада разделен на единичные квадраты. На плане они образуют ряды и колонки. Ряды пронумерованы целыми числами 1, 2, ..., начиная с верхней стороны, а колонки пронумерованы целыми числами 1,2,..., начиная с левой стороны.
Для хранения технологических устройств на складе имеются контейнеры. Контейнеры имеют индивидуальные идентификационные номера. Каждый контейнер занимает один квадрат. Склад настолько велик, что количество хранящихся контейнеров всегда меньше, чем количество рядов, и меньше, чем количество колонок. Контейнеры со склада не вывозятся, но иногда на склад поступает новый контейнер. Вход на склад находится в левом верхнем углу.
Рабочий расставил контейнеры вблизи левого верхнего угла склада некоторым способом, чтобы можно было легче найти их по идентификационным номерам. Он использует следующий метод.
Пусть необходимо разместить на складе контейнер с идентификационным номером k (будем называть его контейнер k). Рабочий проходит по первому ряду слева направо и ищет первый контейнер с идентификационным номером, большим чем k. Если он не находит такого контейнера, то контейнер k устанавливается непосредственно после самого правого контейнера в этом ряду. Если же такой контейнер l найден, то контейнер l заменяется на контейнер k, а контейнер l размещается в следующем ряду с помощью этого же метода. Если рабочий достигает ряда, в котором нет контейнеров, то контейнер устанавливается в самом левом квадрате этого ряда.
Положим, что контейнеры 3,4,9,2,5,1 прибыли на склад именно в таком порядке. Тогда размещение контейнеров на складе будет следующим:
1 4 5
2 9
3
Между менеджером и рабочим происходит следующий диалог:
Менеджер: Контейнер 5 прибыл раньше контейнера 4?
Рабочий: Нет, это невозможно.
Менеджер: О! Так ты можешь восстановить последовательность прибытия контейнеров по их расположению!
Рабочий: Вообще-то нет. Например, последовательность поступления контейнеров, которые сейчас находятся на складе, могла быть 3,2,1,4,9,5, либо 3,2,1,9,4,5, либо еще какая-нибудь из оставшихся 14 вариантов.
Менеджер не хочет выглядеть глупым перед рабочим. Помогите ему и напишите программу, которая по заданному расположению контейнеров вычисляет все возможные последовательности поступления контейнеров.
ВХОД
Входной файл имеет имя depot.in. Первая строка этого файла содержит единственное целое число R: количество рядов, в которых есть контейнеры. Последующие R строк содержат информацию о рядах 1, ..., R. Первым в каждой из этих строк находится число M: количество контейнеров в ряду. Затем в этой строке следуют M целых чисел: идентификационные номера контейнеров в ряду слева направо. Все идентификационные номера контейнеров I удовлетворяют ограничению 1 ≤ I ≤ 50.
Обозначим общее количество контейнеров на складе через N, 1 ≤ N ≤ 13.
ВЫХОД
Выходной файл имеет имя depot.out. Выходной файл содержит столько строк, сколько существует возможных различных последовательностей поступления контейнеров. Каждая из этих строк содержит N целых чисел - идентификационные номера контейнеров в возможной последовательности прибытия. Каждая строка описывает последовательность, которая не записана ни в одной другой строке.
Если выходной файл содержит хотя бы одну неправильную последовательность или не содержит последовательностей вообще, то за тест начисляется 0 баллов. В противном случае, балл вычисляется по следующему правилу. Если выходной файл содержит все возможные последовательности, каждую в точности один раз, то начисляется 4 балла. Если в выходном файле содержится не менее половины возможных последовательностей и каждая из них встречается один раз, то начисляется 2 балла. Если в выходном файле содержится меньше половины возможных последовательностей или некоторые из них встречаются более одного раза, то за тест начисляется 1 балл. Копания "Европлан". Лизинг легковых автомобилей, оборудования и лизинг грузовиков. . купить китайский iphone . Вашему вниманию безупречная перевозка контейнером Мирового уровня . Река, Коттеджный посёлок Чулково Club.