最长的渡船行程

有 8 个人，编号为 1、2、3、4、5、6、7、8。他们一开始都在左岸，目标是全部到达右岸。河上只有一艘船；每次必须有 1 人或 2 人乘船，船只能从它当前所在的一岸划到另一岸。每次单程记为 1 趟。

普通的两人渡船问题往往很短；这里反过来：你要设计“哪些人可以同时留在同一岸”的安全规则，让任何可行方案都被迫绕很远的路。规则不是逐条用自然语言列出，而是压缩成一个十六进制字符串，供程序直接读取。

规则必须用一个恰好 32 个十六进制字符的字符串提交，也就是恰好 128 个二进制位。

如何由十六进制字符串定义岸的合法性

把第 8 人当作参照。任何一个时刻，必有一岸包含第 8 人。

设这一岸上除第 8 人以外的人组成集合：

给集合 $S$ 编号：

也就是说，1 到 7 号人对应的权重依次是 1、2、4、8、16、32、64。例如，若 $S=\{1,3,6\}$，则

把你提交的 32 个十六进制字符按通常方式展开为 128 个二进制位：最右边是第 0 位，最左边是第 127 位。对每个集合 $S$：

• 第 $i(S)$ 位为 0：第 8 人与 $S$ 中这些人留在同一岸是合法的；
• 第 $i(S)$ 位为 1：这种分岸状态非法。

另一岸恰好是上述人员的补集，所以同一个位已经规定了完整分岸状态是否允许。渡河过程中的每一个时刻都必须合法，开始和结束时也必须合法。

为什么只记录含第 8 人的一岸？因为另一岸必然是它的补集；确定一岸的人员后，另一岸的人员也随之确定，不需要重复编码。

任务

找出一个 32 个十六进制字符的字符串，使得：

1. 从“8 人都在左岸、船在左岸”到“8 人都在右岸、船在右岸”存在合法方案；
2. 在所有合法方案中，趟数最少的方案也至少需要 73 趟。

请只提交这个 32 个十六进制字符的字符串。

小例子：6 人版

为理解编码，考虑一个 6 人版本。把第 8 人换成小写 a，其余 5 人依次为 b、c、A、B、C，仍按顺序赋予权重 1、2、4、8、16。

规则表 7e3e5e6e 表示下列含 a 的同岸人群合法：

a b c A B C
a b c
a b A B
a b A
a b
a c A B C
a c A C
a c
a A B C
a A
a

这个 6 人例子的最短合法渡河方案需要 11 趟。

再看一个具体的位编号。对 6 人示例，若含 a 的岸上另外有 b 和 A，其编号是 $1+4=5$。规则表 7e3e5e6e 的第 5 位为 1，所以 a、b、A 同岸的分配不合法；这也解释了为什么上面的合法人群列表中没有这一项。

附加题： 仍使用同样的 6 人、两人船和规则表编码，找出一个规则表，使最短合法渡河方案需要 19 趟。