Условие: На прямоугольном поле размером 2 на N (N<=10000) в нижней строке случайным образом расставлено некоторое количество мин, не видимых саперу, а в верхней строке в каждой клетке написаны числа от 0 до 3, которые совпадают с количеством мин в полях нижней строки, соседних с этой клеткой (расположены слева, под ней и справа). Требуется написать программу, которая находит все возможные расположения мин.
Технические условия: Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных: Входной файл INPUT.TXT содержит в первой строке число N, а во второй - числа из верхней строки, записанные через пробел.
Формат выходных данных: В первую строку выходного файла OUTPUT.TXT вывести количество возможных расположений мин (0, если такое невозможно). В следующих строках записать по одному найденному расположению мин (1 – есть мина, 0 – нет, числа разделить одним пробелом).
Примеры входных и выходных файлов: Input.txt 2 2 2
Output.txt 1 1 1
Решение: ---------- 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 (i<n) 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.
