某個闖關遊戲上有一隻神奇寶貝與兩個可控制左右移動的按鍵。神奇寶貝被安置在僅可左右移動的滑軌上。滑軌分成 $ n $ 個位置,由左到右分別以 $ 0 $ ~ $ n - 1 $ 表示。當遊戲開始時,神奇寶貝從位置 $ 0 $ 開始,遊戲的資訊包含 $ P$ 、 $L $ 與 $ R $ 三個數字,其中 $ P $ 表示所須移至的目標位置 $,L $ 與 $ R $ 則分別表示每按一次左鍵或右鍵後,會往左或往右移動的格子數。
此外,每一個位置 $ x $ 都對應一個瞬間移動位置 $ S(x)$ ;每一次按鍵後,神奇寶貝會先依據按鍵往左或右移動到某個位置 $ x$ ,接著瞬間移動至 $ S(x)$ 。某些點的瞬間移動位置等同原地點,也就是 $ S(x) = x$ ,這些點稱為停留點。開始與目標位置都一定是停留點;此外,每個點的瞬間移動位置都一定是停留點(除非超出界外),也就是不會發生連續瞬間移動的情形。遊戲的目標是以最少的按鍵數操作神奇寶貝由開始位置到達目標位置,此外,在移動過程中不可以超過滑軌的範圍 $[0, n - 1]$ ,否則算闖關失敗;某些點的瞬間移動位置也可能會超出滑軌的範圍,移動到這些點也會導致闖關失敗。
輸入有兩行,第一行有 $ 4 $ 個數字,第 $ 1 $ 個為 $ n$ ,第 $ 2 $ 個為目標位置 $ P$ ,第 $ 3 $ 個為 $ L$ ,第 $ 4 $ 個為 $ R$ ,後三個數字皆為小於 $ n $ 之正整數,且 $ 2 ≤ n ≤ 1e6$ 。
第二行有 $ n $ 個整數,依序是各點的瞬間移動位置 $ S(0), S(1), …, S(n - 1)$ ,
這些數字是絕對值不超過 $ 1e8 $ 的整數。
輸出到達目標位置所需的最少按鍵數,如果無法到達目標位置,則輸出 $ -1$ 。
5 3 1 2 0 3 2 3 5
2
10 8 2 3 0 5 2 3 4 5 6 6 8 9
3
考量 Python 使用者,記憶體限制目前自 64MiB 放寬至 160MiB.
$nevikw39$
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |