a304: 3. 石窟探險[2022年10月APCS]
標籤 : APCS dfs 樹
通過比率 : 13人/13人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-11-04 15:10

內容

有一組探險隊要去一個樹狀結構的石窟內探險,該石窟內有 n 個石室,第 i 個石室有一個編號 ai,若 ai 為偶數則會有 2 條分支(左分支和右分支),若 ai 為奇數則有 3 條分支(左分支、中分支和右分支)。

探險隊想要紀錄這個石窟的結構,每次只要第一次走到一個新的石室,就會將該石室的編號記錄在紙上,並由左到右依序走訪該石室的分支們,若走到一條死路則會在紙上紀錄一個數字 0,若該石室已經走完所有分支則退回到上一個石室,走訪完整個石窟後在紙上得到上一個數字序列。

探險隊回到基地後忘記計算了這個石窟內所有相鄰的石室編號相差取絕對值的總和,請幫助探險隊從紙上的序列推算出該數值。

輸入說明

輸入一個整數個數不超過 106 的整數序列,石室的編號不超過 105,並保證造出來的樹深度不超過 40。

輸出說明

輸出一個整數代表這個石窟內所有相鄰的石室編號相差取絕對值的總和,答案大小有可能會超過 231

範例輸入 #1
2 6 0 8 14 0 0 0 10 0 4 0 0
範例輸出 #1
26
範例輸入 #2
5 2 10 0 0 0 8 0 0 17 0 0 0
範例輸出 #2
26
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1K
提示 :

 範例測資一

|2 - 6| + |6 - 8| + |8 - 14| + |2 - 10| + |10 - 4| = 26

測資二

|5 - 2| + |2 - 10| + |5 - 8| + |5 - 17| = 26

標籤:
APCS dfs 樹
出處:
zerojudge演算法海牛 [管理者: ]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」