考拉茲距離 (APCS 2026-11 中高級)

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

• 如果 \(n\) 是奇數，\(n\) 變成 \(\dfrac{3n+1}{2}\)。
• 如果 \(n\) 是偶數，\(n\) 變成 \(\dfrac{n}{2}\)。

（\(n\) 是奇數時 \(3n+1\) 是偶數，所以換出來的數仍是正整數。）例如 \(21\) 是奇數，做一次操作變成 \((3 \times 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, \ldots, a_q\)，代表每筆詢問給的數。

限制

• \(1 \le t \le 10^9\)
• \(0 \le m < 32\)
• \(1 \le q < 10^4\)
• \(1 \le a_i \le 10^{18}\)

輸出格式

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

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

11 3 3
16 88 200

範例輸出 1

2
0
112

範例解釋 1

\(t = 11\)、\(m = 3\)。依照剛好要做幾次操作才會變成 \(11\)，可行的數分成下面幾組：

例如 \(29\) 是奇數，做一次操作變成 \(44\)，再做兩次依序變成 \(22\)、\(11\)。

• \(a_1 = 16\)：最近的可行數是 \(14\)，答案是 \(16 - 14 = 2\)。
• \(a_2 = 88\)：\(88\) 在上面的表裡（做 \(3\) 次操作會變成 \(11\)），答案是 \(0\)。
• \(a_3 = 200\)：沒有比 \(200\) 大的可行數，比它小的之中最大的是 \(88\)，答案是 \(200 - 88 = 112\)。

範例輸入 2

5 4 5
1 9 20 27 100

範例輸出 2

2
1
0
1
20

範例解釋 2

\(t = 5\)、\(m = 4\)。依照剛好要做幾次操作才會變成 \(5\)，可行的數分成下面幾組：

例如 \(13\) 依序變成 \(20\)、\(10\)、\(5\)，做 \(3\) 次操作會變成 \(5\)。

• \(a_1 = 1\)：比所有可行數都小，最近的是 \(3\)，答案是 \(2\)。
• \(a_2 = 9\)：最近的可行數是 \(10\)，答案是 \(1\)。
• \(a_3 = 20\)：\(20\) 在上面的表裡（做 \(2\) 次操作會變成 \(5\)），答案是 \(0\)。
• \(a_4 = 27\)：最近的可行數是 \(26\)，答案是 \(1\)。
• \(a_5 = 100\)：沒有比 \(100\) 大的可行數，最近的是 \(80\)，答案是 \(20\)。

題目來源

APCS 2026 年 11 月中高級實作題第 3 題。

官方未公布題本，題敘參考 ecc〈APCS 2026 11月中高級〉 整理，細節可能與正式試題有出入。