Euler Projesi 275. Soru

Dengeli Yapılar

n mertebeli dengeli bir yapıyı aşağıdaki şekilde tanımlayalım:

• Bloklardan (n adet karo) ve kaide (kalan karo) olarak bilinen n+1 karodan oluşan bir polyomino;
• kaidenin merkezi (x=0, y=0) konumunda;
• blokların ordinatları sıfırdan büyük (yani kaide en altta kalan tek karo);
• tüm karoların oluşturduğu şeklin kütle merkezi 0 apsislidir.

Yapıları sayarken sadece y-eksenine göre simetrik olanlar aynı kabul edilirler. Örneğin 6 mertebeli 18 dengeli yapı aşağıda gösterilmiştir. Y-eksenine göre simetrik olanların tek bir yapı olarak sayıldığına dikkat edin:

10 mertebeli 964 ve 15 mertebeli 360505 dengeli yapı bulunmaktadır.

18 mertebeli kaç dengeli yapı mevcuttur?
Cevap: 15030564 Python: def euler275b(n,holes,lenholes,tiles,i,m,low,high,H): if n==0: if m==0: a=tuple(sorted(tiles)) a2=tuple(sorted((-x,y) for x,y in a)) if a==a2: return 2 return 1 return 0 # Check centre of mass still attainable if m>0: if (low*n-n*(n-1)/2+m)>0: return 0 if m<0: if (high*n+n*(n-1)/2+m)<0: return 0 t=0 if i>=lenholes: return 0 h=holes[i] x,y=h if i<lenholes-1: low2,high2=low,high if x==low: low2=min(x for x,y in holes[i+1:lenholes]) if x==high: high2=max(x for x,y in holes[i+1:lenholes]) t=euler275b(n,holes,lenholes,tiles,i+1,m,low2,high2,H) tiles[n-1]=h m+=x H2=[] for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]: x2=x+dx y2=y+dy if y2<=0: continue h2=(x2,y2) if h2 in H: continue holes[lenholes]=h2 H.add(h2) H2.append(h2) lenholes+=1 low=min(x-1,low) high=max(x+1,high) t+=euler275b(n-1,holes,lenholes,tiles,i+1,m,low,high,H) for h2 in H2: H.remove(h2) return t holes=[0]*200 holes[0]=(0,1) N=18 tiles=[0]*N print euler275b(N,holes,1,tiles,0,0,-1,1,set([(0,1)]))//2 C/C++: #include <stdio.h> #include <math.h> #include <stdlib.h> #include <memory.h> #include <time.h> const long num=18; struct poly{char nt,c[num];long mom;}p[100000]; //poly: arrangement on one side of the plinth // nt: total number of tiles //c[i]: number of tiles in column i (counting away from plinth) // mom: total moment of the tiles about the plinth // arrangements are sorted by 'mom', then paired with others having the same 'mom'. long np=1,nz,cnt,max,flag;// max number of tiles on either side of the plinth char w[2*num+1], m[2*num+1][num], zx[100000], zy[100000]; // w[i]: number of tiles in column i (index of the plinth-column ='num') // m[i][j]: 1 if there is a tile in (i,j) _or_ -1 if adjacent to a tile. // zx[k]=i, zy[k]=j: when m[i][j]=-1 (stack of locations we can add a tile to). int comppoly(const void *a,const void *b){ if(((poly *)a)->mom > ((poly *)b)->mom)return 1; if(((poly *)a)->mom < ((poly *)b)->mom)return -1; return 0; } void put(long ind, long pre){ long i,j,k=nz,x,y; if(pre==num){ if(flag)for(j=0;j<num;j++){ for(i=1;i<num;i++) if(m[num+i][j]>0){if(m[num-i][j]<1)return;} else if(m[num-i][j]>0){j=num;break;} } cnt++; return; } for(i=ind;i<k;i++){ x=zx[i]; y=zy[i]; if(w[x]){ w[x]--; m[x][y]=1; if(w[x-1] && !m[x-1][y]){ zx[nz]=char(x-1); zy[nz++]=char(y); m[x-1][y]=-1; } if(w[x+1] && !m[x+1][y]){ zx[nz]=char(x+1); zy[nz++]=char(y); m[x+1][y]=-1; } if(y && w[x] && !m[x][y-1]){ zx[nz]=char(x); zy[nz++]=char(y-1); m[x][y-1]=-1; } if(w[x] && !m[x][y+1]){ zx[nz]=char(x); zy[nz++]=char(y+1); m[x][y+1]=-1; } put(i+1, pre+1); if(nz>k){ for(j=k;j<nz;j++)m[zx[j]][zy[j]]=0; nz=k; } w[x]++; m[x][y]=-1; } } } void make(long pos, poly *x){ long i,j,m=x->nt; for(i=1;i+m<=max;i++){ p[np].nt=char(m+i); for(j=0;j<pos;j++)p[np].c[j]=x->c[j]; p[np].c[j]=char(i); p[np++].mom=x->mom+i*(pos+1); if(m+i<max)make(pos+1,p+np-1); } } int main(){ double start=clock(); long i,j,k,tot=0; max=long(num-0.5*sqrt(1+8.*num)+0.6); make(0,p); qsort(p,np,sizeof(poly),comppoly); printf("%d sorted\n",np); for(i=0;i<np;i++)for(j=i;j<np && p[i].mom==p[j].mom;j++){ if(p[i].nt+p[j].nt<num){ memset(w,0,sizeof(w)); k=num-1; while(!p[i].c[k])k--; for(;k>=0;k--){w[num-k-1]=p[i].c[k];} w[num]=num-p[i].nt-p[j].nt; for(k=0;k<num && p[j].c[k];k++){w[num+k+1]=p[j].c[k];} flag=(i==j); cnt=0; zx[0]=num; zy[0]=0; nz=1; put(0,0); tot+=cnt; } }printf("n=%d, %d ",num,tot); printf("time %.3f sec\n",(clock() - start) / CLOCKS_PER_SEC); return 0; } ml: module IntSet = Set.Make (struct type t = int let compare = compare end) module Scene : sig type t val isplacable : t -> int -> bool val place : t -> int -> int -> t val init : int -> int array -> t val rev : t -> t val clear : int array array -> int -> int -> t -> unit val fold : (int -> int -> 'a -> 'a) -> t -> 'a -> 'a val to_string : t -> string val comp : t -> t -> int end = struct type t = IntSet.t * int array let dec target k = let arr = Array.copy target in arr.(k) <- arr.(k) - 1; arr let comb x y = x * 32 + y let isplacable (_, target) x = target.(x) > 0 let place (set, target) x y = if target.(x) <= 0 then failwith "illegal decrement." else IntSet.add (comb x y) set, dec target x let init offset target = place (IntSet.empty, target) offset 1 let fold f (sc, _) acc = IntSet.fold (fun xy acc2 -> let x = xy / 32 in let y = xy land 31 in f x y acc2) sc acc let rev ((set, target) as sc) = let t = Array.length target - 1 in fold (fun x y acc -> IntSet.add (comb (t - x) y) acc) sc IntSet.empty, target let clear arr w h (scxy, _) = for y = 0 to h - 1 do for x = 0 to w - 1 do arr.(y).(x) <- if y = 0 || x = 0 || y = h - 1 || x = w - 1 then 1 else 0 done done; IntSet.iter (fun xy -> let x = xy / 32 in let y = xy land 31 in arr.(y).(x) <- 1) scxy let to_string (t, _) = IntSet.fold (fun xy s -> s ^ Printf.sprintf "(%d,%d)" (xy / 32) (xy land 31)) t "" let comp (sa, _) (sb, _) = IntSet.compare sa sb end module SceneSet = Set.Make (struct type t = Scene.t let compare = Scene.comp end) module Container : sig type e = Scene.t type t val empty : t val add : bool -> e -> t -> t val count : t -> int val fold : (e -> 'a -> 'a) -> t -> 'a -> 'a val prt : t -> unit end = struct type e = Scene.t type t = SceneSet.t let empty = SceneSet.empty let add f e c = if f && SceneSet.mem (Scene.rev e) c then c else SceneSet.add e c let count c = SceneSet.cardinal c let fold = SceneSet.fold let prt c = SceneSet.iter (fun e -> print_endline (Scene.to_string e)) c end let main n = let initslot left center right = Array.of_list (0:: left @ [ center ] @ List.rev (0 :: right)) in let initarena y x = Array.create_matrix (y+2) (x+2) 0 in let calcpat offset target arena flag = let h = Array.length arena in let w = Array.length arena.(0) in let proc sc a = let check sc x y ac = if Scene.isplacable sc x && arena.(y).(x) = 0 then ( let _ = arena.(y).(x) <- 1 in Container.add flag (Scene.place sc x y) ac ) else ac in let proc2 sc x y a = let a = check sc (x-1) y a in let a = check sc (x+1) y a in let a = check sc x (y-1) a in check sc x (y+1) a in Scene.clear arena w h sc; Scene.fold (proc2 sc) sc a in let rec loop r cont = if r = 0 then ( Container.count cont ) else loop (r-1) (Container.fold proc cont Container.empty) in loop (n-1) (Container.add flag (Scene.init offset target) Container.empty) in let rec calc count = let rec calc2 ml fal a l2 count = (match l2 with | [] -> count | (mr, far, b) :: tl -> let count = if mr + ml + 1 <= n then let ct = n - mr - ml in let target = initslot a ct b in let arena = initarena n (fal+far+2) in count + calcpat (fal+1) target arena false else count in calc2 ml fal a tl count) in function | [] -> count | (ml, far, a) :: tl -> let count = if ml + ml + 1 <= n then let target = initslot a (n-ml*2) a in let arena = initarena n (far*2+2) in count + calcpat (far+1) target arena true else count in calc (calc2 ml far a tl count) tl in let tlim = let t = (n - 1) / 2 in t * (t + 1) / 2 + 1 in let rec loop1 r c w l acc arr = if r < c then arr else let nw = w + l * c in if nw > tlim then arr else let arr = loop1 r (c+1) w l acc arr in let acc = c :: acc in loop1 (r-c) 1 nw (l+1) acc (arr.(nw)<-(n - r + c, l, acc) :: arr.(nw); arr) in let arr = loop1 n 1 0 1 [] (Array.create (tlim + 1) []) in Array.fold_left calc 1 arr ;; Printf.printf "Answer: %d\n" (main (int_of_string Sys.argv.(1)))