---
# System prepended metadata

title: Coding Note－Algorithm

---

# Coding Note－Algorithm
此篇為針對演算法之筆記整理，此份筆記內容參考至Horowitx.E(2003), Fundamentals of data structure in C, 13th printing及大學開放式課程。除統整學習內容及概念外，也整理常見之問題討論及解析(c++)，希望能夠過此資訊筆記紀錄學習歷程，並精進程式能力！

## Sorting Algorithm
此部分將簡介各排序演算法的運算邏輯、效能、程式碼以及流程圖，並針對其運算的空間、時間複雜度進行分析。下圖即為複雜度的運算性能比較。Ref:Big-O Complexity Chart http://bigocheatsheet.com/
![image](https://hackmd.io/_uploads/Hk8Ev99IR.png)

另外，以下關於演算法運算邏輯的演示皆用此組範例資料進行(排序由小到大)
```
A[5] = {25, 15, 6, 18, 42}
排序後即為 A[5] = {6, 15, 18, 25, 42}
```


### Bubble Sort
運算邏輯及簡介:氣泡排序法反覆地遍歷陣列，比較相鄰兩個元素。如果順序錯誤(視期望之排序)，就將它們交換。過程反覆進行，直到整個陣列排序完畢。

Time Complexity:
* Best Case: O(n)
* Average: O(n^2)
* Worst Case: O(n^2) 
最壞狀況下，陣列原本是逆著排的，因此n個階層下，須執行n-i-1次(i為外層迴圈迭代次數)。因此，時間複雜度即為(i=0->n−1)∑(n−i−1)=n(n−1)/2

Space Complexity:O(1)

範例測資演示
First pass:
(**25,15**,6,18,42)->(**15,25**,6,18,42) //swap
(15,**25,6**,18,42)->(15,**6,25**,18,42) //swap
(15,6,**25,18**,42)->(15,6,**18,25**,42) //swap
(15,6,18,**25,42**)->(15,6,18,**25,42**) 
Second pass:
(**15,6**,18,25,42)->(**6,15**,18,25,42) //swap
(6,**15,18**,25,42)->(6,**15,18**,25,42)
(6,15,**18,25**,42)->(6,15,**18,25**,42)
Third pass:
(**6,15**,18,25,42)->(**6,15**,18,25,42)
(6,**15,18**,25,42)->(6,**15,18**,25,42)
Fourth pass:
(**6,15**,18,25,42)->(**6,15**,18,25,42)

Code
```
void bubble_sort(int *array)
{
    for (int i = 0; i < n - 1; i++) //n為size of array
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}
```
#### Bubble Sort optimized
修正後的氣泡排序法可避免在陣列已經排序後，仍然接續往下面的階層遍歷，節省了多餘的部分。
Code
```
void bubble_sort_revision(int *array) 
{
    for(int i=0; i<n; i++)
    {
      flag = false;
      for(int j=0; j<n-i-1; j++)
      {
         if(array1[j]>array1[j+1])
         {
            flag = true;
            int temp = array1[j+1];
            array1[j+1] = array1[j];
            array1[j] = temp;
         }
      }
      //check whether it's sorted or not
      if(!flag){ 
         return;
      }
   }
}
```


### Quick Sort
運算邏輯及簡介: Quicksort採用的是Divide-and-Conquer策略，Quicksort將在數列中找一個數字作為基準 (pivot)，把該數列中所有比基準數小的數字都放在左邊、比基準數大的數字都放在右邊。接者，再讓左右兩個子陣列各自做排序，當左、右子陣列排完時，整個排序也就結束。

Time Complexity:
* Best Case: O(nlogn)
    Best case為pivot恰好將陣列分成切割兩等分(比pivot大以及小的一樣多)
    $T(n)=2×T(n/2)+c×n$ //partition time
        $=...+n×T(1)+\log_2(n)×c×n$
* Average: O(nlogn)
* Worst Case: O(n^2) 
    Worst case為pivot恰好為陣列的最大值或是最小值
    $T(n)=T(n-1)+T(0)+c×n=T(1)+c×(2+3+...+n)=c×(n+2)(n-1)/2$

Space Complexity:O(logn)
 
範例測資演示(以首項作為pivot演示)
(25,15,6,18,42)->(15,6,18,25,42) //taking 25 as pivot
* left (15,6,18)->(6,15,18) //taking 15 as pivot
    left:(6)->(6) right:(18)->(18) //sorted
* right (42)->(42) //sorted

Combined:(6,15,18,25,42)

Code
```
void Quicksort(vector<pair<int, int>> &A, int left, int right)
{
    int l = left + 1, r = right;
    if (left >= right)
        return;
    int pivot = A[left].first;
    while (1)
    {
        while (l <= right)
        {
            if (A[l].first > pivot)
                break;
            l++;
        }
        while (r > left)
        {
            if (A[r].first < pivot)
                break;
            r--;
        }
        if (l > r)
            break;
        swap(A[l], A[r]);
    }
    swap(A[left], A[r]);
    Quicksort(A, left, r - 1);
    Quicksort(A, r + 1, right);
}
```
#### Quicksort revision 
優化方法：和Bubble sort revision相同，此優化的目的也是為了避免Worst case的發生，以提升此演算法的效率。詳細計算可見以下資料來源(Ref:https://kopu.chat/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F-quick-sort/)
1. Middle-of-three solution
    (1) 令 middle = (left + right) /2
    (2) 比較 A[left]、A[middle] 與 A[right] 三筆資料，排出中間        值，將中間值再與 A[left]做交換
    (3) 讓現在新的 A[left] 作為 pivot

    假設 pivot 位置在 n 筆資料中的 n/10 與 9n/10 之間：
    T(n) = c*n + T(n/10) + T(9n/10)
    因此，此方法的時間複雜度可以收斂到 O(nlogn)
    
2. Median-of-Medians solution

    (1) 將 n 個資料分成 n/5 個堆，每堆有 5 個資料 (可能會有 1 個堆        的資料不到 5 個) ，花 O(n) 時間。

    (2)每堆由小到大做排序。排序一堆花 O(5^2) 時間，可以想成 O(1) 常        數。所以當有 n/5 堆排序時，共花 O(n) 時間。

    (3)排序完將每堆中位數資料作為該堆pivot。在這 n/5 堆中，遞迴套          用quicksort，求得中位數 k。 k 即為 median-of-medians ，        此步驟花費時間 T(n/5)。

    (4)以 k 作為 pivot 重新將整堆做排序，花 O(n) 時間。

    (5)至少有一半的組（不包括 pivot 自己及不到 5 個資料的組）每組將        至少有 3 個資料大於或等於 pivot。這保證了 pivot 𝑘 將陣列分        成兩部分，每部分大小至多為7n/10。
    
    遞迴關係式即為T(n)<=T(n/5)+T(7n/10)+O(n)，因此此方法在           worst case時，時間複雜度仍能降為O(n)。

### Selection Sort
運算邏輯及簡介:選擇排序法將在陣列中尋找最小值，並將其交換至陣列的第一個元素，並將剩餘元素往右推直到所有元素排序完畢。

Time Complexity:
* Best Case: O(n^2)
    因每個迴圈中所有元素須被遍歷過，以找出最小值，因此時間複雜度為n^2
* Average: O(n^2)
* Worst Case: O(n^2) 

Space Complexity:O(1)

範例測資演示:
(25,15,6,18,42)->(6,25,15,18,42) //將找到的最小值放至左側
(6,25,15,18,42)->(6,15,25,18,42)
(6,15,25,18,42)->(6,15,18,25,42)
(6,15,18,25,42)->(6,15,18,25,42)

Code:
```
#include <bits/stdc++.h>
using namespace std;

void selectionSort(vector<int>& A) {
    int n = A.size();
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[min]) {
                min = j;
            }
        }
        swap(A[min], A[i]);
    }
}
```

### Insertion Sort
運算邏輯及簡介: Insertion sort將資料列分為已排序及未排序兩部分，每個步驟皆從從未排序資料中，挑選一個元素並將其插入已排序資料中，直到所有資料排序完成。

Time Complexity:
* Best Case: O(n)
    最好的情況中，此陣列已排序完成，因此每一遍歷到的元素皆插入至最後即可。
* Average: O(n^2)
* Worst Case: O(n^2) 

Space Complexity:O(1)

範例測資演示:
(25,**15**,6,18,42)->(**15**,25,6,18,42) //以25為已排序、剩餘為未排序
(15,25,**6**,18,42)->(**6**,15,25,18,42) //6加入已排序資料
(6,15,25,**18**,42)->(6,15,**18**,25,42) //18加入已排序資料
(6,15,18,**25**,42)->(6,15,18,**25**,42) //插入後順序不變
(6,15,18,25,**42**)->(6,15,18,25,**42**)

Code:
```
void insertionSort(vector<int>& A) {
    int n = A.size();
    for (int i = 1; i < n; ++i) {
        int key = A[i];
        int j = i - 1;
        
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j]; //move bigger elements back
            j = j - 1; 
        }
        A[j + 1] = key; //move key into the sorted section
    }
}
```


### Merge Sort
運算邏輯與簡介: Merge sort 採用Divide and Conquer，將資料對半切分直到每個子陣列僅含一個元素（即已排序），再將子陣列依序合併、排序（子陣列首元素較小的排於前），直到資料列重組完成。

Time Complexity:
* Best Case: O(nlogn)
* Average: O(nlogn)
* Worst Case: O(nlogn) 

Space Complexity:O(n)

```
void merge(vector<int>& A, int left, int mid, int right) {
    vector<int> L(A.begin() + left, A.begin() + mid + 1);
    vector<int> R(A.begin() + mid + 1, A.begin() + right + 1);

    int i = 0, j = 0, k = left;

    while (i < L.size() && j < R.size()) {
        if (L[i] <= R[j]) A[k++] = L[i++];
        else A[k++] = R[j++];
    }
    while (i < L.size()) A[k++] = L[i++];
    while (j < R.size()) A[k++] = R[j++];
}

void mergeSort(vector<int>& A, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid + 1, right);
    merge(A, left, mid, right);
}

```

### Heap Sort
運算邏輯與簡介: Heap sort 利用 Heap Tree 的資料結構來排序，先將資料構建成最大堆（Max Heap），此時根節點為最大值。接著將根節點（最大值）與最後一個節點交換，並從堆中移除，再對剩下的資料重新調整為最大堆，重複此過程直到結束。
*原地排序法、不須其他空間，且非穩定排序

Time Complexity:
* Best Case: O(nlogn)
* Average: O(nlogn)
* Worst Case: O(nlogn) 

Space Complexity:O(1)

```
void heapify(vector<int>& A, int n, int i) {
    int largest = i;         
    int left = 2 * i + 1;    
    int right = 2 * i + 2;   

    if (left < n && A[left] > A[largest]) largest = left;
    if (right < n && A[right] > A[largest]) largest = right;

    if (largest != i) {
        swap(A[i], A[largest]);
        heapify(A, n, largest); // 遞迴調整子樹
    }
}

void heapSort(vector<int>& A) {
    int n = A.size();
    
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(A, n, i);

    // 將堆頂元素與最後一個元素交換，並調整剩餘堆
    for (int i = n - 1; i > 0; i--) {
        swap(A[0], A[i]); 
        heapify(A, i, 0);
    }
}

```

### C++ STL sorting
運算邏輯及簡介: C++之函式庫 algorithm 中，即包含 std::sort 的功能，時間複雜度是 O(nlogn)，相較於初階演算法的小，且使用上也較高階演算法容易許多。關於STL的細節可見資料結構篇。

解析: 此函數在 C++ 中使用一種稱為 Introsort (a varient of Quicksort)，結合了QuickSort、InsertionSort及Heapsort以達到較好的performance。Introsort 設計為在QuickSort超過一定遞歸深度時切換至Heapsort，確保在最壞情況時間複雜度保持在 O(N log N)，避免Quicksort最壞情況下 O(N^2) 複雜度。

Time Complexity:
* Best Case: O(nlogn)
* Average: O(nlogn)
* Worst Case: O(nlogn) 

Space Complexity:O(logn)

Usage
```
sort(begin,end,function);
```
其中funciton可為自定義之函數，可視情況定義想要排序的依據。
Examle:Using compare function
```
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath> //for abs function
using namespace std;

bool compare(int a, int b){
    return abs(a) < abs(b);
}

int main() {
    vector<int> ex = {-9, 3, -5, 1, -4, 7, -2, 6, 8};
    
    sort(ex.begin(), ex.end(),compare);

    cout << "Sorted vector by absolute value: ";
    for(int num : ex) 
        cout << num << " ";
    cout << "\n";
    return 0;
}
```
## Searching Algorithm

### Linear Search (Sequential search)
運算邏輯及簡介:一種基本運用BruteForce的方法，逐一遍歷所有資料，直到找到預搜尋的目標為止

Time Complexity: O(n)
Space Complexity: O(1)

Code
```
int linearSearch(const vector<int>& A, int key) {
    for (int i = 0; i < A.size(); ++i) {
        if (A[i] == key) 
            return i;
    }
    return -1; //not find
}
```

### Binary Search
運算邏輯及簡介: 將資料排序後，取中間值並判斷欲尋找的數字大於或是小於中間值，再一層一層反覆向下找，當範圍的左右兩邊收斂到相等時，此即為欲尋找的數字位置。

Time Complexity: O(logn)
Space Complexity: O(1)-迭代, O(logn)-遞歸


範例資料演示:

Code
```
int binarySearch(const vector<pair<int, int>> &A, int low, int high, int key)
{
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (A[mid].first == key)
            return A[mid].second;
        if (A[mid].first < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}
```
#### Revision－Interpolation Search
優化方法: 改進的二分搜尋，適用於均勻分佈的排序數組。插值演算法估計目標元素可能出現的位置，並根據此猜測進行搜尋。

Time Complexity: 
* Best Case: O(loglogn)
* Worst Case: O(n)

Space Complexity: O(1)

範例資料演示:

Code
```
int interpolationSearch(const vector<int>& A, int key) {
    int low = 0, high = A.size() - 1;

    while (low <= high && key >= A[low] && key <= A[high]) {
        if (low == high) 
            if (A[low] == key) return low;

        //guess the possible position
        int pos = low + ((double)(high - low) / (A[high] - A[low])) * (x - A[low]);

        if (A[pos] == x) 
            return pos;
        else if (A[pos] < x) 
            low = pos + 1;
        else 
            high = pos - 1;
    }
    return -1; 
}

```

### Jump Search
運算邏輯及簡介: 跳著間續檢查元素，而非逐一線性搜尋。從第 √n  個元素開始，每次跳 √n 個元素，直到找到比目標大的元素，然後在上一跳的區間內線性搜尋。此方法適用於資料量大、但無法使用二分搜尋的情況。

Time Complexity: O(sqrt(n))
Space Complexity: O(1)

Code:

```
int jumpSearch(const vector<int>& A, int key) {
    int n = A.size();
    int step = sqrt(n);
    int prev = 0;

    // 找到大於等於 key 的區塊
    while (A[min(step, n) - 1] < key) {
        prev = step;
        step += sqrt(n);
        if (prev >= n) return -1;
    }

    // 線性搜尋該區塊
    while (A[prev] < key) {
        prev++;
        if (prev == min(step, n)) return -1;
    }
    if (A[prev] == key) return prev;
    return -1;
}
```


## Greedy Method
此部分統整幾個常見的貪心演算法問題，針對題目討論解題策略及思路分析。
### Minimum Spanning Tree(MST)
問題簡介：最小生成樹是圖中一棵包含所有節點、且邊的總權重最小的生成樹，不包含任何環，並確保節點間保持連通。

#### Kruskal's method
運算邏輯與方法：將所有邊依權重排序，並使用並查集判斷是否形成環，如果加入新的邊不會形成環，則將該邊加入最小生成樹（MST）並合併集合，重複直到選到𝑛-1條邊。（針對一個n個點的圖）
應用：適合邊少的圖，先排序邊再逐步加入。
```
#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e5 + 5;
int par[mxn];
int sz[mxn];
void init()
{
    for (int i = 0; i < mxn; i++)
    {
        par[i] = i;
        sz[i] = 1;
    }
}
int find(int x)
{
    if (par[x] == x)
        return x;
    return par[x] = find(par[x]);
}
void merge(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return;
    if (sz[y] < sz[x])
        swap(x, y);
    par[x] = y;
    sz[y] += sz[x];
}
struct Edge
{
    int u, v, w;
};
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int main()
{
    int n, m;
    while (cin >> n >> m)
    {
        vector<Edge> vec;
        init();
        for (int i = 0; i < m; i++)
        {
            int a, b, w;
            cin >> a >> b >> w;
            vec.push_back({a, b, w});
        }
        int cnt = n - 1;
        sort(vec.begin(), vec.end(), cmp);
        long long ans = 0;
        for (Edge e : vec)
        {
            if (find(e.u) != find(e.v))
            {
                merge(e.u, e.v);
                ans += e.w;
                cnt--;
            }
        }
        if (cnt != 0)
            cout << -1 << '\n';
        else
            cout << ans << '\n';
    }
}

```

#### Prim's method
運算邏輯與方法：選定起始點，並用優先佇列維護權重最小者。每次從優先佇列取出最小邊，若該邊的終點未在 MST 中，將新點加入，並將其所有鄰接邊加入優先佇列，直到所有節點都包含於其中。
應用:適合點多的圖，從一點開始擴展 MST。
```
#include <bits/stdc++.h>
using namespace std;

const int mxn = 1e5 + 5;
vector<pair<int, int>> adj[mxn]; // {neighbor, weight}
bool visited[mxn];

long long prim(int start, int n) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    long long total_weight = 0;
    int count = 0;

    while (!pq.empty() && count < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        total_weight += w;
        count++;

        for (auto [v, wt] : adj[u]) {
            if (!visited[v])
                pq.push({wt, v});
        }
    }

    if (count < n) return -1; // 圖不連通
    return total_weight;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    cout << prim(0, n) << endl;
}

```

### Interval Scheduling Problem
問題簡介：Interval Scheduling是一種在存在大量區間的情況下，有效率地找出一組最大相容子集（Largest Compatible Subset）的演算法。（即資源最大化的概念）

方法：排列結束時間，選擇結束時間較早的活動，逐一遍歷活動，重複直到結束。


Code：
```
#include <bits/stdc++.h>
using namespace std;

struct Activity {
    int start, end;
};

bool cmp(Activity a, Activity b) {
    return a.end < b.end;
}//compare the ending time

int intervalScheduling(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), cmp); //sort by ending time
    int count = 0, currentTime = 0;

    for (const auto& act : activities) {
        if (act.start >= currentTime) { //check if valid or not
            count++;
            currentTime = act.end;
        }
    }

    return count;
}

int main() {
    int n;
    cin >> n;
    vector<Activity> acts(n);
    for (int i = 0; i < n; i++)
        cin >> acts[i].start >> acts[i].end;

    cout << intervalScheduling(acts) << endl;
}
```

## Dynamic Programming
將主要問題拆解為小問題後，找出遞迴關係，一步步往回推解決主要問題，常用於解決最佳化問題。
### Optimal Substructure
概念:大問題的答案，不用重新計算，而從子問題的答案中將大問題答案給尋找並拼湊出來。可分為以下兩步驟，包括子問題的數量，及子問題不同的分類可能。
### Overlapping subproblems
概念:子問題持續在重複，反覆相同的運算，即可得出大問題的解答

### Bottom-up
運算邏輯與方法:找出遞迴關係式後，找出計算順序來避免遞迴以完成
算法。
以階梯問題為例
```
#include<bits/stdc++.h>
using namespace std;
int main(){
     int F[100000];
     int n;
     cin>>n;
     F[1] = 1, F[2] = 2;
     for(int i=3; i<=n; i++){
         F[i] = F[i-1] + F[i-2];
     }
     cout<<F[n];
     return 0;
}
```

### Top-down Memoization
運算邏輯與方法:不找計算順序，而是直接依照遞迴關係式找遞迴，並以memo(備忘錄)紀錄以計算過的資料，以增加撰寫的容易程度。

以階梯問題為例
```
#include<bits/stdc++.h>
using namespace std;
int F[100] = {0};
int stair(int n){
    if(F[n]>0) return F[n]; //check memo
    F[n] = stair(n-1) + stair(n-2); //record to memo
    return F[n];
}
int main(){
    int n;
    cin>>n; 
    F[1] = 1, F[2] = 2;
    cout<<stair(n);
    return 0;
}
```


---


以下為幾個常見的DP問題
### Knapsack problem (0/1背包問題)
原敘述: 有n種物品，物品j的重量為w_j，價值為p_j。假定所有物品的重量和價格都是非負的。背包所能承受的最大重量為W，試得到在承重的最大重量內可裝的最大價值。

剖析: 此題的命名之所以為0-1是因為每種物品只能選擇0個或1個，不能夠分割，因此無法適用Greedy Method，只放單位價值最高的物品可能會捨去其餘總和更大的情況。(fractional knapsack problem即適用)

動態規劃(二維)解法
```
dp[i][j]:限重j的情況，放入1~i的物品之最大價值
W[i]第i個物品重量、V[i]第i個物品價值

if(j>=W[i])
    dp[i][j]=max(dp[i-1][j],dp[i-1][j-W[i]]+V[i]);
else 
    dp[i][j]=dp[i-1][j];
```
限重大於等於第i物品的情況下，第i個物品即有可能放入背包中，因此比較不放此物品及放入此物品後之價值比較，選擇最大值即為此情況下之最佳解。反之，若無法放入此物品，即為i-1時之值。

以下以i=4, j=5繪製表格dp舉例
W={0,1,2,4,5}, V={0,3,2,8,5}
| i/j | 0 | 1 | 2 | 3 | 4 | 5 |
| --- | --| - |-  |-- |-- |-- |
| 0   | 0 | 0 | 0 | 0 | 0 | 0 |
| 1   | 0 | 3 | 3 | 3 | 3 | 3 |
| 2   | 0 | 3 | 3 | 5 | 5 | 5 |
| 3   | 0 | 3 | 3 | 5 | 8 |11 |
| 4   | 0 | 3 | 3 | 5 | 8 |11 |

### LCS（Longest Common Subsequence）
方法:假設有三字串分別為A={a~1~, a~2~,....,a~i~}, B={b~1~, b~2~,....,b~j~}, C={c~1~, c~2~,....,c~k~}，其中目標為在AB字串中找到最大的共用字串，而假設字串C為兩者的共用字串。從最後的字母開始討論，逐一推至完整數列，共可分為以下三種情況:
1. a~i~=b~j~
    若最後一個字元相同，則只需考慮A~i-1~及B~j-1~
3. a~i~!=b~j~且c~k~!=a~i~
如果A與C字串的最後一個字不同，則共同字串必在B~j~及A~i-1~之間
4. a~i~!=b~j~且c~k~!=b~j~
如果A與B字串的最後一個字不同，則共同字串必在A~j-1~及A~i~之間

此三種情況即為子問題的三種可能，接下來只需表格化在A及B各元素間
表格化字串共同數列，假設兩字串A、B分別為A={X,Y,Z,X,Y,X},B={Y,Z,X,Z,Y,X}，有兩

依此規則可繪製成以下圖表
| i/j  | 0   | 1(X) | 2(Y) | 3(Z) | 4(X) | 5(Y) | 6(X) |
|------|-----|------|------|------|------|------|------|
| 0    | 0   | 0    | 0    | 0    | 0    | 0    | 0    |
| 1(Y) | 0   | 0    | 1    | 1    | 1    | 2    | 2    |
| 2(Z) | 0   | 0    | 1    | 2    | 2    | 2    | 2    |
| 3(X) | 0   | 1    | 1    | 2    | 3    | 3    | 3    |
| 4(Z) | 0   | 1    | 1    | 2    | 3    | 3    | 3    |
| 5(Y) | 0   | 1    | 2    | 2    | 3    | 4    | 4    |
| 6(X) | 0   | 1    | 2    | 2    | 3    | 4    | 5    |

