2x1 ve 3x1 (yatayxdikey) boyutlu tuğlalardan daha güçlü olması için herhangi bir sıradaki tuğlalar arası boşluk ile alt yada üst sıradaki boşlukların çakışmadığı (çakışması durumuna "sürekli çatlak" denir) bir duvar örülecek.
Örneğin, aşağıdaki 9x3 duvar kırmızı ile gösterilen sürekli çatlaktan dolayı kabul edilemez.
"Sürekli çatlak" bulunmayan 9x3 boyutunda 8 farklı duvar yapımı mümkündür. Bunu W(9,3)=8 ile gösterelim.
Bu durumda W(32,10) değeri kaçtır?
Cevap: 806844323190414
C++:
#include <stdio.h>
#include <stdlib.h>
#define height 10
#define width 32
int main() {
int i,j,k,np=0,*brick,pow2,ch=0,found[width+1];
int offset,offset2,s1,s2,good;
long long int *dp,*temp,sum;
pow2=1<<(width/2);
brick=(int*)(malloc)(pow2*sizeof(int));
for(i=0;i<pow2;i++) {
j=i;
sum=0;
while(sum<width) {
if(j&1) sum+=2;
else sum+=3;
j>>=1;
}
if((sum==width)&&(j==0)) {
brick[np]=i;
np++;
}
}
dp=(long long int*)(malloc)(np*sizeof(long long int));
temp=(long long int*)(malloc)(np*sizeof(long long int));
for(i=0;i<np;i++) dp[i]=1;
for(i=0;i<=width;i++) found[i]=-1;
for(i=1;i<height;i++) {
for(j=0;j<np;j++) temp[j]=dp[j],dp[j]=0;
for(j=0;j<np;j++) {
for(k=0;k<np;k++) {
offset=brick[j];
offset2=brick[k];
s1=0,s2=0;
ch++;
while(s1<width) {
if(offset&1) s1+=2;
else s1+=3;
found[s1]=ch;
offset>>=1;
}
good=1;
while(s2<width) {
if(offset2&1) s2+=2;
else s2+=3;
if((s2<width)&&(found[s2]==ch)) {
good=0;
break;
}
offset2>>=1;
}
if(good) dp[j]+=temp[k];
}}}
sum=0;
for(i=0;i<np;i++) sum+=dp[i];
printf("%I64d\n",sum);
return 0;
}import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collection;
/**
*
* @author fra
*/
public class Problem215{
/**
* Generates all combinations of a row of 2x1, 3x1 bricks starting from position pos
* @param r the row of bricks up to now
* @param rows stores all rows
* @param pos up to where the row has been generated
* @param n the length of the row
*/
public static final void generateRows(BitSet r, Collection<BitSet> rows, int pos, int n){
//Last brick
if(pos >= n-4){
if(pos == n-4 || pos == n-3){
rows.add(r);
}
return;
}
//Adds a 2x1 brick
BitSet r2 = (BitSet) r.clone();
r2.set(pos+2);
generateRows(r2, rows, pos+2,n);
//Adds a 3x1 brick
BitSet r3 = (BitSet) r.clone();
r3.set(pos+3);
generateRows(r3, rows, pos+3,n);
return;
}
/**
* Calculates the possible arrangements of 2x1, 3x1 bricks
* @param n length of the row
* @param m number of rows
* @return the possible arrangements of bricks
*/
public static final long w(int n, int m) {
BitSet cracks = new BitSet(n-1);
ArrayList<BitSet> rows = new ArrayList<BitSet>();
long[] swap;
generateRows(cracks, rows, -1,n);
//Checks which rows can be connected
boolean[][] canConnect = new boolean[rows.size()][rows.size()];
for (int i = 0; i < rows.size(); i++) {
for (int j = 0; j <= i; j++) {
canConnect[i][j] = ! rows.get(i).intersects(rows.get(j));
canConnect[j][i] = canConnect[i][j];
}
}
//First row can be any
long[] c = new long[rows.size()];
Arrays.fill(c, 1);
long[] nc = new long[rows.size()];
//Adds a second row
for (int i = 1; i < m; i++) {
Arrays.fill(nc, 0);
for (int j = 0; j < nc.length; j++) {
for (int k = 0; k < nc.length; k++) {
if(canConnect[j][k])
nc[k] += c[j];
}
}
//Prepares for next row
swap = c;
c = nc;
nc = swap;
}
//Sums up the result
long sum =0;
for (long l : c) sum += l;
return sum;
}
public static final void main(String args[]){
int n = 32;
int m = 10;
System.out.println("W(" + n + "," + m +") = " + w(n,m));
}
}
function pe_215
N=32;
P=10;
% list of all walls
L=generate_walls({[]},N);
% easier representation
M=zeros(numel(L),N);
for k=1:numel(L)
M(k,cumsum(L{k}))=1;
end;
% store possible children (fitting walls)
for k=1:numel(L)
idx=M*(M(k,:)');
L{k}=find(idx==1);
end;
L=[L {1:numel(L)}];
% at each stage, replace each node by their children
% (number thereof, actually)
idx=zeros(1,numel(L)); %number of each wall used at a particular stage
idx(end)=1;
for p=1:P
idx2=zeros(1,numel(L));
for k=1:numel(L)
idx2(L{k})=idx2(L{k})+idx(k);
end;
idx=idx2;
end;
%result
int2str(sum(idx))
function L2=generate_walls(L,n)
L2={};
for k=1:numel(L)
s=sum(L{k});
switch s
case n,
L2=[L2 L{k}];
case n-1
%impossible
case n-2
L2=[L2 [L{k} 2]];
case n-3
L2=[L2 [L{k} 3]];
otherwise
L2=[L2 generate_walls({[L{k} 2]},n)];
L2=[L2 generate_walls({[L{k} 3]},n)];
end;
end; > hmwt:=proc(n,t)
> option remember;
> local T,i;
> if n=0 then return [0] fi;
> if n<=1 or member(n,t) then return false fi;
> T:=NULL;
> if hmwt(n-2,t)<>false then for i in hmwt(n-2,t) do T:=T,[n-2,i[]] od fi;
> if hmwt(n-3,t)<>false then for i in hmwt(n-3,t) do T:=T,[n-3,i[]] od fi;
> [T];
> end:
>
> tot:=proc(n,m,t)
> option remember;
> if m=0 then return 1 fi;
> add(tot(n,m-1,y),y in hmwt(n,t));
> end:
>
> tot(9,3,[NULL]);
8
> tot(32,10,[NULL]);
806844323190414
k = 32;
n = 10;
ClearAll[tiles]
tiles[0] := {{}}
tiles[1] := {}
tiles[2] := {{2}}
tiles[3] := {{3}}
addtile[s_, v_] := Map[Sort[Append[#, Last[#] + v]] &, s]
tiles[n_] /; n > 3 :=
tiles[n] = Union[addtile[tiles[n - 2], 2], addtile[tiles[n - 3], 3]]
tobinary[s_] := Total[Map[2^(# - 2) &, s]]
v = tobinary /@ Most /@ tiles[k];
m = Length[v]
c = Table[Boole[BitAnd[v[[i]], v[[j]]] == 0], {i, m}, {j, m}];
Total[Nest[c.# &, ConstantArray[1, m], n - 1]]Delphi:
{----------------------------------------------------------------------}
Procedure Pb215;
Var T: Array of String[32]; nl,nb: Byte; i: Integer; s: Int64; sl: Tstringlist; w: TPtrInt64;
{===== ==== ==== ==== ==== ====}
Procedure FillWall(const zl, zll: Byte; Var zs: Int64);
Var b,wll: Byte; wzs: Int64; wzi: Integer; w1,w2: TPtrInt64;
Begin
For b := 2 to 3 Do Begin
wll := zll+b;
If (wll = nb) Then begin
If (zl = nl) Then
inc(zs)
Else
If sl.find(Inttostr(zl)+Copy(T[zl],1,nb),wzi) then Begin
w1 := Pointer(sL.Objects[wzi]); zs := zs + w1.N;
End
Else Begin
wzs := 0; FillWall(zl+1, 0, wzs); zs := zs + wzs;
w2 := New(TPtrInt64); w2.N := wzs; sl.addobject(Inttostr(zl)+Copy(T[zl],1,nb),Pointer(w2));
End;
End
Else
If (wll <> nb-1) And (T[zl-1][wll] = 'N') Then Begin
T[zl][wll] := 'O'; FillWall(zl, wll, zs); T[zl][wll] := 'N';
End;
End;
End;
{===== ==== ==== ==== ==== ====}
Begin
nl := 10; nb := 32;
sl := Tstringlist.Create; sl.Sorted := True;
Setlength(T, nl+1);
For i := 0 to nl Do Begin
T[i] := 'NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN'; T[i][nb+1] := 'O'; T[i][nb+2] := 'O';
End;
Try
s := 0; FillWall(1,0,s); mmo_res := Inttostr(s);
Finally
Setlength(T, 0);
For i := 0 to sl.count-1 do
If sl.Objects[i] <> NIL Then Begin
w := Pointer(sl.Objects[i]); Dispose(w); sl.Objects[i] := NIL;
End;
sl.free;
End;
End;