官方题解｜奇怪的机器

题目解析

每个转轴一共只有 0, 1, $\ldots$, 9 共 $10$ 个字符；
我们可以尝试枚举最终停下来显示的字符，最终从 $10$ 个答案中取最小的即可。

对于转轴 $i$ 若想其显示字符 $S_j$，那么根据题目意思，在每 $10$ 秒一个周期中只能选择第 $j$ 秒按下按钮。即时间 $t$ 需要满足 $t = 10 \times d + j$。
又每秒只能按一次按钮，我们可以使用一个数组 st 来标记 $t$ 秒是否按过按钮, 然后可以枚举 $d$，找到没有按按钮的最小的 $t = 10 \times d + j$，将 $st[t]$ 标记为 $1$。

对于每个字符 $x$，我们统计让所有的转轴停到 $x$，按下按钮最晚的时间 $x_{t}$ 即可。最终的答案取所有 $x_t$ 中最小的，即 $\min{x_t}$。

AC代码

C++ AC代码：

#include <bits/stdc++.h>

int main() {
    int n;
    std::cin >> n;
    std::vector<std::string> slots(n);
    for (auto &x : slots)
        std::cin >> x;
    int res = n * 10;
    for (int i = 0; i < 10; ++i) {
        std::vector<int> st(n * 10);
        int cur = 0;
        for (auto &s : slots) {
            int p = s.find('0' + i);
            while (st[p]) p += 10;
            st[p] = 1;
            cur = std::max(cur, p);
        }
        res = std::min(res, cur);
    }
    std::cout << res << '\n';
    return 0;
}

Python AC代码：

n = int(input())
slots = [input() for i in range(n)]
res = n * 10
for i in range(10):
    cur = 0
    st = [0] * n * 10
    for slot in slots:
        p = slot.find(str(i))
        while st[p]:
            p += 10
        st[p] = 1
        cur = max(cur, p)
    res = min(res, cur)
print(res)

复杂度分析

枚举所有的转轴，停在字符 $x$ 需要的时间，复杂度为 $\mathrm{O}(N^2)$，总共 $10$ 种字符，时间复杂度为 $\mathrm{O}(N^2 \times 10)$。