百力滋传递

如果某种类型的数量不同，则不可能；数量相同时总能完成。维护不变式：每个栈都是单一类型，且两个栈都非空时，它们的类型不同。设下一个需要的类型为 $c$。

第二个栈中有 $c$ 时执行 2；第一个栈中有 $c$ 时执行 12。如果两栈都没有 $c$，则未读输入中一定还有 $c$。依次读取输入，遇到 $c$ 时用 012 立即交出。

对之前遇到的其他类型 $d$：若第二个栈的类型为 $d$，执行 01；否则，如果第一个栈为空或类型为 $d$，执行 0；剩余情况下第二个栈必为空，执行 01。如果两个栈都非空且类型均不同于 $d$，由于一共只有三种类型，其中一个栈必含 $c$，与当前情况矛盾。必须优先检查第二个栈的同类型，以免将一种类型分散在两个栈中。所有操作都保持不变式。

每根百力滋恰好从输入经过两个栈到达输出，因此命令恰好有 $3N$ 个，时间和空间复杂度均为 $O(N)$。子任务 $1$ 可以记忆化搜索所有合法状态，状态数至多为 $O(N^3 3^N)$，计入字符串处理后的时间上界为 ，足以处理 。子任务 只需用第一个栈作缓冲：不断压入输入，直到栈顶类型符合要求，然后执行 。只有两种类型时，每次交出后缓冲栈总是单一类型，因此可在线性时间内完成。

Solution written by GPT6.1