Сапер - 3 уровень

Условие:
На прямоугольном поле размером 2 на N (N<=10000) в нижней строке случайным образом расставлено некоторое количество мин, не видимых саперу, а в верхней строке в каждой клетке написаны числа от 0 до 3, которые совпадают с количеством мин в полях нижней строки, соседних с этой клеткой (расположены слева, под ней и справа). Требуется написать программу, которая находит все возможные расположения мин.

Техническое условие:
Ограничение по времени тестирования: по 1 секунде на один тест.

Формат входных данных:
Входной файл INPUT.TXT содержит в первой строке число N, а во второй - числа из верхней строки, записанные через пробел.

Формат выходных данных:
В первую строку выходного файла OUTPUT.TXT вывести количество возможных расположений мин (0, если такое невозможно). В следующих строках записать по одному найденному расположению мин (1 – есть мина, 0 – нет, числа разделить одним пробелом).

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

Решение:
---------- cut ----------
Задача является одномерным аналогом игры, входящей в стандартную поставку Windows.

Пусть в левой нижней клетке есть мина, тогда, используя заданное значение в левой верхней клетке, можно узнать есть ли мина во второй слева нижней клетке (правда, при этом может получиться и недопустимое значение, но об этом далее). После этого, используя значение во второй верхней клетке, определяем наличие мины в третьей нижней клетке. Эти действия повторяем до тех пор, пока не произойдет одно из событий:

- найденные значения удовлетворяют всем равенствам,
- получено недопустимое значение.

Тогда в первом случае найдена расстановка мин, а во втором получили, что такой расстановки мин не существует. Проделав тоже самое в предположении, что в левом поле нет мины, мы либо найдем еще одну расстановку мин, либо определим, что таковой не существует.

В итоге получаем, что в задаче может:

- не быть решения,

- имеется одно решение,

- имеется два решения.

Изложенный алгоритм и используется в программе:
---------- cut ----------

var
  f, g : text;
  a, b : array[1..10000] of integer;
  n, i, a0, b0, c0, a1, b1, c1, c : integer;
  t0, t1 : boolean;
begin
  assign(f,'input.txt'); reset(f);
  readln(f,n);
  t0:=true; t1:=true;
  a0:=0; b0:=0; a[1]:=b0;
  a1:=0; b1:=1; b[1]:=b1;
  i:=1;
  while (n>i) and (t0 or t1) do
  begin
    i:=i+1;
    read(f,c);
    c0:=c-a0-b0; a[i]:=c0; a0:=b0; b0:=c0;
    t0:=t0 and ((c0=0) or (c0=1));
    c1:=c-a1-b1; b[i]:=c1; a1:=b1; b1:=c1;
    t1:=t1 and ((c1=0) or (c1=1))
  end;
  read(f,c);
  assign(g,'output.txt'); rewrite(g);
  t0:=t0 and (a0+b0=c);
  t1:=t1 and (a1+b1=c);
  if t0 and t1 then write(g,2)
  else
    if t0 or t1 then write(g,1)
  else write(g,0);
    if t0 then
  begin
    writeln(g);
    for i:=1 to n-1 do write(g,a[i],' ');
    write(g,a[n])
  end;
  if t1 then
  begin
    writeln(g);
    for i:=1 to n-1 do write(g,b[i],' ');
    write(g,b[n])
  end;
  close(g)
end.