1. Кубики (автор - Александр Рыбак)
Максимальная оценка: 100 баллов
Ограничение по времени: 1 сек.
Ограничение по памяти: 32 MБ
Входной файл: cubes.in
Исходный файл: cubes.out
Приложение: cubes .*
Несмотря на то, что Петрик Пяточкина ходит в школу, он все еще продолжает играть с кубиками.С одинаковых кубиков он излагает ступени вдоль стены. Для этого составляет столбики из кубиков следующим образом:
● первый столбик стоит вплотную к стене;
● второй столбик стоит вплотную к стене и вплотную к первой колонки справа от него;
● третий столбик стоит вплотную к стене и вплотную к второй колонки справа от него и так далее ...
Высоты столбиков не растут при рассмотрении ступенек слева направо. Иначе говоря, если hi - высота i го столбца, то h1 ≥ h2 ≥ h3 ≥ ... .
Петрик устанавливает кубики в некоторой последовательности. Он установил для себя такие правила:
(1) кубик, расположен не на полу, можно поставить только после кубика, на котором он должен стоять. Иначе говоря, нельзя подсовывать кубики под уже поставлены;
(2) кубик, который находится не в первой колонке, можно поставить лишь после установления кубика, расположенного слева от него.
Задачи
Найти количество различных способов последовательного установления кубиков, в результате которых возникнут лестница с заданными высотами столбцов h1, h2, ..., hk.Учитывают только те способы, удовлетворяющих условиям (1) и (2).
Входные данные
Первая строка входного файла содержит натуральное число k - количество столбцов (1 ≤ k ≤ 6).
Вторая строка входного файла содержит k натуральных чисел h1, h2, ..., Hk - количества кубиков соответственно в первый, второй, ..., k м столбце лестницы (6 ≥ h1 ≥ h2 ≥ ... ≥ hk ≥ 1).
Входные данные
Единственная строка выходного файла должна содержать количество различных способов расположения кубиков в заданную конфигурацию согласно указанным правилам (1) и (2) при данных высотах столбцов.

{ Turbo Pascal }

type
  matr=array[1..6,1..6]of shortint;

var
  k:byte;
  h:array[1..6]of byte;
  m:matr;
  i,j:byte;
  kol:longint;
  s:byte;
  f:text;

procedure find(nomer:byte;m:matr);
var
  i,j,p:byte;
  f:text;
begin
    for j:=1 to k do
      begin
        if m[1,j]=-1 then
          break;
        for i:=1 to h[j] do
          begin
            if m[i,j]=-1 then
              break;

            if m[i,j]=0 then
              begin
                if (i-1>=1)and(m[i-1,j]=0)then continue;
                inc(nomer);
                m[i,j]:=nomer;
                if i+1<=h[j] then
                  m[i+1,j]:=0;
                if (j+1<=k)and(h[j+1]>=i)and((i-1=0)or((i-1>=1)and(m[i-1,j+1]>=1))) then
                  m[i,j+1]:=0;

                find(nomer,m);
                if nomer=s then
                  inc(kol);
                if (i=1)and(j=1) then
                  begin
                    assign(f,'cubes.out');
                    rewrite(f);
                    writeln(f,kol);
                    close(f);
                    halt;
                  end;
                m[i,j]:=0;
                for p:=i+1 to h[i] do m[p,j]:=-1;
                for p:=j+1 to k do m[i,p]:=-1;

                dec(nomer);
              end;
          end;
      end;
end;



begin
  s:=0;
  assign(f,'cubes.in');
  reset(f);
  readln(f,k);
  for i:=1 to k do
    begin
      read(f,h[i]);
      inc(s,h[i]);
    end;
  close(f);
  for j:=1 to 6 do
    for i:=1 to 6 do
      m[i,j]:=-1;
  m[1,1]:=0;
  kol:=0;
  find(0,m);
end.