這裡的題目與高中生程式解讀系統的題目敘述會有落差，但基本都是相同的 這裡提供由AA競程做的解題系統： P1:https://apcs.aacpoj.com/problem/apcs202611mh1 P2:https://apcs.aacpoj.com/problem/apcs202611mh2 P3:https://apcs.aacpoj.com/problem/apcs202611mh3

高中生程式解讀系統連結:https://zerojudge.tw/ShowContest?contestid=27726

有任何問題歡迎傳Email:edychie0323@gmail.com給我!

P1 營火競賽

題目敘述

營隊要決定隔天由哪一隊負責營地建設，因此舉辦了一場火把競賽。

共有 n 個人參加，分屬 k 支隊伍。所有人面向營火圍成一圈，依順時針方向編號為 1, 2, …, n。第 i 個人所屬的隊伍為 tᵢ，隊伍編號介於 1 到 k 之間。

由於所有人都面向圓心，每個人的左手邊就是順時針方向的下一個人。因此，第 i 個人的左手邊是第 i+1 個人，第 n 個人的左手邊則是第 1 個人。

比賽開始時，每個人的火把都已點燃，滅火器由第 1 個人持有。持有滅火器的人稱為「行動者」，每一回合依照下列規則進行：

  1. 熄滅一支火把

    行動者從自己左手邊的下一個人開始，沿順時針方向依序尋找。遇到火把已熄滅的人，或與行動者同隊的人，都直接跳過。找到第一位「火把仍點燃，且與行動者不同隊」的人後，熄滅他的火把。火把熄滅的人，之後不會再成為行動者。

  2. 判斷比賽是否結束

    如果所有火把仍點燃的人都屬於同

  3. 一隊，比賽立刻結束，並由該隊負責隔天的營地建設。

  4. 傳遞滅火器

    如果比賽尚未結束，行動者再次從自己左手邊的下一個人開始，沿順時針方向尋找，將滅火器交給第一位火把仍點燃的人，作為下一回合的行動者。這個人可以與原行動者同隊。

    注意：尋找下一位行動者時，是從原行動者的左手邊開始，而不是從剛被熄滅火把的人的左手邊開始。

沿順時針方向尋找時，經過第 n 個人後，會回到第 1 個人繼續尋找。

如果一開始所有人就屬於同一隊，也就是 k = 1，比賽不進行任何回合便結束，熄滅的火把數為 0。

請計算比賽結束時，總共有幾支火把被熄滅，以及最後由哪一隊負責營地建設。

子題配分

本題共分為以下兩個子題：

子題配分額外限制
140%n < 1000
260%無額外限制，符合原題限制 1 ≤ k ≤ n ≤ 2000

輸入說明

第一行有兩個整數 n 與 k，分別代表參加人數及隊伍數。

第二行有 n 個整數 t₁, t₂, …, tₙ，其中 tᵢ 代表第 i 個人所屬的隊伍。

資料範圍：

  • 1 ≤ k ≤ n ≤ 2000。
  • 1 ≤ tᵢ ≤ k。
  • 第 1 隊到第 k 隊，每一隊都至少有一個人。

輸出說明

輸出一行，包含兩個整數 x 與 w，中間以一個空白隔開。

  • x：比賽結束時，被熄滅的火把總數。
  • w：最後負責營地建設的隊伍編號，也就是所有火把仍點燃的人所屬的隊伍。

範例一

輸入

6 3
2 2 1 3 1 2

輸出

4 2

範例一說明

範例一火把熄滅過程

回合行動者被熄滅火把的人
1第 1 個人（第 2 隊）第 3 個人（第 1 隊）
2第 2 個人（第 2 隊）第 4 個人（第 3 隊）
3第 5 個人（第 1 隊）第 6 個人（第 2 隊）
4第 1 個人（第 2 隊）第 5 個人（第 1 隊）

詳細過程如下：

  1. 第 1 個人屬於第 2 隊。他向左依序遇到第 2 個人（同隊，跳過）及第 3 個人（不同隊），因此熄滅第 3 個人的火把。接著由第 2 個人成為行動者。
  2. 第 2 個人屬於第 2 隊。他向左依序跳過火把已熄滅的第 3 個人，接著找到第 4 個人（第 3 隊），因此熄滅第 4 個人的火把。接著由第 5 個人成為行動者。
  3. 第 5 個人屬於第 1 隊。他向左找到第 6 個人（第 2 隊），因此熄滅第 6 個人的火把。接著沿圓圈繞回第 1 個人，由第 1 個人成為行動者。
  4. 第 1 個人屬於第 2 隊。他向左跳過同隊的第 2 個人，以及火把已熄滅的第 3、4 個人，接著找到第 5 個人（第 1 隊），因此熄滅第 5 個人的火把。

此時只有第 1、2 個人的火把仍然點燃，且兩人都屬於第 2 隊，因此競賽結束。總共熄滅 4 支火把，最後由第 2 隊負責隔日的營地建設。

範例二

輸入

7 3
1 2 1 3 2 3 2

輸出

6 2

範例二說明

回合行動者被熄滅火把的人
1第 1 個人（第 1 隊）第 2 個人（第 2 隊）
2第 3 個人（第 1 隊）第 4 個人（第 3 隊）
3第 5 個人（第 2 隊）第 6 個人（第 3 隊）
4第 7 個人（第 2 隊）第 1 個人（第 1 隊）
5第 3 個人（第 1 隊）第 5 個人（第 2 隊）
6第 7 個人（第 2 隊）第 3 個人（第 1 隊）

第 4 回合中，第 7 個人沿順時針方向繞回圓圈前端，找到第 1 個人。

第 6 回合結束後，只剩第 7 個人的火把仍然點燃，他屬於第 2 隊，因此競賽結束。總共熄滅 6 支火把，最後由第 2 隊負責隔日的營地建設。

解題思路：環狀雙向鏈結串列模擬

n 最多只有 2000，可以直接模擬，每回合尋找第一位不同隊伍的人。為了方便跳過火把已熄滅的人，使用兩個陣列表示環狀雙向鏈結串列：

  • nxt[i]：從第 i 個人往順時針方向走，第一位火把仍點燃的人。
  • prv[i]：從第 i 個人往逆時針方向走，第一位火把仍點燃的人。
  • count[t]：第 t 隊目前還有幾個人的火把點燃。
  • remaining_teams：目前還有火把點燃的隊伍數。

程式內的人員索引從 0 開始，因此 actor = 0 代表題目的第 1 個人；隊伍編號仍維持從 1 開始。

為何要這樣做

使用一般陣列刪除元素時，後方元素可能需要搬移。這裡只要更新兩條連結，就能把被熄滅的人從圈子中移除，之後不會再走到他。

每回合先從 nxt[actor] 出發，跳過同隊的人。找到 target 後，令 target 的前一位與後一位互相連接，再更新該隊人數。若某隊人數變成 0，就把剩餘隊伍數減 1。

最容易寫錯的是下一位行動者：必須在刪除 target 之後，設定 actor = nxt[actor]。這表示從「原行動者」向前找，而非從被熄滅的人向前找。若剛好熄滅緊鄰的人，更新後的連結也會自動跳過他。

正確性說明

一開始鏈結包含所有人，且順序和題目一致。假設某回合開始時，鏈結恰好包含所有火把仍點燃的人，actor 也正確。

沿著 nxt 走，等同跳過所有已熄滅的人；再跳過同隊的人，找到的 target 就是題目指定的第一位敵隊成員。刪除 target 後，鏈結仍依原順時針順序保留所有仍點燃的人。此時 nxt[actor] 正是題目規定的下一位行動者，因此下一回合也保持正確。

每回合更新隊伍人數，remaining_teams 恰好代表尚存隊伍數。當它等於 1 時立即停止，輸出的熄滅數與最後隊伍因此正確。若 k = 1，迴圈一次也不執行，會輸出 0 和原本的隊伍。

複雜度

每回合最多搜尋 n 個位置，最多進行 n − 1 回合，因此時間 O(n²)，空間 O(n + k)，在 k ≤ n 下也可寫成 O(n)。

Python 程式碼

import sys


def solve(n, k, team):
    count = [0] * (k + 1)
    for t in team:
        count[t] += 1

    # Circular doubly linked list of people whose torches are still lit.
    nxt = [(i + 1) % n for i in range(n)]
    prv = [(i - 1) % n for i in range(n)]
    remaining_teams = k
    actor = 0
    extinguished = 0

    while remaining_teams > 1:
        target = nxt[actor]
        while team[target] == team[actor]:
            target = nxt[target]

        # Remove the target before choosing the next actor.
        nxt[prv[target]] = nxt[target]
        prv[nxt[target]] = prv[target]
        t = team[target]
        count[t] -= 1
        if count[t] == 0:
            remaining_teams -= 1
        extinguished += 1
        actor = nxt[actor]

    return extinguished, team[actor]


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, k = data[:2]
    print(*solve(n, k, data[2:2 + n]))


if __name__ == "__main__":
    main()

C++17 程式碼

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> team(n), count(k + 1), nxt(n), prv(n);
    for (int &t : team) {
        cin >> t;
        ++count[t];
    }
    for (int i = 0; i < n; ++i) {
        nxt[i] = (i + 1) % n;
        prv[i] = (i + n - 1) % n;
    }

    int remainingTeams = k, actor = 0, extinguished = 0;
    while (remainingTeams > 1) {
        int target = nxt[actor];
        while (team[target] == team[actor]) target = nxt[target];

        nxt[prv[target]] = nxt[target];
        prv[nxt[target]] = prv[target];
        if (--count[team[target]] == 0) --remainingTeams;
        ++extinguished;
        actor = nxt[actor];
    }
    cout << extinguished << ' ' << team[actor] << '\n';
}

P2 火星探測資料

題目敘述

探測車在火星表面進行了 k 次探測，每次的結果都記錄為一個長度為 n、只包含小寫英文字母的字串。研究團隊希望將這些資料整合成一個字串 S，以減少傳回地球時所需的能源。

整合後的字串 S 必須包含每一筆探測結果，且每筆結果都必須是 S 的「連續子字串」。不同探測結果可以共用部分字母，在 S 中出現的順序也不必與輸入順序相同。如果有多筆相同的探測結果，只需要在 S 中出現一次即可。

例如，rock 和 ocks 可以整合成 rocks，因為這兩個字串都是 rocks 的連續子字串。

請找出符合條件且長度最短的字串 S。如果有多個長度最短的答案，請輸出其中字典序最小的一個。

連續子字串

是指從一個字串中取出一段連續的字元，並保持原本的順序。例如，lan 是 planet 的連續子字串，但 pnt 不是。

字典序

的比較方式為：由左至右逐一比較兩個字串的字母，在第一個不同的位置，字母較前面的字串，其字典序較小。例如，rocker 的字典序比 rocket 小，因為第一個不同的字母是 r 和 t，而 r 在字母表中排在 t 前面。

輸入說明

第一行包含兩個整數 n、k（1 ≤ n ≤ 8，1 ≤ k ≤ 9），分別代表每筆探測結果的長度與探測結果的筆數。

接下來 k 行，每行包含一個長度恰好為 n、僅由小寫英文字母組成的字串，代表一筆探測結果。

輸出說明

輸出一行字串 S。S 必須包含所有輸入字串作為連續子字串，且長度必須最短。若答案不唯一，輸出其中字典序最小者。

範例一

輸入

4 2
aaaa
bbbb

輸出

aaaabbbb

範例一說明

aaaa 的非空後綴無法與 bbbb 的前綴相同，反過來也一樣，因此兩個字串無法重疊。任何可行答案的長度至少為 8。

aaaabbbb 與 bbbbaaaa 都包含這兩筆探測結果，且長度都是 8。比較字典序時，第一個字元分別為 a 與 b，因此 aaaabbbb 較小，應輸出 aaaabbbb。

範例二

輸入

4 6
aaaa
aaab
aaba
aabc
abaa
baaa

輸出

aabaaaabc

範例二說明

在輸出字串 aabaaaabc 中，各筆探測結果的位置如下（位置由 1 開始計算）：

探測結果在輸出字串中的位置
aaba第 1 至第 4 個字元
abaa第 2 至第 5 個字元
baaa第 3 至第 6 個字元
aaaa第 4 至第 7 個字元
aaab第 5 至第 8 個字元
aabc第 6 至第 9 個字元

因此，aabaaaabc 的確包含全部六筆探測結果。

由於六個輸入字串彼此不同，而長度為 L 的字串只有 L-4+1 個長度為 4 的連續子字串位置，因此要容納六個不同的輸入字串，S 的長度至少為 9。

將六筆資料依照 aaba、abaa、baaa、aaaa、aaab、aabc 的順序排列時，每一筆的後三個字元都與下一筆的前三個字元相同，所以它們可以依序重疊，得到長度為 9 的 aabaaaabc。

這個結果達到前述長度下限，因此不可能再縮短。經比較所有長度為 9 的可行字串後，aabaaaabc 的字典序最小，所以答案為 aabaaaabc。

解題思路：狀態壓縮動態規劃

k 最多為 9，因此可以用一個二進位整數記錄哪些字串已經選入排列。先移除重複字串，令剩下的不同字串數為 r。所有字串長度都相同，去重後不會有某字串完整包含另一個不同字串的情況。

先計算兩個字串的最大重疊

對每對字串 i、j，從大到小嘗試重疊長度，找出「i 的後綴」等於「j 的前綴」的最大長度。

例如 abcd 與 cdef 的最大重疊是 cd，接上第二個字串時只需追加 ef。程式的 add[i][j] 就記錄需要追加的部分。

不能每次只選眼前重疊最多的一對：這個決定可能破壞後續更好的銜接，所以需要考慮所有字串排列。

DP 狀態與轉移

dp[mask][i] 表示：排列中已選入 mask 標記的字串，最後一個選入的是 i 時，能得到的最佳合併字串。「最佳」依序比較長度、字典序。

mask 的第 j 個位元是 1，表示第 j 個字串已選入排列。這是排列的紀錄，不要求未選入的字串一定尚未作為子字串出現。

初始時，只選一個字串 i，所以 dp[1 << i][i] = words[i]。

對每個尚未選入的 j，候選答案為：

new_mask = mask | (1 << j)
candidate = dp[mask][i] + add[i][j]

若 candidate 比 dp[new_mask][j] 短，或長度相同但字典序更小，就更新該狀態。最後從全部字串皆選入的狀態中，選出最佳答案。

Python 用 None 表示尚未到達的狀態；C++ 用空字串表示，因為本題的有效答案一定非空。

為何每個狀態只留一個字串就夠

相同的 mask 和最後一個字串 i，接下來可選的字串完全相同，追加的內容也只由 i 和下一個 j 決定。

如果目前答案比較短，後面追加相同內容後仍然比較短；如果長度相同而字典序較小，追加相同內容後也仍然較小。因此較差的狀態不可能在未來反超，可以安全捨棄。

正確性說明

任一最短可行答案，都能為每個不同輸入字串選定一個出現位置，依照起點由左到右排序。因為所有輸入字串等長且互不相同，它們的起點與終點都依相同順序增加，不會互相包含。

這個排列至少有一種把字串依序接起來的方式。相鄰字串若有重疊，該重疊不會超過我們預先算出的最大重疊；若有未被覆蓋的空隙，刪掉空隙也不影響包含所有字串。因此用最大重疊依序合併，不會比原答案更長。

如果原答案已最短，合併後便不能再短，所以它對應的相鄰間距必須已經達到最大重疊。這表示所有最短答案都能由某個字串排列的最大重疊合併產生。

DP 考慮所有起點與所有下一個字串，涵蓋全部排列；每個狀態又保留長度與字典序最好的字串，所以最後必定得到最短、且同長度中字典序最小的答案。

複雜度

令 L = r × n，這是答案長度的上界，最多為 72。

目前程式透過切片／子字串比較計算重疊，預處理時間為 O(r² × n²)。DP 有 O(2^r × r) 個狀態，每個嘗試 r 種下一個字串；考慮字串複製與比較，時間為 O(2^r × r² × L)，空間為 O(2^r × r × L + r² × n)。

Python 程式碼

import sys


def solve(words):
    words = sorted(set(words))
    r = len(words)
    n = len(words[0])

    # add[i][j] is the part of word j not covered by word i.
    add = [[""] * r for _ in range(r)]
    for i in range(r):
        for j in range(r):
            overlap = 0
            for length in range(n, 0, -1):
                if words[i][-length:] == words[j][:length]:
                    overlap = length
                    break
            add[i][j] = words[j][overlap:]

    dp = [[None] * r for _ in range(1 << r)]
    for i, word in enumerate(words):
        dp[1 << i][i] = word

    for mask in range(1, 1 << r):
        for i in range(r):
            current = dp[mask][i]
            if current is None:
                continue
            for j in range(r):
                if mask & (1 << j):
                    continue
                new_mask = mask | (1 << j)
                candidate = current + add[i][j]
                old = dp[new_mask][j]
                if old is None or (len(candidate), candidate) < (len(old), old):
                    dp[new_mask][j] = candidate

    return min((s for s in dp[-1] if s is not None), key=lambda s: (len(s), s))


def main():
    data = sys.stdin.buffer.read().split()
    k = int(data[1])
    print(solve([s.decode() for s in data[2:2 + k]]))


if __name__ == "__main__":
    main()

C++17 程式碼

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool better(const string &a, const string &b) {
    return b.empty() || a.size() < b.size() ||
           (a.size() == b.size() && a < b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<string> words(k);
    for (auto &s : words) cin >> s;
    sort(words.begin(), words.end());
    words.erase(unique(words.begin(), words.end()), words.end());
    int r = static_cast<int>(words.size());

    vector<vector<string>> add(r, vector<string>(r));
    for (int i = 0; i < r; ++i) {
        for (int j = 0; j < r; ++j) {
            int overlap = 0;
            for (int length = n; length >= 1; --length) {
                if (words[i].substr(n - length) == words[j].substr(0, length)) {
                    overlap = length;
                    break;
                }
            }
            add[i][j] = words[j].substr(overlap);
        }
    }

    // An empty string denotes an unreachable state; valid answers are nonempty.
    vector<vector<string>> dp(1 << r, vector<string>(r));
    for (int i = 0; i < r; ++i) dp[1 << i][i] = words[i];
    for (int mask = 1; mask < (1 << r); ++mask) {
        for (int i = 0; i < r; ++i) {
            if (dp[mask][i].empty()) continue;
            for (int j = 0; j < r; ++j) {
                if (mask & (1 << j)) continue;
                int newMask = mask | (1 << j);
                string candidate = dp[mask][i] + add[i][j];
                if (better(candidate, dp[newMask][j]))
                    dp[newMask][j] = candidate;
            }
        }
    }

    string answer;
    for (const auto &s : dp.back()) {
        if (!s.empty() && better(s, answer)) answer = s;
    }
    cout << answer << '\n';
}

P3 考拉茲距離

題目敘述

考拉茲操作會把一個正整數 n 換成另一個數，換法依 n 的奇偶而定：

  • 如果 n 是奇數，n 變成 (3n + 1) / 2。
  • 如果 n 是偶數，n 變成 n / 2。

當 n 是奇數時，3n + 1 是偶數，所以換出來的數仍是正整數。例如，21 是奇數，做一次操作後變成 (3 × 21 + 1) / 2 = 32；32 是偶數，再做一次操作後變成 16。

給定目標數字 t 和操作次數的上限 m。如果從正整數 x 開始連續做考拉茲操作，在 m 次以內（可以是 0 次）就會變成 t，就說 x 是「可行的數」。做 0 次的意思是 x 本身就等於 t，所以 t 一定是可行的數。

接著有 q 筆詢問，每筆詢問給一個正整數 a_i。對每筆詢問，請在所有可行的數 x 之中找出距離 a_i 最近的，輸出 |a_i − x| 的最小值。每筆詢問分開計算，互不影響。

輸入說明

第一行有三個整數 t、m、q，依序代表目標數字、操作次數的上限、詢問的筆數。

第二行有 q 個正整數 a_1、a_2、…、a_q，代表每筆詢問給的數。

資料範圍：

  • 1 ≤ t ≤ 10^9
  • 0 ≤ m < 32
  • 1 ≤ q ≤ 10^4
  • 1 ≤ a_i ≤ 10^18

輸出說明

輸出 q 行，第 i 行是第 i 筆詢問的答案，也就是 |a_i − x| 在所有可行的數 x 之中的最小值。

範例一

輸入

11 3 3
16 88 200

輸出

2
0
112

範例一說明

所有能在不超過 3 次考拉茲操作後變成 11 的正整數為：

考拉茲操作次數可行的起始數字操作過程
01111
17,227→11；22→11
214,4414→7→11；44→22→11
39,28,29,889→14→7→11；28→14→7→11；29→44→22→11；88→44→22→11
  • 對 16 而言，最接近的可行數字是 14，所以將 16 減少 2 即可，答案為 2。
  • 88 本身就是可行數字，不需要調整，答案為 0。
  • 對 200 而言，最接近的可行數字是 88，所以需要減少 200-88=112，答案為 112。

範例二

輸入

5 4 5
1 9 20 27 100

輸出

2
1
0
1
20

範例二說明

可以從目標數字 5 反向列出所有可行的起始數字。若目前數字為 y，則 2y 一定能在一次操作後變成 y；此外，只有當 (2y-1)/3 是正奇數時，它才是另一個合法的前一步數字。

所有能在不超過 4 次考拉茲操作後變成 5 的正整數如下：

考拉茲操作次數可行的起始數字
05
13,10
26,20
312,13,40
424,26,80

各詢問的計算如下：

詢問最接近的可行數字加減次數考拉茲操作過程
1323 → 5
910110 → 5
2020020 → 10 → 5
2726126 → 13 → 20 → 10 → 5
100802080 → 40 → 20 → 10 → 5

所以五個詢問依序輸出 2,1,0,1,20。

解題思路：反向搜尋可行起點，再用二分搜尋

直接對每個詢問嘗試調整 x 不可行，因為 a 最大為 10^18。我們改從共同的目標 t 出發，一次找出所有能在 m 步以內抵達 t 的起點，再重複利用這個集合回答詢問。

如何反推前一步

假設操作後的數字為 y：

  1. 若前一步 x 是偶數，x / 2 = y，所以 x = 2y。這個前一步永遠合法。
  2. 若前一步 x 是奇數，(3x + 1) / 2 = y，所以 x = (2y − 1) / 3。必須確認它是正奇數。

第二種前一步恰好在 y % 3 == 2 時成立。寫成 y = 3b + 2，便得到 x = 2b + 1，一定是正奇數，因此不需要額外檢查奇偶性。

例如 y = 5 的前一步有 10 和 3；y = 3 只有 6，不能直接把 (2×3−1)/3 當成整數除法取整。

為何要分層搜尋與去重

第 0 層先放 t，代表允許操作 0 次。再向外反推 m 層，並把每層找到的數字加入 seen。

frontier 只放本層首次發現的數字。因為按層搜尋，每個數字第一次被找到時，就是它反向抵達 t 的最少步數；較晚再次到達同一個數字不會增加可用的剩餘步數，因此不需要重複展開。

這點也能處理 t = 1 等循環，例如 1 與 2 之間的重複走訪。不能只保留第 m 層，因為題目允許的是「不超過 m 次」，所以必須保留所有已發現的數字。

如何回答詢問

將 seen 排序成 values。對詢問 a，使用二分搜尋找出第一個大於或等於 a 的位置 pos。

最近的可行數字只可能是 values[pos] 或 values[pos − 1]，也就是 a 左右最靠近的鄰居。更左邊或更右邊的值，距離一定不會更小。程式會先檢查索引是否存在，再計算兩者距離的較小值。

若 a 就在集合中，右側候選等於 a，答案自然為 0。

正確性說明

反向搜尋加入的每條邊，都是一次合法考拉茲操作的反向，所以第 d 層找到的數字能用 d 步抵達 t，不會加入不合法的起點。

反過來，任何能用不超過 m 步抵達 t 的起點，都有一條合法的正向操作路徑。把路徑反過來，會由 t 沿著上述兩種反向邊走到該起點，因此一定會被搜尋找到。分層去重不會漏掉路徑，因為最早發現同一數字時，剩餘可搜尋的深度最多。

因此 seen 正好是所有可行起點。排序後檢查 a 左右鄰居，可以得到集合中與 a 距離最小的數字，所以每個詢問的答案正確。

整數範圍與複雜度

每次反向操作得到的數字最多是原本的兩倍，所以所有可行起點都不超過 t × 2^m。依本題限制，上界為 10^9 × 2^31 = 2,147,483,648,000,000,000，小於有號 64 位元整數上限；C++ 使用 long long 即可，Python 的整數則會自動擴充。

注意可行起點可能大於 10^18，不能因為詢問上限是 10^18 就直接丟棄它們。

令 V 為搜尋得到的不同數字總數。使用雜湊集合時，搜尋的平均時間為 O(V)，排序 O(V log V)，q 個詢問共 O(q log V)，空間 O(V)。這不是只需 O(m) 的演算法：反向搜尋會分支，V 也取決於 t、m；粗略最壞樹狀上界為 2^(m+1) − 1，實際受到合法奇數前驅條件與去重限制，不能把每層當成必有兩個分支。本題 m 最多為 31。

Python 程式碼

import sys
from bisect import bisect_left


def reachable(t, m):
    seen = {t}
    frontier = [t]
    for _ in range(m):
        next_frontier = []
        for y in frontier:
            # The even predecessor always exists.
            x = 2 * y
            if x not in seen:
                seen.add(x)
                next_frontier.append(x)

            # If y % 3 == 2, (2*y-1)/3 is a positive odd integer.
            if y % 3 == 2:
                x = (2 * y - 1) // 3
                if x not in seen:
                    seen.add(x)
                    next_frontier.append(x)
        frontier = next_frontier
        if not frontier:
            break
    return sorted(seen)


def distance(values, a):
    pos = bisect_left(values, a)
    answer = abs(a - values[0])
    if pos < len(values):
        answer = min(answer, values[pos] - a)
    if pos > 0:
        answer = min(answer, a - values[pos - 1])
    return answer


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    t, m, q = data[:3]
    values = reachable(t, m)
    print("\n".join(str(distance(values, a)) for a in data[3:3 + q]))


if __name__ == "__main__":
    main()

C++17 程式碼

#include <algorithm>
#include <iostream>
#include <iterator>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int64 t;
    int m, q;
    cin >> t >> m >> q;
    unordered_set<int64> seen;
    seen.insert(t);
    vector<int64> frontier{t};
    for (int depth = 0; depth < m; ++depth) {
        vector<int64> nextFrontier;
        for (int64 y : frontier) {
            int64 x = 2 * y;
            if (seen.insert(x).second) nextFrontier.push_back(x);
            if (y % 3 == 2) {
                x = (2 * y - 1) / 3;
                if (seen.insert(x).second) nextFrontier.push_back(x);
            }
        }
        frontier = std::move(nextFrontier);
        if (frontier.empty()) break;
    }

    vector<int64> values(seen.begin(), seen.end());
    sort(values.begin(), values.end());
    while (q--) {
        int64 a;
        cin >> a;
        auto it = lower_bound(values.begin(), values.end(), a);
        int64 answer = (a >= values[0] ? a - values[0] : values[0] - a);
        if (it != values.end()) answer = min(answer, *it - a);
        if (it != values.begin()) answer = min(answer, a - *prev(it));
        cout << answer << '\n';
    }
}