# Ch2 解題指引

## 找出最小的完全平方數

### 解題思路
以下想法有其中兩種是可行的，一種會超時（TLE），猜猜看是哪一個！

#### ==想法一==
- 使用`for`迴圈，從 $k$ 位數的第一個數，檢查到 $k$ 位數的最後一個數。
- 每檢查到一個數，就看看他是否符合「各位數字皆為偶數」且「為完全平方數」。若同時滿足兩個條件，即為所求。

#### ==想法二==
- 設 $m$ 為起始數字，由 $m = 2$ 開始，檢查 $m^2$ 是不是 $k$ 位數，又是否符合「各位數字皆為偶數」這個條件。
- 每次`m += 2`，若 $m^2$ 為第一個符合條件的 $k$ 位數字，則記錄下來，此即所求。

#### ==想法三==
- 找出 $k$ 位數中最小的偶數 $e$。
- 由 $\lceil{\sqrt{e}}\rceil$ 開始，一個一個數字檢查，檢查其平方數是否符合「各位數字皆為偶數」，符合的話即為所求。
- 另外可使用加速條件：偶數的平方數尾數必為0, 4, 6。

### 引導問題

:::spoiler **Q. 是哪個想法會超時呢？**
A. 答案是想法一！因為`a、b`之間的數字，在位數`k`較大的時候，檢查了太多不必要的數字。
已知位數限制為 $0 < k \leq 10$，在最極端的狀況：$k=10$，需要檢查的數字個數，量級到了 $10^9$ ~ $10^{10}$ 之間，顯然會超過時間限制。
相較之下，想法二、三只檢查了「完全平方數」，平方後不超過 10 位數的數字，最大不超過 $10^5$。
:::
:::spoiler **Q. 如何判斷一個數是否為 k 位數？**
A. 有兩種方法。

- [法一] 使用`while`迴圈處理整數變數

宣告一個總和變數，只要除以 10 不為 0 就 +1。迴圈總共執行幾次，就是幾位數。

- [法二] `string`的`size()`

可以使用 C++ 11 中的`stoi`函式。先將一個數字轉換成字串（`string`），再用字串長度判斷位數。若你是使用code::blocks撰寫程式，需要手動調整使用的編譯器版本，具體作法可參考[這裏](https://stackoverflow.com/questions/18174988/how-can-i-add-c11-support-to-codeblocks-compiler)。

:::

::: spoiler **Q. 如何判斷一個數的各位數字都是偶數？**
A. 承上，使用迴圈檢查每一個位數，確認都能被 2 整除即可。具體如何實作呢？你可以宣告一個布林變數`is_all_even`，初始值為`true`，只要有一個位數的數字為奇數，就把`is_all_even`設為`false`，然後結束迴圈，不用再繼續檢查下去。

bool is_all_even = true;  // 意義：各位數字是否都是偶數
    while(...){   // 使用迴圈檢查每一位數字
        if(...){  // 只要發現有一個位數是奇數
            is_all_even = false; 
            break;
        }
        ...
    }

若要將其改寫為自訂函式，回傳資料型態可以設為布林值，代表「是否各位數字皆為偶數」：

bool is_all_even(int n){
    while(...){   // 使用迴圈檢查每一位數字
        if(...){  // 只要發現有一個位數是奇數
            return false;
        }
        ...
    }
    return true;    // 前面都沒有return false，表示各位數字皆為偶數
}

:::

::: spoiler **Q. 我使用`int`來做題目，為什麼會拿到 WA(15%)？**
A. 因為題目有說到，最多為 10 位數字，`int`型態的數字無法容納所有 10 位數字，可能會出現 ==溢位（overflow）== 狀況，進而計算錯誤的結果。幸好數字也沒有太大，請嘗試使用長整數（`long long`）這個資料型別，其可容納的數字範圍可上網查詢。
:::

## 一起回家的日子

> 這題楷宗老師有特別說明最小公倍數的解法，請參考[函式實作示例](https://hackmd.io/@letscoding/ByzfuV0uA)。以下將延續課堂講解的解題邏輯進行說明。

### 解題思路
- ==宣告所需自訂函式==：最小公因數、最大公因數、閏年判斷。
- ==處理輸入==：作法與「計算時間差」這題相似，處理特定日期格式輸入。
- ==計算天數==：根據輸入的人數與天數，求最小公倍數，代表下次一起回家所需天數。
- ==推算日期==：扣除所需天數，跨月、跨年，直到下次一起回家的日期。
- ==處理輸出==：作法與「計算時間差」這題相似，輸出特定日期格式。
### 引導問題

::: spoiler **Q. 怎麼判斷一個數是否為閏年？**
A. 網路上有很多種解法，歡迎同學們去查查看，觀察每種解法的思路。最常看到的寫法為：
- 被 4 整除的數字，如果不是 100 的倍數，即為閏年。
- 如果是 400 的倍數，必為閏年。
以上兩式寫成邏輯運算式，`||`起來就是閏年判斷的條件式。

大部分人應該都學過閏年判斷，不妨嘗試寫成自訂函式，在主程式呼叫使用。
:::

::: spoiler **Q. 具體如何針對跨月、跨年，往前推進到一起回家的日子？**
A. 做法有非常多，順著加、倒著扣都有對應的寫法。而課堂範例的思路大概是這樣的：
- 先將現在的日期加上下次回家所需天數備用。
- 只要所需天數大於該月份天數，就扣掉這些天數，開心度過這個月。
- 到下一個月。注意若 12 月過完，要回到 1 月，並進入新的一年。
- 重複以上步驟。當可扣掉的天數未滿該月份總天數，該月份、剩餘天數即為一起回家的日子。
:::

::: spoiler **Q. 我該如何把閏年納入考量？**
A. 閏年的影響視在特定年份的 2 月多 1 天。基本判斷準則如下：

- 該年是否為閏年？
- 如果是閏年，剩餘天數加上去後，是否需要跨過該年的 2/29？

同時符合以上條件，才需要多加一天。
:::

:::spoiler **Q. 要一個一個月份判斷有幾天超級麻煩，有沒有簡化程式碼的方法？**
A. 宣告一個陣列，存放每個月的天數：

int month_day[] = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

另外，也可以宣告 13 個整數的陣列，在陣列最前面多放一個數字 0 ，如此一來，就可以接以月份為陣列索引值，取用每個月對應的天數。
:::

::: spoiler **Q. 不知道哪裡寫錯了，我的想法很對啊QQ 可以怎麼檢查呢？**
A. 建議出幾筆測資給自己測試。例如，我喜歡拿 1 個人、1 天後回家，來測試閏年/非閏年跨天、跨月、跨年的各種可能性：

1
1
2024/02/29

發想各種例外情況，避免無端被扣分，是賽後測評機制的重要能力。這題是很好的練習機會，大家試試看吧！
:::

## 賓果遊戲

（待補）