{ (x0,y0,z0), (dx,dy,dz) } parametreleri ile belirlenen bir eksen-hizalı küboid, x0 ≤ X ≤ x0+dx, y0 ≤ Y ≤ y0+dy ve z0 ≤ Z ≤ z0+dz olacak biçimde (X,Y,Z) noktalarından oluşur. Küboidin hacmi dx × dy × dz dir. Bir küboid kümesinin birleşik hacmi bu küboidlerin birleşimlerinin hacmi olup ayrık birleşimleri hacminden azdır.
Cn küboidinin parametreleri
x0 = S6n-5 mod 10000
y0 = S6n-4 mod 10000
z0 = S6n-3 mod 10000
dx = 1 + (S6n-2 mod 399)
dy = 1 + (S6n-1 mod 399)
dz = 1 + (S6n mod 399)
olmak üzere C1,...,C50000 eksen-hizalı 50000 küboid kümesi verilsin.y0 = S6n-4 mod 10000
z0 = S6n-3 mod 10000
dx = 1 + (S6n-2 mod 399)
dy = 1 + (S6n-1 mod 399)
dz = 1 + (S6n mod 399)
Burada S1,...,S300000 ifadeleri "Gecikmeli Fibonacci Üreteci" dir:
For 1 ≤ k ≤ 55, Sk = [100003 - 200003k + 300007k3] (mod 1000000)
For 56 ≤ k, Sk = [Sk-24 + Sk-55] (mod 1000000).
Yani, C1 küboidinin parametreleri {(7,53,183),(94,369,56)}, C2 küboidinin parametreleri {(2383,3563,5079),(42,212,344)}, vb.For 56 ≤ k, Sk = [Sk-24 + Sk-55] (mod 1000000).
İlk 100 küboid (C1,...,C100) kümesinin birleşik hacmi 723581599 dir.
Bu durumda C1,...,C50000 küboid kümesinin birleşik hacmi kaçtır?
Cevap: 328968937309
C++:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int MAX(int x,int y) {
if(x<y) return y;
return x;
}
int MIN(int x,int y) {
if(x<y) return x;
return y;
}
int main() {
double dtime=clock();
int *S,*x0,*y0,*z0,*dx,*dy,*dz,k,n,*ct,**perm;
int a1,a2,a3,R,x,y,z,count,fx,fy,fz,lx,ly,lz;
int *X1,*X2,*Y1,*Y2,*Z1,*Z2,*parity,w,r1,r2,r3,i,p,all,all2;
int xx1,xx2,yy1,yy2,zz1,zz2,xxx1,xxx2,yyy1,yyy2,zzz1,zzz2;
int x1[32],x2[32],y1[32],y2[32],z1[32],z2[32],F=50000;
long long int K,res,vol;
S=(int*)(malloc)(300001*sizeof(int));
x0=(int*)(malloc)(50001*sizeof(int));
y0=(int*)(malloc)(50001*sizeof(int));
z0=(int*)(malloc)(50001*sizeof(int));
dx=(int*)(malloc)(50001*sizeof(int));
dy=(int*)(malloc)(50001*sizeof(int));
dz=(int*)(malloc)(50001*sizeof(int));
X1=(int*)(malloc)(100000*sizeof(int));
X2=(int*)(malloc)(100000*sizeof(int));
Y1=(int*)(malloc)(100000*sizeof(int));
Y2=(int*)(malloc)(100000*sizeof(int));
Z1=(int*)(malloc)(100000*sizeof(int));
Z2=(int*)(malloc)(100000*sizeof(int));
parity=(int*)(malloc)(100000*sizeof(int));
ct=(int*)(malloc)(17576*sizeof(int));
perm=(int**)(malloc)(17576*sizeof(int));
for(k=1;k<=55;k++) {
K=k;
res=100003-200003*K+300007*K*K*K;
res%=1000000;
S[k]=res;
}
for(k=56;k<=300000;k++)
S[k]=(S[k-24]+S[k-55])%1000000;
for(n=1;n<=50000;n++) {
x0[n]=S[6*n-5]%10000;
y0[n]=S[6*n-4]%10000;
z0[n]=S[6*n-3]%10000;
dx[n]=1+(S[6*n-2]%399);
dy[n]=1+(S[6*n-1]%399);
dz[n]=1+(S[6*n]%399);
}
for(n=0;n<17576;n++) ct[n]=0;
for(n=1;n<=F;n++) {
R=(x0[n]/400)*676+(y0[n]/400)*26+(z0[n]/400);
x=x0[n]/400;
if(x0[n]+dx[n]>=400*(x+1)) a1=1;
else a1=0;
y=y0[n]/400;
if(y0[n]+dy[n]>=400*(y+1)) a2=1;
else a2=0;
z=z0[n]/400;
if(z0[n]+dz[n]>=400*(z+1)) a3=1;
else a3=0;
ct[R]++;
if(a1) ct[R+676]++;
if(a2) ct[R+26]++;
if(a3) ct[R+1]++;
if(a1+a2==2) ct[R+676+26]++;
if(a2+a3==2) ct[R+26+1]++;
if(a3+a1==2) ct[R+1+676]++;
if(a1+a2+a3==3) ct[R+676+26+1]++;
}
for(n=0;n<17576;n++) perm[n]=(int*)(malloc)(ct[n]*sizeof(int*));
for(n=0;n<17576;n++) ct[n]=0;
for(n=1;n<=F;n++) {
R=(x0[n]/400)*676+(y0[n]/400)*26+(z0[n]/400);
x=x0[n]/400;
if(x0[n]+dx[n]>=400*(x+1)) a1=1;
else a1=0;
y=y0[n]/400;
if(y0[n]+dy[n]>=400*(y+1)) a2=1;
else a2=0;
z=z0[n]/400;
if(z0[n]+dz[n]>=400*(z+1)) a3=1;
else a3=0;
w=R,perm[w][ct[w]]=n,ct[w]++;
if(a1) w=R+676,perm[w][ct[w]]=n,ct[w]++;
if(a2) w=R+26,perm[w][ct[w]]=n,ct[w]++;
if(a3) w=R+1,perm[w][ct[w]]=n,ct[w]++;
if(a1+a2==2) w=R+676+26,perm[w][ct[w]]=n,ct[w]++;
if(a2+a3==2) w=R+26+1,perm[w][ct[w]]=n,ct[w]++;
if(a3+a1==2) w=R+1+676,perm[w][ct[w]]=n,ct[w]++;
if(a1+a2+a3==3) w=R+676+26+1,perm[w][ct[w]]=n,ct[w]++;
}
vol=0;
for(n=0;n<17576;n++) {
r1=n/676;
r2=(n/26)%26;
r3=n%26;
fx=r1*400;
lx=fx+400;
fy=r2*400;
ly=fy+400;
fz=r3*400;
lz=fz+400;
count=ct[n];
for(i=0;i<count;i++) {
p=perm[n][i];
x1[i]=MAX(fx,x0[p]);
x2[i]=MIN(lx,x0[p]+dx[p]);
y1[i]=MAX(fy,y0[p]);
y2[i]=MIN(ly,y0[p]+dy[p]);
z1[i]=MAX(fz,z0[p]);
z2[i]=MIN(lz,z0[p]+dz[p]);
}
X1[0]=fx;
X2[0]=lx;
Y1[0]=fy;
Y2[0]=ly;
Z1[0]=fz;
Z2[0]=lz;
parity[0]=0;
all=1;
for(i=0;i<count;i++) {
all2=all;
xxx1=x1[i],xxx2=x2[i];
yyy1=y1[i],yyy2=y2[i];
zzz1=z1[i],zzz2=z2[i];
for(k=0;k<all;k++) {
xx1=MAX(X1[k],xxx1);
xx2=MIN(X2[k],xxx2);
yy1=MAX(Y1[k],yyy1);
yy2=MIN(Y2[k],yyy2);
zz1=MAX(Z1[k],zzz1);
zz2=MIN(Z2[k],zzz2);
if((xx1<xx2)&&(yy1<yy2)&&(zz1<zz2)) {
X1[all2]=xx1;
X2[all2]=xx2;
Y1[all2]=yy1;
Y2[all2]=yy2;
Z1[all2]=zz1;
Z2[all2]=zz2;
parity[all2]=1-parity[k];
if(parity[all2]) vol+=(xx2-xx1)*(yy2-yy1)*(zz2-zz1);
else vol-=(xx2-xx1)*(yy2-yy1)*(zz2-zz1);
all2++;
}
}
all=all2;
}
}
printf("volume=%I64d, time=%.3lf sec.\n",vol,(double) (clock()-dtime)/CLOCKS_PER_SEC);
return 0;
} Java:import java.util.ArrayList;
import java.util.List;
public class Euler212 {
private class Cuboid
{
public int x1,x2,y1,y2,z1,z2;
public long volume(){
return (long)(x2-x1)*(y2-y1)*(z2-z1);
}
public Cuboid intersect( Cuboid c2 ){
if( x2<=c2.x1 || c2.x2<= x1 ) return null;
if( y2<=c2.y1 || c2.y2<= y1 ) return null;
if( z2<=c2.z1 || c2.z2<= z1 ) return null;
Cuboid c3 = new Cuboid();
c3.x1 = Math.max( x1, c2.x1 );
c3.y1 = Math.max( y1, c2.y1 );
c3.z1 = Math.max( z1, c2.z1 );
c3.x2 = Math.min( x2, c2.x2 );
c3.y2 = Math.min( y2, c2.y2 );
c3.z2 = Math.min( z2, c2.z2 );
return c3;
}
}
FibGenerator fib = new FibGenerator();
public Cuboid getNext(){
Cuboid c = new Cuboid();
c.x1 = fib.get() % 10000;
c.y1 = fib.get() % 10000;
c.z1 = fib.get() % 10000;
c.x2 = fib.get() % 399 + c.x1 + 1;
c.y2 = fib.get() % 399 + c.y1 + 1;
c.z2 = fib.get() % 399 + c.z1 + 1;
return c;
}
Euler212(){
List<Cuboid> cubadd = new ArrayList<Cuboid>();
List<Cuboid> cubsub = new ArrayList<Cuboid>();
List<Cuboid> newcubadd = new ArrayList<Cuboid>();
List<Cuboid> newcubsub = new ArrayList<Cuboid>();
int size = 50000;
for( int n=0; n<size; n++ ){
Cuboid c = getNext();
newcubadd.clear();
newcubsub.clear();
newcubadd.add(c);
for (Cuboid c2 : cubadd) {
Cuboid c3 = c.intersect(c2);
if( c3!=null ) newcubsub.add(c3);
}
for (Cuboid c2 : cubsub) {
Cuboid c3 = c.intersect(c2);
if( c3!=null ) newcubadd.add(c3);
}
cubadd.addAll(newcubadd);
cubsub.addAll(newcubsub);
}
long volume = 0;
for (Cuboid c2 : cubadd) volume += c2.volume();
for (Cuboid c2 : cubsub) volume -= c2.volume();
System.out.println("vol:"+volume);
}
} Pascal:program problem212;
uses crt;
const limit=50000;
type cuboid = record
x, y, z, dx, dy, dz: longint;
end;
var S:array[1..300000] of longint;
a:array[1..50000] of cuboid;
i,k:longint;
volume:int64;
procedure f(sign, x, y, z, dx, dy, dz, i: longint);
var x1, y1, z1, dx1, dy1, dz1, j: longint;
begin
if a[i].x>=x then begin
x1:=a[i].x;
if a[i].x+a[i].dx>=x+dx then dx1:=x+dx-a[i].x
else dx1:=a[i].dx;
end
else begin
x1:=x;
if x+dx>=a[i].x+a[i].dx then dx1:=a[i].x+a[i].dx-x
else dx1:=dx;
end;
if dx1<=0 then exit;
if a[i].y>=y then begin
y1:=a[i].y;
if a[i].y+a[i].dy>=y+dy then dy1:=y+dy-a[i].y
else dy1:=a[i].dy;
end
else begin
y1:=y;
if y+dy>=a[i].y+a[i].dy then dy1:=a[i].y+a[i].dy-y
else dy1:=dy;
end;
if dy1<=0 then exit;
if a[i].z>=z then begin
z1:=a[i].z;
if a[i].z+a[i].dz>=z+dz then dz1:=z+dz-a[i].z
else dz1:=a[i].dz;
end
else begin
z1:=z;
if z+dz>=a[i].z+a[i].dz then dz1:=a[i].z+a[i].dz-z
else dz1:=dz;
end;
if dz1<=0 then exit;
volume:=volume + sign*dx1*dy1*dz1;
for j:=i+1 to limit do f(-sign, x1, y1, z1, dx1, dy1, dz1, j);
end;
begin
clrscr;
for k:=1 to 55 do S[k]:=(100003 - (200003*k) mod 1000000
+ ((300007*k*k) mod 1000000)*k) mod 1000000;
for k:=56 to 300000 do S[k]:=(S[k-24]+S[k-55]) mod 1000000;
i:=0;
for k:=1 to 50000 do begin
i:=i+1;
a[k].x:=S[i] mod 10000;
i:=i+1;
a[k].y:=S[i] mod 10000;
i:=i+1;
a[k].z:=S[i] mod 10000;
i:=i+1;
a[k].dx:=1 + S[i] mod 399;
i:=i+1;
a[k].dy:=1 + S[i] mod 399;
i:=i+1;
a[k].dz:=1 + S[i] mod 399;
end;
volume:=0;
for i:=1 to limit do volume:=volume+a[i].dx*a[i].dy*a[i].dz;
for i:=1 to limit-1 do
for k:=i+1 to limit do f(-1, a[i].x, a[i].y, a[i].z, a[i].dx, a[i].dy, a[i].dz, k);
writeln(volume);
readkey;
end. Delphi:Procedure Pb212;
Var n,i,j,l,m,x,y,z: integer; k,v: Int64; t: array of Int64; sl: Tstringlist; p: array of smallint; s : String;
Begin
v := 0; Setlength(t,300001); Setlength(p,10400*10400); SL := Tstringlist.create;
try
For n := 1 to 300000 do Begin
k := n;
if k < 56
Then t[k] := (100003-200003*k+300007*k*k*k) mod 1000000
Else t[k] := (t[k-24]+t[k-55]) mod 1000000;
End;
For n := 1 to 50000
do For i := 0 to t[6*n-2] mod 399
Do Sl.add(NumStrPad((t[6*n-5] mod 10000)+i,5)+
NumStrPad(t[6*n-4] mod 10000,5)+NumStrPad(t[6*n-1] mod 399,3)+
NumStrPad(t[6*n-3] mod 10000,5)+NumStrPad(t[6*n ] mod 399,3));
Sl.sort;
For i := 0 to 10399 do For j := 0 to 10399 do p[10400*i+j] := -1;
For n := 0 to Sl.count-1 do Begin
s := Sl[n]; x := Strtoint(Copy(s,1,5)); y := Strtoint(Copy(s,6,5)); z := Strtoint(Copy(s,14,5)); m := Strtoint(Copy(s,19,3));
For i := 0 to Strtoint(Copy(s,11,3)) Do Begin
l := 10400*(y+i)+z;
For j := 0 to m
Do If (p[l+j] < x) then begin p[l+j] := x; v := v + 1; End;
End;
End;
mmo_res := Inttostr(v);
Finally
Setlength(t,0); Setlength(p,0); sl.Free;
End;
End; VB:Public Shared Function Problem212() As String
Const cuboidcount = 50000
Dim prevnumbers(0 To 54) As Integer, previndex = 0
Dim volume = 0L
Dim cuboids(25, 25, 25) As List(Of Cuboid)
For i = 0 To 25
For j = 0 To 25
For k = 0 To 25
cuboids(i, j, k) = New List(Of Cuboid)
Next
Next
Next
For i = 1 To cuboidcount
Dim rnums(5) As Integer
For k = 6 * i - 5 To 6 * i
Dim r As Long
If k <= 55 Then
r = (100003L - 200003L * k + 300007L * k * k * k) Mod 1000000
Else
r = (prevnumbers((previndex + 55 - 24) Mod 55) + prevnumbers(previndex)) Mod 1000000
End If
rnums(k - 6 * i + 5) = CInt(r)
prevnumbers(previndex) = CInt(r)
previndex = (previndex + 1) Mod 55
Next
Dim newcub As Cuboid
newcub.X0 = rnums(0) Mod 10000
newcub.Y0 = rnums(1) Mod 10000
newcub.Z0 = rnums(2) Mod 10000
newcub.X1 = newcub.X0 + 1 + (rnums(3) Mod 399)
newcub.Y1 = newcub.Y0 + 1 + (rnums(4) Mod 399)
newcub.Z1 = newcub.Z0 + 1 + (rnums(5) Mod 399)
Dim xindex = newcub.X0 \ 400, yindex = newcub.Y0 \ 400, zindex = newcub.Z0 \ 400
Dim newlist = CheckCuboidAgainstCollection(cuboids, newcub,
Math.Max(xindex - 1, 0), Math.Min(xindex + 1, 25),
Math.Max(yindex - 1, 0), Math.Min(yindex + 1, 25),
Math.Max(zindex - 1, 0), Math.Min(zindex + 1, 25))
For Each cub In newlist
volume += cub.GetVolume
cuboids(cub.X0 \ 400, cub.Y0 \ 400, cub.Z0 \ 400).Add(cub)
Next
Next
Return volume.ToString
End Function
Private Shared Function CheckCuboidAgainstCollection(cuboids(,,) As List(Of Cuboid),
newcub As Cuboid, xmin As Integer, xmax As Integer,
ymin As Integer, ymax As Integer,
zmin As Integer, zmax As Integer) As List(Of Cuboid)
Dim extracuboids As New List(Of Cuboid)
For x = xmin To xmax
For y = ymin To ymax
For z = zmin To zmax
For Each oldcub In cuboids(x, y, z)
If oldcub.Overlaps(newcub) Then
If newcub.X0 < oldcub.X0 Then '' split off lower part
Dim l = CheckCuboidAgainstCollection(cuboids,
New Cuboid(newcub.X0, oldcub.X0, newcub.Y0, newcub.Y1, newcub.Z0, newcub.Z1),
x, xmax, ymin, ymax, zmin, zmax)
extracuboids.AddRange(l)
newcub.X0 = oldcub.X0
End If
If newcub.X1 > oldcub.X1 Then '' split off upper part
Dim l = CheckCuboidAgainstCollection(cuboids,
New Cuboid(oldcub.X1, newcub.X1, newcub.Y0, newcub.Y1, newcub.Z0, newcub.Z1),
x, xmax, ymin, ymax, zmin, zmax)
extracuboids.AddRange(l)
newcub.X1 = oldcub.X1
End If
If newcub.Y0 < oldcub.Y0 Then '' split off lower part
Dim l = CheckCuboidAgainstCollection(cuboids,
New Cuboid(newcub.X0, newcub.X1, newcub.Y0, oldcub.Y0, newcub.Z0, newcub.Z1),
x, xmax, ymin, ymax, zmin, zmax)
extracuboids.AddRange(l)
newcub.Y0 = oldcub.Y0
End If
If newcub.Y1 > oldcub.Y1 Then '' split off upper part
Dim l = CheckCuboidAgainstCollection(cuboids,
New Cuboid(newcub.X0, newcub.X1, oldcub.Y1, newcub.Y1, newcub.Z0, newcub.Z1),
x, xmax, ymin, ymax, zmin, zmax)
extracuboids.AddRange(l)
newcub.Y1 = oldcub.Y1
End If
If newcub.Z0 < oldcub.Z0 Then '' split off lower part
Dim l = CheckCuboidAgainstCollection(cuboids,
New Cuboid(newcub.X0, newcub.X1, newcub.Y0, newcub.Y1, newcub.Z0, oldcub.Z0),
x, xmax, ymin, ymax, zmin, zmax)
extracuboids.AddRange(l)
newcub.Z0 = oldcub.Z0
End If
If newcub.Z1 > oldcub.Z1 Then '' split off upper part
Dim l = CheckCuboidAgainstCollection(cuboids,
New Cuboid(newcub.X0, newcub.X1, newcub.Y0, newcub.Y1, oldcub.Z1, newcub.Z1),
x, xmax, ymin, ymax, zmin, zmax)
extracuboids.AddRange(l)
newcub.Z1 = oldcub.Z1
End If
Return extracuboids
End If
Next
Next
Next
Next
extracuboids.Add(newcub)
Return extracuboids
End Function
Private Structure Cuboid
Public X0, X1, Y0, Y1, Z0, Z1 As Integer
Public Sub New(x0 As Integer, x1 As Integer, y0 As Integer, y1 As Integer,
z0 As Integer, z1 As Integer)
Me.X0 = x0
Me.X1 = x1
Me.Y0 = y0
Me.Y1 = y1
Me.Z0 = z0
Me.Z1 = z1
End Sub
Public Function Overlaps(cub As Cuboid) As Boolean
If Math.Max(Me.X0, cub.X0) >= Math.Min(Me.X1, cub.X1) Then Return False
If Math.Max(Me.Y0, cub.Y0) >= Math.Min(Me.Y1, cub.Y1) Then Return False
Return Math.Max(Me.Z0, cub.Z0) < Math.Min(Me.Z1, cub.Z1)
End Function
Public Function GetVolume() As Integer
Return (Me.X1 - Me.X0) * (Me.Y1 - Me.Y0) * (Me.Z1 - Me.Z0)
End Function
End Structure