Вы - -й посетитель этой странички 

Решение задач XIII международной олимпиады

Е.В.Андреева.

Москва

Продолжение. Cм. № 37, 40 , 42/2001

СКЛАД

У финской компании, выпускающей высокотехнологичное оборудование, имеется большой прямоугольный склад.  На складе работают менеджер и рабочий. Стороны прямоугольника, изображающего склад на плане, в порядке их обхода называют левой,  верхней, правой и нижней. Пол склада разделен на единичные квадраты. На плане они образуют ряды и колонки. Ряды пронумерованы целыми числами 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 целых чисел — идентификационные номера контейнеров в возможной последовательности прибытия. Каждая строка описывает последовательность, которая не записана ни в одной другой строке.

Примеры входных и выходных файлов

Пример 1:

DEPOT.IN                          DEPOT.OUT

3                                          3 2 1 4 9 5

3 1 4 5                                 3 2 1 9 4 5

2 2 9                                    3 4 2 1 9 5

1 3                                       3 2 4 1 9 5

                                            3 2 9 1 4 5

                                            3 9 2 1 4 5

                                            3 4 2 9 1 5

                                            3 4 9 2 1 5

                                            3 2 4 9 1 5

                                            3 2 9 4 1 5

                                            3 9 2 4 1 5

                                            3 4 2 9 5 1

                                            3 4 9 2 5 1

                                            3 2 4 9 5 1

                                            3 2 9 4 5 1

                                            3 9 2 4 5 1

 

П р и м е р 2:

DEPOT.IN                         DEPOT.OUT

2                                         3 1 2

2 1 2                                   1 3 2

1 3

Оценка программы

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

Решение

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

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

Приведем программу решения данной задачи.

const maxN = 15;

type carr = array [1 .. maxN] of longint;

var

  i, j, k, r, n : longint;

  tbl : array [1..maxN, 1..maxN] of longint;

  ntbl, order : carr;

procedure recurse ( nd : longint );

var

  i, j, k, l, v, t : longint;

  c : carr;

begin

if nd = n then

begin {решение построено в обратном порядке}

    for i := n downto 1 do

      write(order[i] ,  '  ' ) ;

    writeln ; exit

end;

for i := 1 to r do

begin

    if ntbl[i] = 0 then break;

   if ntbl[i] > ntbl[i + 1] then

    begin

      v := tbl[i, ntbl[i]];

      {убираем контейнер v из ряда i}

      dec(ntbl[i]);

      for j := i - 1 downto 1 do

        for k := ntbl[j] downto 1 do

          if v > tbl[j, k] then

         begin

            t := v; v := tbl [j, k] ;

            tbl [j, k] := t; c[j] := k;

           break

          end;

        order [nd + 1] := v;

        recurse (nd + 1) ;

        {восстанавливаем контейнер v}

        for j := 1 to i - 1 do

        begin

          t := v; v := tbl [j, c [ j ] ];

          tbl [j, c [ j ] ] := t

        end;

        inc ( ntbl [ i ] ) ;

        tbl [ i , ntbl [ i ] ] := v

      end

  end

end;

begin

  assign ( input , 'depot.in'); reset ( input ) ;

  assign (output, 'depot.out' ) ; rewrite (output );

  read ( r );  n := 0;

  for i := 1 to r do

  begin

    read ( ntbl [ i ] ) ;

{ кол-во контейнеров в ряду i }

  inc ( n, ntbl [ i ] );

  for j := 1 to ntbl [ i ] do

    read ( tbl [ i, j ] )

  end;

  ntbl[r + 1] := 0;

  recurse(0)

end.

Окончание следует