Дырокол
PUNCHER
Условие Комментарии Решение Тестовые файлы Оглавление
Описание
Квадратный клетчатый лист бумаги размерами 2N×2N клеток начинают складывать следующим образом: сначала нижняя половина листа накладывается на верхнюю, а затем правая половина листа накладывается на его левую части. Эту операцию повторяют N-3 раза, в результате чего получается сложенный лист 8×8 клеток. Какие-то из клеток, сложенного таким образом листа, удаляются при помощи дырокола
После развертывания исходный лист распадется на некоторое количество связных частей, т.е. таких множеств клеток, что из любой клетки одного множества можно пройти по любой другой, переходя каждый раз на соседнюю по вертикали или горизонтали клетку.
Задача
Напишите программу, вычисляющую число частей, на которые распадется лист
Входные данные
Первая строка входного файла содержит целое число N (4
N500). В следующих S строках записана матрица 8х8 из нулей и единиц, разделенных пробелом. Единицами отмечены клетки, выкалываемые дыроколом из сложенного листа 8x8Выходные данные
Вывести в выходной файл искомое число частей
Например:
PUNCHER.IN
4
0 1 0 0 0 0 1 0
1 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
PUNCHER.OUT
11
Идеи
Динамическое программирование, длинная арифметика
Комментарии
Каждую связную область сложенного листа (если смотреть на него сверху) закодируем двоичным числом b3b2b1b0. А именно, положим b0 равным единице, если эта область примыкает к нижней границе листа, и нулю в противном случае. Числа b1, b2 и b3 определим аналогичным образом для верхней, правой и левой границ листа соответственно. Тем самым, все области разбиваются на 16 типов в соответствии с их кодами. Теперь проанализируем, что происходит с областями при развертывании листа
Рассмотрит например, разгибание относительно нижней стороны. Легко заметить, что связная область типа b3b2b11 перейдет в связную область типа b3b2b1b1 (действительно, будет ли она прилегать К нижнему краю после разгибания зависит от того, прилегала ли ока к верхнему краю листа до разгибания). Связная область типа b3b2b10 после разгибания распадется на две. Одна из них будет иметь тот же тип b3b2b10, а другая - b3b20b1. Аналогично анализируется разгибание листа относительно правой стороны
Для решения задачи проделываем 2·N разгибаний, обратных произведенным при складывании листа сгибаниям. При этом на каждое шаге пересчитываем количество связных областей каждого из типов
Решение
{$A+,B-,D+,E-,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
Program puncher;
Const Size=8;
Var N:Integer;
A:Array[1..Size,1..Size] of Boolean;
Procedure Init;
Var i,j,k:Integer;
Begin
Read(N);
For i:=1 to Size do
For j:=1 to Size do
Begin
Read(K);
A[i,j]:=K=1;
End;
End(*Init*);
Const P=10000;
Len=100;
St=4;
Type O=Array[0..Len] of Integer;
Procedure Incr(Var A:O;B:O);
Var i,R,E:Integer;
K:LongInt;
T:O;
Begin
E:=B[0];
If A[0]>=B[0] then
E:=A[0];
R:=0;
For i:=1 to E do
Begin
K:=A[i];
A[i]:=(K+B[i]+R) mod P;
R:=(K+B[i]+R) div P;
End;
A[0]:=E;
If R>0 then
Begin
Inc(A[0]);
A[A[0]]:=R;
End;
End(*Incr*);
Var Part,Part1:Array[Boolean,Boolean,Boolean,Boolean] of O;
Is:Array[1..4] of Boolean;
Procedure Rec(i,j:Integer);
Begin
If (i<1) or (i>Size) or (j<1) or (j>Size) or A[i,j] then
Exit;
A[i,j]:=True;
If i=1 then
Is[2]:=True;
If j=1 then
Is[1]:=True;
If i=Size then
Is[4]:=True;
If j=SIze then
Is[3]:=True;
Rec(i+1,j);
Rec(i-1,j);
Rec(i,j+1);
Rec(i,j-1);
End(*Rec*);
Procedure Inc(Var A:O);
Var B:O;
Begin
FillChar(B,SizeOf(B),0);
B[0]:=1;
B[1]:=1;
Incr(A,B);
End(*Inc*);
Procedure InitPart;
Var i,j:Integer;
Begin
FillChar(Part,SizeOf(Part),0);
For i:=1 to Size do
For j:=1 to Size do
If Not A[i,j] then
Begin
FillChar(Is,SizeOf(Is),False);
Rec(i,j);
Inc(Part[Is[1],Is[2],Is[3],Is[4]]);
End;
End(*InitPart*);
Procedure Calc(B1,B2,B3,B4:Boolean);
Begin
Case B3 of
True:Case B4 of
True:Incr(Part[B1,B2,B1,B2],Part1[B1,B2,B3,B4]);
False:Begin
Incr(Part[B1,False,B1,B2],Part1[B1,B2,B3,B4]);
Incr(Part[B1,B2,B1,False],Part1[B1,B2,B3,B4]);
End;
End;
False:Case B4 of
True:Begin
Incr(Part[B1,B2,False,B2],Part1[B1,B2,B3,B4]);
Incr(Part[False,B2,B1,B2],Part1[B1,B2,B3,B4]);
End;
False:Begin
Incr(Part[B1,B2,False,False],Part1[B1,B2,B3,B4]);
Incr(Part[B1,False,False,B2],Part1[B1,B2,B3,B4]);
Incr(Part[False,B2,B1,False],Part1[B1,B2,B3,B4]);
Incr(Part[False,False,B1,B2],Part1[B1,B2,B3,B4]);
End;
End;
End;
End(*Calc*);
Procedure Solve;
Var i:Integer;
Begin
InitPart;
For i:=1 to N-3 do
Begin
Part1:=Part;
FillChar(Part,SizeOf(Part),0);
For Is[1]:=False to True do
For Is[2]:=False to True do
For Is[3]:=False to True do
For Is[4]:=False to True do
If Not((Part1[Is[1],Is[2],Is[3],Is[4],0]=0) or
(Part1[Is[1],Is[2],Is[3],Is[4],0]=1) and
(Part1[Is[1],Is[2],Is[3],Is[4],1]=0)) then
Calc(Is[1],Is[2],Is[3],Is[4]);
End;
End(*Solve*);
Procedure Print(A:O);
Var i:Integer;
S:String;
Begin
Write(A[A[0]]);
For i:=A[0]-1 downto 1 do
Begin
Str(A[i],S);
While Length(S)
S:='0'+S;
Write(S);
End;
End(*Print*);
Procedure Done;
Var Sum:O;
Begin
FillChar(Sum,SizeOf(Sum),0);
For Is[1]:=False to True do
For Is[2]:=False to True do
For Is[3]:=False to True do
For Is[4]:=False to True do
Incr(Sum,Part[Is[1],Is[2],Is[3],Is[4]]);
Print(Sum);
WriteLn;
End(*Done*);
Procedure Initialize;
Begin
Assign(Input,'puncher.in');
ReSet(Input);
Assign(Output,'puncher.out');
ReWrite(Output);
End(*Initialize*);
Procedure DoneAll;
Begin
Close(Input);
Close(Output);
End(*DoneAll*);
BEGIN
Initialize;
While not SeekEof do
Begin
Init;
Solve;
Done;
End;
DoneAll;
END.
© Особенности национальных задач по информатике