Входные данные

Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта (1N10, 1M10). Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.

Выходные данные

В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.

Примеры

Input.txt	Output.txt
1 10 1 0 0 0 0 0 0 0 0 1	0
2 5 0 0 0 0 0 0 1 1 1 0	2

Решается методом перебора с возвратом.

{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}

{$M 65520,0,655360}

const maxn=10;maxm=10;

l:array[1..11] of integer=(1,2,4,8,16,32,64,128,256,512,1024);

var

a:array[0..maxn,0..maxm] of integer; карта лабиринта

b:array[1..maxn+1,-1..1024] of boolean;

c:array[1..maxn] of integer;

ans,now:array[1..maxn] of integer;

n,m:integer;

res,nowres:longint;

time:longint absolute $0:$46c;

oldtime:longint;

procedure out; forward;

procedure init;

var i,j:integer;

begin

oldtime:=time;

assign(input,'input.txt');

reset(input);

read(n,m);

for i:=1 to n do

for j:=1 to m do

begin

read(a[i,j]);

c[i]:=(c[i] shl 1)+a[i,j];

end;

close(input);

end;

procedure rec(p:integer;q1,q2:integer); рекурсивная процедура поиска решения

var i,j:integer;

f:boolean;

pr:longint;

begin

if (time-oldtime)/8.2>7.9 then exit; отсечение по времени

if nowres>=res then exit; если текущий результат хуже

найденного ранее, то возвращаемся

if p=n+1 then если все просмотрели то

возвращаемся

begin

if nowres<res then если получили лучший результат

begin res:=nowres;ans:=now;end; то запоминаем его

exit;

end;

inc(p); переходим к рассмотрению

следующего варианта

if b[p,-1] then rec(p,0,0) else

for i:=0 to l[m+1]-1 do

if (b[p,i])or(b[p,-1]) then

begin

f:=true;

for j:=0 to m-1 do

if ((i and (1 shl j))=0)and((q1 and (1 shl j))<>0)and

((q2 and(1 shl j))=0)and(not b[p-1,-1])and(a[p-1,j+1]<>1) then

f:=false;

if f then begin

pr:=0;

for j:=0 to m-1 do

if (i and (1 shl j))<>(i and (1 shl (j+1))) then

if (i and(1 shl j)=0)then inc(pr);

if i and (l[m])=0 then inc(pr);

for j:=0 to m-1 do

if (((q1 and (1 shl j))=0) and ((i and (1 shl j))<>0))and(a[p,j+1]<>1)

then inc(pr);

for j:=0 to m-1 do

if (a[p-1,j+1]=1)and(i and(1 shl j)<>0)and(a[p,j+1]<>1) then inc(pr);

now[p]:=i;

inc(nowres,pr);

rec(p,i,q1);

dec(nowres,pr);

end;

end;

end;

procedure solve;

var i,j,k:integer;

begin

res:=maxlongint;

fillchar(b,sizeof(b),true);

for i:=1 to n do

begin

for j:=0 to l[m+1]-1 do

begin

if ((j>=l[m-1])and(j<l[m]))or(((j and (1 shl 0))=0)and(j and (1 shl 1)<>0)) then b[i,j]:=false else

for k:=1 to m do

if (j and (a[i,k] shl (k-1))=0)and(a[i,k]=1) then b[i,j]:=false;

if b[i,j] then

for k:=1 to m-2 do

if (j and(1 shl (k-1))=0)and(j and(1 shl (k))<>0)and(j and(1 shl (k+1))=0) then

b[i,j]:=false;

end;

end;

for i:=1 to n do

if c[i]=l[n+1]-1 then b[i,-1]:=true else b[i,-1]:=false;

rec(0,0,0);

end;

procedure out;

begin

assign(output,'output.txt');

rewrite(output);

write(res-1);

close(output);

end;

begin init; solve; out; end.

переборзадачи

Задача 7 Значение выражения

Дано натуральное число m. Вставить между некоторыми цифрами 1,2,3,4,5,6,7,8,9 знаки + - так, чтобы значение получившегося выражения равнялось m.Если знаки расставить невозможно, вывести ‘no’.

program pastznak;

var t:array[2..9] of string; массив запомненных знаков

m,i:integer; m-заданное число

procedure sign(s,r:longint;op:char;n:integer);

var newr:longint; newr-текущая сумма

begin s-следующее слагаемое

r-текущая сумма

op -текущий знак

n-текущая цифра

if op='+' then newr:=r+s else newr:=r-s;

if n<=9 then

begin

t[n]:='+'; sign(n,newr,'+',n+1);

t[n]:='-'; sign(n,newr,'-',n+1);

t[n]:=''; sign(s*10+n,r,op,n+1);

end

else {проверка равенства}

if newr=m then

begin

for i:=2 to 9 do write(i-1,t[i]); вывод результата

writeln('9');

end;

end;

begin

assign(input,'input.txt');

reset(input);

assign(output,'output.txt');

rewrite(output);

read(m);

sign(1,0,'+',2);

close(input); close(output);

end.

переборзадачи

Задача 8 Последовательность

Последовательность 1001011001101001... строится так: сначала пишется 1, затем повторяется такое действие: уже написанную часть приписывают справа с заменой элемента 0 на 1 и наоборот, т.е. 1->10->1001->10010110->...

Требуется написать программу, вычисляющую n-ый член этой последовательности по заданному n<=2147483647.

Формат входных данных:

Входной файл Input.txt содержит натуральное число n.

Формат выходных данных:

В выходной файл Output.txt вывести найденную цифру.

Пример

Input.txt	Output.txt
6	1

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

var

n, p : longint;

t : byte;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(n);

if n>1073741824

then p:=1073741824

else

if n>536870912

then p:= 536870912

else

begin p:=1; while p<n do p:=p*2; p:=p div 2 end;

t:=0;

while n>1 do

begin

t:=1-t;

n:=n-p;

while p>=n do p:=p div 2

end;

write(1-t); close(output)

end.

переборзадачи

Задача 9 Конструктор

Недавно Пете подарили конструктор. В конструкторе N деталей. Детали пронумерованы от 1 до N. На каждой детали находятся разъемы; каждый разъем помечен латинской заглавной буквой. Все разъемы одной детали помечены разными буквами. Два разъема на разных деталях могут быть соединены, если они помечены одинаковыми буквами.

Пете надоело собирать детали в соответствии с инструкцией. Он решил выбрать K деталей конструктора и собрать из них свою конструкцию так, чтобы она удовлетворяла следующим требованиям:

• Все разъемы каждой использованной детали были соединены с разъемами других деталей.

• Число K должно быть максимально возможным.

Помогите Пете выбрать подходящие детали для сборки своей конструкции.