题目150：在三角形数组中搜索具有最小和的子三角形

欧拉计划

Searching a triangular array for a sub-triangle having minimum-sum

In a triangular array of positive and negative integers, we wish to find a sub-triangle such that the sum of the numbers it contains is the smallest possible.

In the example below, it can be easily verified that the marked triangle satisfies this condition having a sum of −42.

We wish to make such a triangular array with one thousand rows, so we generate 500500 pseudo-random numbers s_k in the range ±2¹⁹, using a type of random number generator (known as a Linear Congruential Generator) as follows:

t := 0
for k = 1 up to k = 500500:
    t := (615949*t + 797807) modulo 2²⁰
    sk := t−2¹⁹

Thus: s₁ = 273519, s₂ = −153582, s₃ = 450905 etc

Our triangular array is then formed using the pseudo-random numbers thus:

s1
s2  s3
s4  s5  s6  
s7  s8  s9  s10
...

Sub-triangles can start at any element of the array and extend down as far as we like (taking-in the two elements directly below it from the next row, the three elements directly below from the row after that, and so on).
The "sum of a sub-triangle" is defined as the sum of all the elements it contains.
Find the smallest possible sub-triangle sum.

题目：

在一个由正整数和负整数组成的三角形数组中，我们希望找到一个子三角形，使得该三角形中包含的所有数字之和最小。

在下图的例子中，可以验证红色标记的三角形满足上述条件，其和为 -42。

我们希望构造一个一千行的三角形数组，所以我们用如下一种名为线性同余法的随机数生成法生成 500500 个伪随机数 s_k，范围在正负 2¹⁹ 之间：

t := 0
for k = 1 up to k = 500500:
t := (615949*t + 797807) modulo 2²⁰
s_k := t−2¹⁹

因此: s₁ = 273519, s₂ = −153582, s₃ = 450905 等等。

因此我们用随机数组成的三角型数组具有如下形式：

s1
s2 s3
s4 s5 s6
s7 s8 s9 s10
...

子三角形可以从数组中的任意元素开始，可以向下任意延伸（从下一行取两个元素，再下一行取三个元素，如此继续）。

定义“子三角形和”为子三角形内包含的所有元素之和。

求最小的子三角形和。

jerryxjr1220

from numba import jit
import numpy as np 
@jit
def gen_s():
        s = np.zeros((1000,1000), dtype='int64')
        t = 0
        for l in range(1000):
                i = 0
                while i <= l:
                        t = (615949*t+797807) % 2**20
                        s[l,i] = t-2**19
                        i += 1
        return s
@jit
def get_sum(s, start_row, start_col, lines):
        total = s[start_row, start_col]
        for l in range(1, lines):
                for i in range(l+1):
                        total += s[start_row+l, start_col+i]
        return total
@jit
def solve():
        s = gen_s()
        smallest = 99999999
        for lines in range(1000,1,-1):
                x, y = 0, 0
                while  x + lines <= 1000:
                        y = 0
                        while y <= x:
                                smallest = min(smallest, get_sum(s, x, y, lines))
                                y += 1
                        x += 1
        return smallest
print(solve())

gunjang

继续采用pascal代码，d7编译通过，运行时间1~2s左右

program p150_2;

{$APPTYPE CONSOLE}

uses
  SysUtils, Types, Windows, Math;
const
  maxline = 1000;
  B220 = 1 shl 20;
  B219 = 1 shl 19;
type
  tline = array of Int64;
  Ttriangle = array[0..maxline - 1] of tline;
    //have n*(n+1)*(n+2)/6 triangle == 1.67billion
var
  triangle: Ttriangle;
  sumtriangle: Ttriangle;
  minsum: int64; //2^12 * 50w may >= 2^32
  st: DWORD;

procedure initSK;
var
  t, s: int64;
  line, col: integer;
begin
  minsum := 0;
  t := 0;
  for line := 0 to maxline - 1 do
  begin
    setlength(triangle[line], line + 1);
    for col := 0 to line do
    begin
      t := (615949 * t + 797807) mod B220;
      s := t - b219;
      triangle[line][col] := s;
      if s < minsum then
        minsum := s; //sidelength=1
    end;
  end;
end;

procedure calSumofTriangles;
var
  x, y: integer;
  sidelength: integer;
  x2, y2: integer;
  bottomsum: int64;
begin
  //calculate sidelength=2 Triangles
  for y := 0 to maxline - 2 do
  begin
    setlength(sumtriangle[y], y + 1);
    for x := 0 to y do
    begin
      sumtriangle[y][x] := triangle[y][x] + triangle[y + 1][x] + triangle[y + 1][x + 1];
      if sumtriangle[y][x] < minsum then
        minsum := sumtriangle[y][x];
    end;
  end;

  for sidelength := 3 to maxline do
  begin
    for y := 0 to maxline - sidelength do
    begin
      bottomsum := 0;
      y2 := y + sidelength - 1;
      for x2 := 0 to sidelength - 1 do
        inc(bottomsum, triangle[y2][x2]);
      inc(sumtriangle[y][0], bottomsum);
      if sumtriangle[y][0] < minsum then
        minsum := sumtriangle[y][0];

      for x := 1 to y do
      begin
        inc(bottomsum, -triangle[y2][x - 1] + triangle[y2][x - 1 + sidelength]);
        sumtriangle[y][x] := sumtriangle[y][x] + bottomsum;
        if sumtriangle[y][x] < minsum then
          minsum := sumtriangle[y][x];
      end;
    end;

    if sidelength mod 50 = 0 then
      writeln(Format('sidelenght=%d, minSum=%d', [sidelength, minsum]));
  end;
end;

begin
  st := gettickcount;
  initSK;
  calSumofTriangles;
  writeln(minsum); //-271248680
  writeln(Format('cost %n s', [(gettickcount - st) / 1000])); //1.56s-2.36s
  readln;
end.