|
%I #26 Sep 04 2023 10:59:45
%S 1,1,2,3,2,3,5,4,3,2,4,7,6,5,5,4,3,5,9,8,7,6,6,6,5,6,4,3,6,11,10,9,8,
%T 8,7,7,8,7,7,6,7,5,4,7,13,12,11,10,10,9,9,9,8,7,8,9,8,8,7,10,8,8,6,5,
%U 4,8,15,14,13,12,12,11,11,11,10,9,10,10,9,8,9
%N The optimum crossing time for the Bridge and Torch problem, given that the crossing times for the group's members are given by the n-th partition in A026791.
%H User baseman101, <a href="https://codegolf.stackexchange.com/q/75615/53884">The Bridge and Torch Problem</a>, Programming Puzzles & Code Golf Stack Exchange.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Bridge_and_torch_problem">Bridge and torch problem</a>.
%e When the crossing times are [1,2,5,10], the minimum total time for the group to cross is 17 minutes:
%e (2m) 1 and 2 cross,
%e (1m) 1 returns,
%e (10m) 5 and 10 cross,
%e (2m) 2 returns,
%e (2m) 1 and 2 cross.
%e +----+--------------------+------+
%e | n | Crossing times | a(n) |
%e +----+--------------------+------+
%e | 1 | [1] | 1 |
%e | 2 | [1, 1] | 1 |
%e | 3 | [2] | 2 |
%e | 4 | [1, 1, 1] | 3 |
%e | 5 | [1, 2] | 2 |
%e | 6 | [3] | 3 |
%e | 7 | [1, 1, 1, 1] | 5 |
%e | 8 | [1, 1, 2] | 4 |
%e | 9 | [1, 3] | 3 |
%e | 10 | [2, 2] | 2 |
%e | 11 | [4] | 4 |
%e | 12 | [1, 1, 1, 1, 1] | 7 |
%e | 13 | [1, 1, 1, 2] | 6 |
%e | 14 | [1, 1, 3] | 5 |
%e | 15 | [1, 2, 2] | 5 |
%e | 16 | [1, 4] | 4 |
%e | 17 | [2, 3] | 3 |
%e | 18 | [5] | 5 |
%e | 19 | [1, 1, 1, 1, 1, 1] | 9 |
%e | 20 | [1, 1, 1, 1, 2] | 8 |
%e | 21 | [1, 1, 1, 3] | 7 |
%e | 22 | [1, 1, 2, 2] | 6 |
%e | 23 | [1, 1, 4] | 6 |
%e | 24 | [1, 2, 3] | 6 |
%e | 25 | [1, 5] | 5 |
%e | 26 | [2, 2, 2] | 6 |
%e | 27 | [2, 4] | 4 |
%e | 28 | [3, 3] | 3 |
%e | 29 | [6] | 6 |
%e +----+--------------------+------+
%o (Julia)
%o function BT(p)
%o n = length(p)
%o p[end] = -(sum(p) + (n > 2 ? (n-3) * p[1] : 0))
%o if n >= 3
%o q = 2p[2] - p[1]; tog = false
%o for k in n-1:-1:1
%o (tog = ~tog) && p[k] > q ? p[k] -= q : p[k] = 0
%o end
%o end
%o -sum(p) end
%o [BT(p) for n in 1:9 for p in A026791(n)] |> println # _Peter Luschny_, Oct 18 2019
%Y Cf. A026791, A078476.
%K nonn,nice
%O 1,3
%A _Peter Kagey_, Aug 22 2018
%E Terms a(45) and beyond added using Erwan's program from CodeGolf StackExchange by _Andrey Zabolotskiy_, Oct 18 2019
|
