# HW01 補充說明

:::info
作業發出後，任何更新將會寫於此

- 3/15 1.2 更新
- 新增 QnA 區段
- 3/16 1.4 更新
- 範例圖的距離為 ~~5~~ --> 6 ， cost 為 23
- 3/16 1.3 更新
- 在提示新增一點提醒
- 規則新增：輸出需要最簡
- 規則提醒：輸出要降序排序
- 3/21 1.3 更新
- 可能會有重複的次方項
- 3/21 Bonus 更新
- 不需完成小實驗
- 3/24 1.4 小提醒
- 只會 allocate pMinPath 本生, pPath 不會 allocate

:::

## 1.1 My String Library

## 1.2 String Calculator

測試資料範圍：
- `pExpr` 中每個運算元之 base 10 均不會超過 `int32_t` 範圍
- `pExpr` 長度不超過 100
- `2 <= base <= 16`

請注意：
- 運算元中 digits 和 base 間的底線 `_` 為半形而非全形
- 題目範例之一 "`ABC_16 + 00001_2`" 中，運算子和運算元間必有空格
- 若結果為 0，不可以加上負號（如 "`0_2`"）
- 若是格式不符合（包含但不限於運算元格式不符、出現 `+`、`-`、`*` 以外的運算子、運算元和運算子間無空格等），請回傳 `-1`
- 建議勿於函式中印出任何內容

You have good TA:

- 可以考慮將所有運算元轉成 base 10，計算完再轉到指定 base 的做法
- 可以將 base 轉換另外用函式撰寫，包含轉成 base 10 或是 base 10 轉成其他 base 的函式

QnA:
> `pExpr` 可能會只包含一個運算元嗎？

可能

> 運算元若是正數，前面多了一個正號是否算格式錯誤呢？

是的，要算格式錯誤，回傳 -1

> 請問要考慮先乘除後加減嗎

需要先乘除後加減，不能從左一路算到右

## 1.3 Chain Rule

規則：
- 保證 `*pResult` 的 size 不超過 $10^3$
- 保證 Power 皆為 uint32_t
- 保證 Coefficient 在計算過程與結果皆為 int32_t
- 保證 `pFy` 和 `pFx` 給的 size 和 pPowers 及 pCoefficients 一致
- 若單筆測資執行時間超過 $10$ 秒會視為錯誤
- (3/16 更新)記得輸出要降序排序
- (3/16 更新)輸出的多項式必須為最簡，也就是 $2x+2x$ 要合併成 $4x$。
- (3/17 更新)化為最簡包含將係數為 0 的項移除，例如:
$2x^3 + 0x^2 + 3x^1 + 0$ 會變成 $2x^3 + 3x^1$
- (3/21 更新)可能會有重複的次方項(如 $2x + 3x^2 + 4x$)

提示：
- 可以把運算拆成 function 來寫，會比較簡單
- 記得處理壞壞的輸入哦(不過題目保證那麼多就只剩下...)
- 可能會有以下情況，你如果想跑 $10^9\times10^9$ 迴圈會跑很久哦
$f(y)=y^2$,$f(x)=x^{10^9}+1$
- (3/16 更新)強烈建議像是上面的 $f(x)$ 不要開 $10^9$ 陣列存，空間會爆掉，也算不完。

參考測資(以下為難度參考，並非正式測資)：
- 國中生微積分：$f(y)=2y$,$f(x)=2x^3-3x+5$
- 高中生微積分：$f(y)=2y^3$,$f(x)=2x^3-3x+5$
- 高中生段考微積分：$f(y)=y^2$,$f(x)=x^{10^9}+1$
- 大學生微積分：$f(y)=2y^3-3y^2+4y-5$,$f(x)=2x^3-3x+5$

這些難度的測資都會出現在正式測資中，且各難度的配分均至少 $2$ 分。

答案可以用網路上的微積分計算機算出來哦

Q&A:

## 1.4 Maze

- 不要想太多，這題沒有在考驗你們複雜的演算法，暴力解必定能解。
- 範例圖的距離為 6 ， cost 為 23
- 我只會 allocate pMinPath 本身, pPath 不會 allocate 喔，請依照長度 allocate 合適的大小

## 1.5 Taiko Music Generator
- **測資皆已上傳完畢，後面不會再傳(時間2024/03/24-13:10)**，就留這些給你們慢慢測試吧，不過如果有人想要我這裡沒整理過的 tja 檔案也歡迎來跟我講，我可以直接把手機版太鼓次郎的整份資料夾給你，目前測資數量：
- sample: 6
- sample(no-chart-json): 26
- sample(special): 9
- 現在除了支援列印 json 檔案格式，也支援txt檔案，如果你們選擇以下輸出格式，檔案副檔名請設定為txt，以作業裡 1.5.2 輸出為例：
:::spoiler Output

    course: 3
    [1, 1.646000]
    [1, 1.822471]
    [2, 1.998941]
    [1, 2.175412]
    [1, 2.351882]
    [1, 2.528353]
    [2, 2.704823]
    [2, 2.881294]

    course: 2
    [1, 1.646000]
    [1, 1.998941]
    [1, 2.351882]
    [2, 2.528353]
    [1, 2.704823]
    [2, 2.881294]

    course: 1
    [1, 1.646000]
    [1, 2.351882]
    [1, 2.704824]
    [1, 3.057765]
    [1, 3.587177]
    [1, 3.940118]
    [1, 4.293059]

    course: 0
    [1, 1.646000]
    [1, 3.057765]
    [1, 4.469530]
    [1, 5.881294]
    [2, 6.587176]

:::
- 如果Hard以上的難度跟不上的話，你們可以先驗證去聽Easy、Normal難度，前面驗證對的話基本上Hard以上的難度都會是驗證正常的，當然還是要去聽啦，或是拿我給你的chart.json去看。
- sample 的譜面檔案我後面會陸續增加，你們會有很多的測資可以測
- 檔案是給你驗證用，你的程式不會涉及到任何檔案的處理
- 作業裡所謂的輸入輸出指的是stdin與stdout，而不是檔案的寫入，所以關於輸入與輸出內容很大很多很可怕，可以查 redirection command，還有檔案的 CRLF 與 LF 的情況你們可能也會用到(也有可能用不到，反正我有遇到)
- 如果你覺得你有寫對但是聽起來有一部分有延遲，有以下兩個原因可以忽視，但是基本上如果音符與音樂之間沒有太大的誤差(一秒之內)，那都還算ok
1. 譜面本身設計問題
2. 小數點精度問題
- Taiko Music Generator 的網站因為伺服器的網路真的是很爛，所以在傳送的時候大概要等一到兩分鐘，如果你們會 python 的話也可以打 source code載下來在local測試，然後可能會有舊音樂的資料被傳回來而誤導你們，你們要注意一下
- sample(special) 資料夾是特別譜面，我不會拿你們的程式測特別譜面，因為如果只按照我給你的資訊來寫程式的話，基本上80%的譜面檔案都可以正確生成chart.json，特別譜面就是在20%的譜面檔案，如果你們有興趣可以挑戰看看
- 如果你們有想要什麼歌的話可以寫信來跟我講，我可以傳測試的檔案給你，你們可以在這[官方網站](https://taiko.namco-ch.net/taiko/tc/songlist)裡面找歌，沒在網站裡的歌也可以問我幫你找找看有沒有

## 1.6 Bonus: _BitInt(N)
- 不需完成小實驗