# APCS 202306 第3題 磁軌移動序列 (ZeroJudge k733)
[ZJ題目連結](https://zerojudge.tw/ShowProblem?problemid=k733) (此題解先說明方法再揭示範例程式，包含python與C++)
###### tags: `apcs`
## 方法說明
這題要計算在一連串磁軌編號之間移動的距離總和。一個磁軌編號以Txx表示，其中xx是10~99的數字，例如T12T34表示先移動到12號磁軌接著移動到34號磁軌，題目中說明一開始的位置在10號磁軌，因此，如果輸入是T12T34，則移動距離是$|12-10|+|34-12|=2+22=24$。
比較困難的是輸入字串中可以包含迴圈，迴圈以Ly...E表示，其中y是1~9，表示迴圈重複y次，而...則是重複的部分。例如L2T12T34E就是T12T34重複兩次，也就是T12T34T12T34，所以輸入此字串的移動距離為$|12-10|+|34-12|+|12-34|+|34-12|=68$。
要展開一個迴圈看起來還不是太難，真正困難的是迴圈中還可以有迴圈，例如L3T20L2T12T34ET15E。此例中外層迴圈L3...E，中間的必須重複3次，中間的是T20L2T12T34ET15分成T20與L2T12T34E與T15，其中L2T12T34E是T12T34重複兩次=T12T34T12T34，所以整個字串是T20T12T34T12T34T15重複3次。
看似複雜的讓人昏頭了，但其實如果我們稱此種字串為S字串，則S字串總歸就是兩種樣子：
* S字串 = Txx + S字串
* S字串 = Ly + S字串 + E

此處的+是字串連接的意思，這是一種遞迴方式定義的結構。要解遞迴定義的結構當然以遞迴程式最為合適。我們先來看看，所求的距離要如何計算。

對於第一種形式Txx+S的結構，距離的計算就是相鄰編號差的絕對值，多個Txx連接時，我們可以用變數記錄前一項編號與目前的編號，一路滑過去過去，不斷的計算差值並予以加總。

對於第二種迴圈結構Ly，我們需要三個資料$(cost,head,tail)$，其中$cost$為迴圈內部距離的總和、$head$是迴圈內的第一個磁軌編號、而$tail$是迴圈內的最後一向磁軌編號。迴圈內的總移動距離就可以計算為$cost\times y+|head-tail|\times (y-1)$，因為內部重複$y$次，而頭尾相鄰$y-1$次。

根據以上分析，我們的遞迴程式中就要計算cost,head,tail三個值。我們設計一個遞迴的副程式，主要流程如下：

輸入字串track與目前位置idx放在global變數
副程式 seq() 將傳回cost,head,tail
while true:
    head = tail = -1 // 初設-1表示沒有
    total = 0 // 紀錄目前距離總和
    if end of track or track[idx]=E then
        update idx and return
    if track[idx]=='T' then
        計算目前編號
        update idx,head,tail,total
    if track[idx]=='L' then 
        計算迴圈次數y並更新idx
        遞迴呼叫seq()取得迴圈內部距離，第一個與最後編號
        update head,tail,total
    end of while

**小技巧：如何計算第一個head與最後一個編號tail**
我們可以初設tail = -1，每次處理時，如果tail==-1就表示目前為第一個，此時便設定head。同時，每次都將目前的編號設為tail，離開時tail就是最後被設定的編號，也就是最後一個編號。

## 完全解
直接說明完全解的範例程式。首先是Python的程式碼。Python的副程式可以回傳多個值，所以我們直接讓他回傳cost, head與tail。第8行開始無窮迴圈，每次依照字串目前的內容track[idx]來做不同的處理，首先判斷字串是否已經結束(第9行)，若是，則回傳結束。然後是'T'的情形(第11行)，先抓取後兩位數字，然後更新資料。如果是'L'的情形(第17行)，先抓取迴圈次數，然後遞迴呼叫，再更新資料。最後是'E'的情形(第25行)。每一種狀況都要記得更新idx也就是下一個字串處理位置。
主程式只要輸入字串後呼叫此副程式就可以了，不要忘了加上起始位置10的距離。
### Python code

track = input()
idx=0
# return cost and head and tail
def seq():
    global track,idx
    total = 0 
    head = tail = -1
    while True:
        if idx >= len(track): # end of input
            return total,head,tail
        if track[idx]=='T':
            t = int(track[idx+1:idx+3])
            idx += 3
            if tail<0: head = t #first track
            else: total += abs(tail-t)
            tail = t
        elif track[idx]=='L':
            t = int(track[idx+1])
            idx += 2
            cost,h,e = seq() #recursive find a seq
            if tail<0: head = h
            else: total += abs(tail-h)
            tail = e
            total += cost*t+abs(h-e)*(t-1)
        else: # End of loop
            idx += 1
            return total,head,tail
    #end while
#end seq

total,h,e = seq()
print(total+abs(10-h))

### C++ code
以下是C\++的程式碼。C++的副程式只能回傳一個值，所以這裡我們讓他回傳cost，而head與tail則用傳址參數的方式將更新後的值回傳。第11行開始無窮迴圈，每次依照字串目前的內容track[idx]來做不同的處理，首先判斷字串是否已經結束(第12行)，若是，則回傳結束。然後是'T'的情形(第13行)，先抓取後兩位數字，然後更新資料。如果是'L'的情形(第19行)，先抓取迴圈次數，然後遞迴呼叫，再更新資料。最後是'E'的情形(第28行)。每一種狀況都要記得更新idx也就是下一個字串處理位置。
主程式只要輸入字串後呼叫此副程式就可以了，不要忘了加上起始位置10的距離。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int idx=0;
string track;
// return cost and head and tail
ll seq(int &head, int &tail) {
    ll total = 0, t;
    head = tail = -1;
    while (true) {
        if (idx>=track.length()) return total;
        if (track[idx]=='T') {
            t = stoi(track.substr(idx+1,2));
            idx += 3;
            if (tail<0) head = t;
            else total += abs(tail-t);
            tail = t;
        } else if (track[idx]=='L') {
            t = stoi(track.substr(idx+1,1));
            idx += 2;
            int h,e;
            ll cost = seq(h,e);
            if (tail<0) head = h;
            else total += abs(tail-h);
            tail = e;
            total += cost*t+abs(h-e)*(t-1);
        } else { // E
            idx += 1;
            return total;
        }
    }
}

int main() {
    int xx,i,j;
    cin >>track;
    ll total = seq(i,j);
    total += abs(10-i);
    cout << total <<endl;
    return 0;
}

## 非遞迴版本
這題想要考的就是遞迴，所以遞迴版本應該在考試時可以得到100分。不過在ZeroJudge上的測資有包含迴圈層數非常大的情況，Python有遞迴層數的限制(default=1000)，因此Python的遞迴版本在ZJ上只能得到80分，以下我們提出一個非遞迴的Python版本。
基本上，**每一個遞迴程式背後都有一個堆疊**。所以利用堆疊就可以寫出非遞迴的版本。主要的觀念是一樣的，我們沿著字串從前往後掃過去，我們時時記錄著head,cost,tail三個值。
Python的list當堆疊非常方便，append()就是尾端加入，pop()就是取出並刪除最後一個。此外list中不必相同型態，可以同時有的元素是整數而有的元素是list。
stk是我們要記錄用到的堆疊，第3行先放個-1是為了省掉後面檢查堆疊是否為空。另外再用一個loop也是當作堆疊，紀錄迴圈的圈數。
當碰到迴圈的開頭時(第7行)，我們在堆疊上放個-1當作迴圈的界線，然後將圈數抓出來放入loop中(第9行)。如果碰到的是'T'，我們抓出編號t後，要檢查前方是否為分界，也就是這個是否是迴圈或全體的第一個，如果是第一個，我們在堆疊中放上[t,0,t]，意思是頭尾都是t，距離總和=0。如果不是第一個，我們就將目前編號併入之前計算的結果，也就是更新距離總和以及tail。
如果是'E'，也就是迴圈結尾，我們從loop中取出此次迴圈重複數，並從stk中取出head,cost,tail，計算此迴圈的距離總和後，與T的狀況一樣，看看是否要併入前面的資料中。
最後的答案就在堆疊的最後一個，但不要忘了加上起始位置10的距離。

# stack, non-recursive
s = input()
stk = [-1] #sentinel
loop = [] #loop times of the previous loop
i = 0
while i<len(s):
    if s[i]=='L': #loop start
        stk.append(-1) # delimiter
        loop.append(int(s[i+1])) #loop times
        i += 2
    elif s[i]=='T':
        t = int(s[i+1:i+3])
        i += 3
        if stk[-1]==-1: #first of the loop
            stk.append([t,0,t]) # (head, cost, tail)
        else: #merge with previous track
            h,c,e = stk[-1]
            stk[-1] = [h,c+abs(e-t),t]
    else: # End of loop
        i += 1
        w = loop.pop()
        h,c,e = stk.pop()
        c = c*w + abs(h-e)*(w-1)
        stk.pop() #pop delimiter (-1)
        if stk[-1]==-1: #no previous
            stk.append([h,c,e])
        else: #merge with previous (head,cost,end)
            stk[-1][1] += c + abs(stk[-1][2]-h)
            stk[-1][2] = e
            
print(stk[-1][1]+abs(10-stk[-1][0]))