|
|
A318271
|
|
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.
|
|
0
|
|
|
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, 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, 4, 8, 15, 14, 13, 12, 12, 11, 11, 11, 10, 9, 10, 10, 9, 8, 9
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
LINKS
|
|
|
EXAMPLE
|
When the crossing times are [1,2,5,10], the minimum total time for the group to cross is 17 minutes:
(2m) 1 and 2 cross,
(1m) 1 returns,
(10m) 5 and 10 cross,
(2m) 2 returns,
(2m) 1 and 2 cross.
+----+--------------------+------+
| n | Crossing times | a(n) |
+----+--------------------+------+
| 1 | [1] | 1 |
| 2 | [1, 1] | 1 |
| 3 | [2] | 2 |
| 4 | [1, 1, 1] | 3 |
| 5 | [1, 2] | 2 |
| 6 | [3] | 3 |
| 7 | [1, 1, 1, 1] | 5 |
| 8 | [1, 1, 2] | 4 |
| 9 | [1, 3] | 3 |
| 10 | [2, 2] | 2 |
| 11 | [4] | 4 |
| 12 | [1, 1, 1, 1, 1] | 7 |
| 13 | [1, 1, 1, 2] | 6 |
| 14 | [1, 1, 3] | 5 |
| 15 | [1, 2, 2] | 5 |
| 16 | [1, 4] | 4 |
| 17 | [2, 3] | 3 |
| 18 | [5] | 5 |
| 19 | [1, 1, 1, 1, 1, 1] | 9 |
| 20 | [1, 1, 1, 1, 2] | 8 |
| 21 | [1, 1, 1, 3] | 7 |
| 22 | [1, 1, 2, 2] | 6 |
| 23 | [1, 1, 4] | 6 |
| 24 | [1, 2, 3] | 6 |
| 25 | [1, 5] | 5 |
| 26 | [2, 2, 2] | 6 |
| 27 | [2, 4] | 4 |
| 28 | [3, 3] | 3 |
| 29 | [6] | 6 |
+----+--------------------+------+
|
|
PROG
|
(Julia)
function BT(p)
n = length(p)
p[end] = -(sum(p) + (n > 2 ? (n-3) * p[1] : 0))
if n >= 3
q = 2p[2] - p[1]; tog = false
for k in n-1:-1:1
(tog = ~tog) && p[k] > q ? p[k] -= q : p[k] = 0
end
end
-sum(p) end
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Terms a(45) and beyond added using Erwan's program from CodeGolf StackExchange by Andrey Zabolotskiy, Oct 18 2019
|
|
STATUS
|
approved
|
|
|
|