# Codebar 程式酒吧 文章備份

一個程式小白的學習紀錄，希望能以最基本的文字與思路，幫助到其他程式初學者！

## [Codebar 程式酒吧]((https://noah-0831.github.io/))
由於版面設計，為了提供更完整的文章分類與更新，歡迎移駕到我的[新部落格](https://noah-0831.github.io/)！

## 目錄
[TOC]

## [a001. 哈囉](https://zerojudge.tw/ShowProblem?problemid=a001)
**解題思路**
先使用scanf()函式讀取輸入的字串，再使用printf()函式輸出相對應的字串。

:::success
**注意事項**
大家或許已經注意到了，有時scanf()函式的變數名稱後面會加上&，有時卻不會，這其實與變數的型態有關。變數依據宣告的位置，可分為全域變數與區域變數。全域變數是宣告在主程式，或甚至主程式之外的變數，可以在所有地方存取或修改值；區域變數是在特定程式區塊，如迴圈或函式等內部宣告的變數，只能在其宣告的程式區塊以內使用。若是其他程式區塊也需使用此變數，必須在變數名稱前加&，表示取得這個變數的位址，進而使用此變數。

以scanf()函式來說，因為其所使用的變數並未在在函式內宣告，屬於區域變數，因此使用時通常須在變數名稱前加&，取得變數的位址來存放輸入。但在所有資料型態中，字串是特例，因為字串在C語言裡就是以空字元\0結尾的字元陣列，符號為%s，而陣列本身即為「指標」，有興趣的人可以自行上網搜尋相關內容。至於其他資料型態的符號可以參考下表：

:::

**程式碼**

#include <stdio.h>
int main() {
    char arr[100];
    scanf("%s", arr);
    printf("hello, %s\n", arr);
    return 0;
}

## [a002. 簡易加法](https://zerojudge.tw/ShowProblem?problemid=a002)
**解題思路**
先使用scanf()函式讀取輸入的兩個數字，再使用printf()函式輸出兩數和。

:::success
**注意事項**
大家或許已經注意到了，有時scanf()函式的變數名稱後面會加上&，有時卻不會，這其實與變數的型態有關。變數依據宣告的位置，可分為全域變數與區域變數。全域變數是宣告在主程式，或甚至主程式之外的變數，可以在所有地方存取或修改值；區域變數是在特定程式區塊，如迴圈或函式等內部宣告的變數，只能在其宣告的程式區塊以內使用。若是其他程式區塊也需使用此變數，必須在變數名稱前加&，表示取得這個變數的位址，進而使用此變數。

以scanf()函式來說，因為其所使用的變數並未在在函式內宣告，屬於區域變數，因此使用時通常須在變數名稱前加&，也就是指定變數的位址作為儲存空間來存放輸入。但在所有資料型態中，字串是特例，因為字串在C語言裡就是以空字元\0結尾的字元陣列，符號為%s，而陣列本身即為「指標」，有興趣的人可以自行上網搜尋相關內容。
:::

**程式碼**

#include <stdio.h>
int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d", a+b);
    return 0;
}

## [a003. 兩光法師占卜術](https://zerojudge.tw/ShowProblem?problemid=a003)
**解題思路**
先讀取出生月日，依據題意得到S值後，再依照S值輸出相對應的字串。

:::success
**注意事項**
[switch()條件句](https://openhome.cc/Gossip/CppGossip/switchStatement.html)是條件句之一。使用時，將想要判斷的數值或字元放在switch後面的括弧裡，並在case列出可能的情況，程式就會自動依據case指定的數字、字元或判斷句的情形，執行相對應的程式區塊。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數M、D，分別表示月、日
    int M, D;
    scanf("%d %d", &M, &D);
    //宣告變數S，依據題意賦值為(M*2+D)%3
    S = (M*2+D)%3;
    //switch()條件句：依據S值輸出相對應的字串
    switch S:
        //若S值為0，輸出「普通」
        case 0:
            printf("普通");
            break;
        //若S值為1，輸出「吉」
        case 1:
            printf("吉");
            break;
        //若S值為2，輸出「大吉」
        case 2:
            printf("大吉");
            break;
    return 0;
}

## [a004. 文文的求婚](https://zerojudge.tw/ShowProblem?problemid=a004)
**解題思路**
根據題意，西元年被4整除且不被100整除，或被400整除者即為閏年。因此，我們可以利用取餘數的方式判斷輸入的年份是否能被4、100和400整除，進而判斷其是否為閏年。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數year，代表西元年
    int year;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%d", &year) != EOF) {
        //根據題意，西元年被4整除且不被100整除，或被400整除者即為閏年
        if(year%4 == 0 && year%100 != 0 || year%400 == 0)
            printf("閏年\n");
        else
            printf("平年\n");
    }
    return 0;
}

## [a005. Eva的回家作業](https://zerojudge.tw/ShowProblem?problemid=a005)
**解題思路**
由題意可知輸入的數列只有等差數列或等比數列兩種可能。先用if_else條件句判斷輸入數列為等差數列還是等比數列，再依據等差數列兩相鄰項差相同、等比數列兩相鄰項比相同的性質推知第五項。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此可使用[for迴圈](https://openhome.cc/Gossip/CGossip/forStatement.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數t，代表數列的數目
    int t;
    scanf("%d", &t);
    //使用for迴圈分別討論每一個數列的情況
    for(int i = 0 ; i < t ; i++) {
        //宣告並讀取陣列a[4]，代表輸入數列的前四項
        int a[4];
        scanf("%d %d %d %d", &a[0], &a[1], &a[2], &a[3]);
        //若數列任兩項間的差相同，即為等差數列
        if(a[1]-a[0] == a[2]-a[1])
            printf("%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[3]+(a[1]-a[0]));
        //若否，即為等比數列
        else
            printf("%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[3]*(a[1]/a[0]));
    }
    return 0;
}

## [a006 一元二次方程式](https://zerojudge.tw/ShowProblem?problemid=a006)
**解題思路**
求一元二次方程式的根有多種方式，舉凡配方法、十字交乘等，而這裡採用的是[公式解](https://www.youtube.com/watch?v=Z0omOUKCXcg&ab_channel=%E5%9D%87%E4%B8%80%E6%95%99%E8%82%B2%E5%B9%B3%E5%8F%B0JunyiAcademy)。若判別式b^2^-4ac>0，代表此方程式有兩相異實根(-b±√b^2^-4ac)/2a；若判別式b^2^-4ac=0，代表此方程式有兩相同實根(重根)(-b+√b^2^-4ac)/2a=(-b-√b^2^-4ac)/2a；若判別式b^2^-4ac<0，代表此方程式沒有實根。

:::success
**注意事項**
本題中使用了[sqrt()函式](https://www.runoob.com/cprogramming/c-function-sqrt.html)表示根式寫法。由於sqrt()函式並非標準函式庫裡的函式，使用前須先引用<math.h>函式庫。
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    //宣告並讀取變數a、b、c，代表一元二次方程式的三個係數
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    //宣告變數D，代表一元二次方程式的判別式
    int D = b*b-4*a*c;
    //若判別式小於零，代表無實根存在
    if(D < 0)
        printf("No real root\n");
    //若判別式大於等於零，代表有實根存在
    else {
        int x1 = (-b+sqrt(D))/(2*a);
        int x2 = (-b-sqrt(D))/(2*a);
        //若判別式大於零，代表有兩相異實根
        if(D > 0)
            printf("Two different roots x1=%d , x2=%d", x1, x2);
        //若判別式等於零，代表有相同實根
        else if(D == 0)
            printf("Two same roots x=%d", x1);
    }
    return 0;
}

## [a009. 解碼器](https://zerojudge.tw/ShowProblem?problemid=a009)
**解題思路**
[ASCII碼](https://web.fg.tp.edu.tw/~anny/ASCII_table.htm)全名為「American Standard Code for Information Interchange」，中文為「美國信息交換標準代碼」。之所以會有這個代碼是因為電腦採用的是二進制，八進制、十進制的其他數字，或甚至英文字母，必須經由此代碼轉換為二進制後，電腦才能順利理解、顯示、運算。
以C語言來說，當電腦進行字元與整數的運算時，會自動將該字元轉為ASCII碼再與整數運算，運算完成後再轉成字元。因此，所謂「把明碼的每個字元加上某一個整數K而得到密碼的字元」，指的是將明碼所對應到的ASCII碼加上某一個整數K，再轉為字串得到密碼。

透過觀察範例輸入/出可知，1經過轉換後會變成*，查表可得K值為-7。因此，我們先使用scanf()函式讀取輸入的明碼，存放到字元陣列arr，再將陣列內的元素逐一減七，就是題目所求的密碼了。

:::success
**注意事項**
本題中使用了[strlen()函式](https://www.runoob.com/cprogramming/c-function-strlen.html)取出字串長度。由於strlen()函式並非標準函式庫裡的函式，使用前須先引用<string.h>函式庫。
:::

**程式碼**

#include <stdio.h>
#include <string.h>
int main() {
    //以字元陣列的形式，宣告並讀取輸入的明碼
    char arr[1000];
    scanf("%s", arr);
    //利用for迴圈，逐項將明碼轉為密碼
    for(int i = 0 ; i < strlen(arr) ; i++)
        arr[i] = arr[i]-7;
    printf("%s", arr);
    return 0;
}

## [a010. 因數分解](https://zerojudge.tw/ShowProblem?problemid=a010)
**連結題目：[a740. 质因数之和](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a740-%E8%B4%A8%E5%9B%A0%E6%95%B0%E4%B9%8B%E5%92%8C)**

**解題思路**
這題的關鍵是「因數分解」這四個字，背後所代表的計算過程。當我們在做因數分解的時候，會使用短除法，從最小的質數開始檢查。當遇到該數的因數時，就把該數除以此質數得到商數，然後再重複上述動作，直到確定商數已經不能再被此質數整除為止。重複上述動作直到商數剩下一為止，即完成因數分解。

:::success
**注意事項**
在因數分解時，因數之間會以 * 隔開，但注意輸出結尾不會有 * 。因此，我們必須判斷甚麼時候輸出結束。而正如解題思路所說，因數分解到最後，商數會剩下一。因此，我們可以利用if條件句判斷，當商數不為一的時候再輸出 * 。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數num，代表要進行因數分解的整數
    int num;
    scanf("%d", &num);
    //用for迴圈跑2到自己本身的所有數字，檢查是否為因數
    for(int factor = 2 ; factor <= num ; factor++) {
        //若可以整除，代表此數是因數，將其分解至得出質因數為止
        if(num%factor == 0) {
            int power = 0;
            while(num%factor == 0) {
                num /=factor;
                power++;
            }
            //若此質因數只有一次，直接輸出數字即可
            if(power == 1)
                printf("%d", factor);
            //若此質因數不只一次，需輸出共幾次方
            else
                printf("%d^%d", factor, power);
            //除了最後一位以外，每個質因數輸出後皆須加上*
            if(num != 1)
                printf(" * ");
        }
    }
    return 0;
}

## [a013. 羅馬數字](https://zerojudge.tw/ShowProblem?problemid=a013)
**解題思路**
本題希望我們寫出可以進行羅馬數字減法的程式。而由於電腦無法直接進行羅馬數字的運算，因此我們須先將輸入的兩組羅馬數字轉為阿拉伯數字，然後再進行運算，最後將運算後的結果再轉回羅馬數字輸出。

:::success
**注意事項**
為了維持程式碼的簡潔與易讀性，本程式碼使用了[函式](https://mycollegenotebook.medium.com/%EF%BD%83%E8%AA%9E%E8%A8%80%E7%AD%86%E8%A8%98-%E5%87%BD%E5%BC%8F-functions-cea21d86560f)宣告。所謂函式，可以想成是「可重複使用的程式區塊」，因此宣告函式就意味著將主程式可能重複用到的程式碼直接寫在主程式外。如此一來當主程式需要用到時，只要呼叫函式較可以直接使用了。在宣告函式時，首先要確定這個函式要執行的功能是什麼，應該要回傳什麼型態的回傳值給主程式；再來要思考這個函式可能會需要用到哪些主程式的參數，將這些參數傳進函式裡，剩下的部分就和一般撰寫程式時差不多了。所以說不必因看到「函式宣告」而感到緊張，其實只是有些格式要注意而已！
:::

**程式碼**

#include <stdio.h>
#include <string.h>
//宣告一回傳值為int型態的函式，將羅馬數字轉為阿拉伯數字
int roman_to_arabic(char roman[11]) {
    int i = 0, arabic = 0;
    while(roman[i] != '\0' && roman[i] != '\n') {
        switch(roman[i]) {
            //若讀取到I，可能為I、IV或IX
            case 'I': {
                //若I後面有V，則為IV，代表4
                if(roman[i+1] == 'V') {
                    arabic += 4;
                    i += 2;
                }
                //若I後面有X，則為IX，代表9
                else if(roman[i+1] == 'X') {
                    arabic += 9;
                    i += 2;
                }
                //若I後面既非V也非X，則為I，代表1
                else {
                    arabic += 1;
                    i++;
                }
                break;
            }
            //若讀取到V，因IV會先讀取到I，只可能為V，代表5
            case 'V': {
                arabic += 5;
                i++;
                break;
            }
            //若讀取到X，因IX會先讀取到I，只可能為X、XL或XC
            case 'X': {
                //若X後面有L，則為XL，代表40
                if(roman[i+1] == 'L') {
                    arabic += 40;
                    i += 2;
                }
                //若X後面有C，則為XC，代表90
                else if(roman[i+1] == 'C') {
                    arabic += 90;
                    i += 2;
                }
                //若X後面既非L也非C，則為X，代表10
                else {
                    arabic += 10;
                    i++;
                }
                break;
            }
            //若讀取到L，因XL會先讀取到X，只可能為L，代表50
            case 'L': {
                arabic += 50;
                i++;
                break;
            }
            //若讀取到C，因XC會先讀取到X，只可能為C、CD或CM
            case 'C': {
                //若C後面有D，則為CD，代表400
                if(roman[i+1] == 'D') {
                    arabic += 400;
                    i += 2;
                }
                //若C後面有M，則為CM，代表900
                else if(roman[i+1] == 'M') {
                    arabic += 900;
                    i += 2;
                }
                //若C後面既非D也非M，則為C，代表100
                else {
                    arabic += 100;
                    i++;
                }
                break;
            }
            //若讀取到D，因CD會先讀取到C，只可能為D，代表500
            case 'D': {
                arabic += 500;
                i++;
                break;
            }
            //若讀取到M，因CM會先讀取到C，只可能為M，代表1000
            case 'M': {
                arabic += 1000;
                i++;
                break;
            }
        }
    }
    //回傳轉換後的阿拉伯數字
    return arabic;
}
//宣告一回傳值為void型態（不回傳）的函式，將阿拉伯數字轉為羅馬數字
void arabic_to_roman(int arabic) {
    int i = 0;
    char roman_temp[15] = {}, roman[11] = {};
    //若數字大於等於1000，就用1000換成一個M
    while(arabic >= 1000) {
        roman_temp[i] = 'M';
        arabic -=1000;
        i++;
    }
    //若數字大於等於500，就用500換成一個D
    while(arabic >= 500) {
        roman_temp[i] = 'D';
        arabic -=500;
        i++;
    }
    //若數字大於等於100，就用100換成一個C
    while(arabic >= 100) {
        roman_temp[i] = 'C';
        arabic -=100;
        i++;
    }
    //若數字大於等於50，就用50換成一個L
    while(arabic >= 50) {
        roman_temp[i] = 'L';
        arabic -=50;
        i++;
    }
    //若數字大於等於10，就用10換成一個X
    while(arabic >= 10) {
        roman_temp[i] = 'X';
        arabic -=10;
        i++;
    }
    //若數字大於等於5，就用5換成一個V
    while(arabic >= 5) {
        roman_temp[i] = 'V';
        arabic -=5;
        i++;
    }
    //若數字大於等於1，就用1換成一個I
    while(arabic >= 1) {
        roman_temp[i] = 'I';
        arabic -=1;
        i++;
    }
    //檢查：在羅馬數字的表示法中，不會有4個相同符號並列，若有4格符號並列需用減法的思維重新記錄，比如4在羅馬數字的表示法中是記成XI而不是IIII
    int j=0;
    for(i=0 ; roman_temp[i] != '\0' ; i++) {
        //若有4個相同符號並列，先檢查是什麼符號，再決定如何轉換
        if(roman_temp[i] == roman_temp[i+1] && roman_temp[i+1] == roman_temp[i+2] && roman_temp[i+2] == roman_temp[i+3]) {
            switch(roman_temp[i]) {
                //若為4個C，可能為DCCCC或CCCC
                case 'C': {
                    //若C前面為D，則為DCCCC，重新記為CM
                    if(roman_temp[i-1] == 'D') {
                        roman[j-1] = 'C';
                        roman[j] = 'M';
                    }
                    //若C前面非D，則為CCCC，重新記為CD
                    else {
                        roman[j] = 'C';
                        roman[j+1] = 'D';
                        j++;
                    }
                    break;
                }
                //若為4個X，可能為LXXXX或XXXX
                case 'X': {
                    //若X前面為L，則為LXXXX，重新記為XC
                    if(roman_temp[i-1] == 'L') {
                        roman[j-1] = 'X';
                        roman[j] = 'C';
                    }
                    //若X前面非L，則為XXXX，重新記為XL
                    else {
                        roman[j] = 'X';
                        roman[j+1] = 'L';
                        j++;
                    }
                    break;
                }
                //若為4個I，可能為VIIII或IIII
                case 'I': {
                    //若I前面為V，則為VIIII，重新記為IX
                    if(roman_temp[i-1] == 'V') {
                        roman[j-1] = 'I';
                        roman[j] = 'X';
                    }
                    //若I前面非V，則為IIII，重新記為IV
                    else {
                        roman[j] = 'I';
                        roman[j+1] = 'V';
                        j++;
                    }
                    break;
                }
            }
            //因為是4個相同的符號，檢查一個後，後面三個可直接略過
            i += 3;
        }
        //若無4個相同符號並列，直接照記即可
        else
            roman[j] = roman_temp[i];
        //
        j++;
    }
    //輸出轉換後的羅馬數字
    printf("%s\n", roman);
}
//主程式
int main() {
    while(1) {
        //先讀取第一個字串，若為#則終止輸入，若否則將此字串複製給roman_1
        char test[10];
        scanf("%s", test);
        if(test[0] == '#')
            break;
        char roman_1[11] = {}, roman_2[11] = {};
        strcpy(roman_1, test);
        //再讀取第二個字串，將此字串存到roman_2
        scanf("%s", roman_2);
        //因電腦無法直接進行羅馬數字的計算，需先將羅馬數字轉為阿拉伯數字
        int arabic_1 = roman_to_arabic(roman_1), arabic_2 = roman_to_arabic(roman_2);
        int arabic_difference = abs(arabic_1-arabic_2);
        //若相減後的差為零，則輸出「ZERO」*/
        if(arabic_difference == 0)
            printf("ZERO\n");
        //若差不為0，根據題意，需先將阿拉伯數字轉為羅馬數字再輸出
        else
            arabic_to_roman(arabic_difference);
    }
    return 0;
}

## [a015. 矩陣的翻轉](https://zerojudge.tw/ShowProblem?problemid=a015)
**解題思路**
以逐個字元讀取的方式讀取輸入的二維陣列後，將其行列互換後再輸出。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](
https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數row、column，代表矩陣的行與列
    int row, column;
    //根據題意，測資檔會包含多組矩陣資料，因此使用EOF寫法判斷程式執行的條件
    while(scanf("%d %d", &row, &column) != EOF) {
        //宣告並讀取二維陣列
        int matrix[row][column];
        for(int i = 0 ; i < row ; i++)
            for(int j = 0 ; j < column ; j++)
                scanf("%d", &matrix[i][j]);
        //將二維陣列行列互換後輸出
        for(int j = 0 ;j < column ; j++) {
            for(int i = 0 ; i < row ; i++)
                printf("%d ", matrix[i][j]);
            printf("\n");
        }
    }
    return 0;
}

## [a020. 身分證檢驗](https://zerojudge.tw/ShowProblem?problemid=a020)
**連結題目：[a054. 電話客服中心](https://noah-0831.github.io/a054-%E9%9B%BB%E8%A9%B1%E5%AE%A2%E6%9C%8D%E4%B8%AD%E5%BF%83/)**

**解題思路**
本題的題意相當複雜，大致上的意思是:
1. 讀取輸入的身分證字號。
2. 將身分證字號中代表出生縣市的英文代號依照附圖的方式轉換成數字。
3. 將2.的數字的個位數字乘以9倍並加上十位數字。
4. 將身分證字號的數字部分由左到右分別乘上8、7、6、5、4、3、2、1、1。
5. 以3.與4.的和做為判斷標準。若能被10整除則輸出"real"，否則輸出"fake"。

1.的部分需注意身份證字號的各數字之間沒有空格，若用整數型態的變數儲存會被讀取成一個整數。因此，這裡使用字元陣列讀取並儲存輸入的身分證字號。

2.就是單純的條件判斷，乍看之下需寫出26個英文字母各自的條件語句，但仔細觀察會發現有些英文字母的轉換是有規律的。我們可以善用這個規律化簡程式碼，將剛剛以字元型態讀取的英文代號先轉為[ASCII碼](https://web.fg.tp.edu.tw/~anny/ASCII_table.htm)，再經由加減運算得到如附圖中的數字。

3.的關鍵在於分別取得數字的個位數和十位數。個位數可以用除10後取餘數的方式獲得，而十位數則因為在整數型態的運算中，若運算結果為小數，會自動無條件捨去至整數位，剛好等於除10後的商。

4.的部分，可以看到前8位數字的倍數呈規律遞減，因此可善用for迴圈得出，第9位再單獨加上去就好了。

5.就是單純的條件判斷並輸出相對應的輸出！

:::success
**注意事項**
在進行資料型態的轉換時，會以「確保轉換過程中不會有資料遺失」為原則，因此若轉換後的資料型態所占的記憶體空間大於等於原資料型態，就可以直接轉換。以本題的程式碼來說，因為整數型態變數所佔的記憶體空間為4位元組，比字元型態變數所佔的1位元組還大，因此字元型態的變數在遇到需要用整數型態判別或運算的時候，會自動轉為整數，也就是其ASCII碼。嚴謹的寫法是 : (轉換後的的資料型態)變數名稱。 e.g. (int)city
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取字元型態變數city，代表身份證字號第一碼
    //宣告字元陣列num，代表身分證字號後9碼
    char city, num[10]; 
    scanf("%c %s", &city, num);
    //根據身份證字號第一碼所對應的出生城市，將其轉為數字
    if(city >= 65 && city <= 72) 
        city-=55;
    else if(city == 'I')
        city -=39;
    else if(city >= 74 && city <= 78)
        city -=56;
    else if(city == 'O')
        city -=44;
    else if(city >= 80 && city <= 86)
        city -=57;
    else if(city == 'W')
        city -=55;
    else if(city == 'X' || city == 'Y')
        city -=58;
    else if(city == 'Z')
        city -=57;
    //將轉換後得出的數字，個位數字乘以9倍並加上十位數字
    int sum = city/10+(city%10)*9;
    //將身分證字號的數字部分由左到右分別乘上8、7、6、5、4、3、2、1，最後再加上末碼
    for(int i = 0 ; i < 8 ; i++)
        sum += (num[i]-48)*(8-i);
    sum += num[8]-48;
    //若上述總和可被10整除就輸出real，否則輸出fake
    if(sum%10 == 0)
        printf("real");
    else
        printf("fake");

    return 0;
}

## [a022. 迴文](https://zerojudge.tw/ShowProblem?problemid=a022)
**連結題目：[明明愛明明](https://hackmd.io/8wBqbi0mSV6mPg9bcNGJ3Q?view#a224-%E6%98%8E%E6%98%8E%E6%84%9B%E6%98%8E%E6%98%8E)**

**解題思路**
迴文，是指字串不論是從正向讀還是反向讀均相同，也就是說迴文字串必定頭尾對稱。因此，我們可以利用for迴圈檢查。若長度為len的字串，第i項等於第len-i-1項，就將計數變數count值+1。若count值等於len/2，就代表該字串符合迴文的條件。

:::success
**注意事項**
在C語言的語法裡，陣列的最後一項是空字元，也就是說若今天有一個大小為i項的陣列，那麼它可以儲存的項數是i-1項！
:::

**程式碼**

#include <stdio.h>
#include <string.h>
int main() {
    //宣告並讀取陣列arr，代表輸入的字串
    char arr[1000];
    scanf("%s", arr);
    //宣告變數count，代表前後對稱的組數
    int count = 0;
    //迴文字串必然對稱，因此我們可以檢查該字串前後對應到的項是否相同
    //若發現字串的任一組頭尾不同，即非迴文，輸出no後跳出迴圈
    for(count = 0 ; count < strlen(arr)/2 ; count++) {
        if(arr[count] != arr[(strlen(arr)-1)-count]) {
            printf("no");
            break;
        }
    }
    //即非迴文到字串的一半都未發現不同的組，則為迴文，輸出yes
    if(count == strlen(arr)/2)
        printf("yes");
    return 0;
}

## [a024. 最大公因數(GCD)](https://zerojudge.tw/ShowProblem?problemid=a024)
**解題思路**
求兩數最大公因數的辦法有很多種，可以將兩數個別的因數都先求出來，再取它們的交集得到最大公因數；也可以直接求兩數公因數的最大值。但本題測資的值較大，上述方法在ZeroJudge上執行時很可能會超時(TLE)。因此，建議使用[輾轉相除法](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)，快速計算最大公因數。

輾轉相除法的概念是，兩數的最大公因數等於其中較小的數和兩數相除後的餘數的最大公因數。具體的做法是先將兩數中較大的數字除以較小的數字，基於除法運算後餘比商小的特性，可知剩下的餘一定會比原先較小的數字還小。這時原先較小的數字就成了新的運算中較大的數字，而餘則成了新的運算中較小的數字。重複運算至其中一數變成零為止，剩下的另一個數就是兩數的最大公因數。如果在看完上述文字解說後仍然無法立刻理解，可以參考[維基百科上的動畫](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)，或是[昌爸工作坊提供的運算欄位列出的算式](http://www.mathland.idv.tw/fun/euclidean.htm)，搭配實際運算或程式演示幫助理解。

:::success
**注意事項**
本程式碼第7、8行使用了「[條件運算子](https://shengyu7697.github.io/cpp-ternary-operator/)」，寫法是「(條件) ？ (敘述1) ： (敘述2)」。條件運算子在程式執行時，會依據條件決定接下來的動作。如果符合條件就回傳敘述1的值，否則回傳敘述2的值。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數a、b，代表輸入的兩個整數
    int a, b;
    scanf("%d%d", &a, &b);
    //宣告變數big、small，分別代表兩數中較大和較小的數字
    int big = (a > b) ? a : b;
    int small = (a > b) ? b : a;
    //輾轉相除法：將兩數中較大的數字除以較小的數字，
    //原來較小的數字作為新的運算中教大的數字，餘作為新的運算中較小的數字
    //直到其一為0時運算結束，剩下的數字就是兩數的最大公因數
    while(small != 0) {
        int temp = big;
        big = small;
        small = temp%small;
    }
    printf("%d", big);
    return 0;
}

## [a034. 二進位制轉換](https://zerojudge.tw/ShowProblem?problemid=a034)
**解題思路**
在進入本題的討論之前，我們需要先了解何謂進位制。所謂的進位制，指的是以「基數」的指數和表示數字的記數方法。以最常見的十進位制來說，基數就是10。因此，以123這個數字來說，在十進位制下即為1x10^2^+2x10^1^+3x10^0^。而所謂的二進位制，就是基數為2的進位制。除了基數不同以外，邏輯和十進位制其實相同。因此，在進行從十進位制到二進位制的轉換時，我們可以2的指數逐一降次檢查大小。

因為整數型態的變數可儲存的最大值為2的31次方，所以我們先從2的31次方開始檢查，若該數比2的31次方還大，就將該位數註記為1，並將其值減去2的31次方，否則將該位數註記為0。接著降次繼續檢查，直到整個數字檢查完畢，即完成二進位制的轉換。舉例來說，十進位制的123可以被表示為1x2^6^+1x2^5^+1x2^4^+1x2^3^+0x2^2^+1x2^1^+1x2^0^，因此其在二進位制表示法即為1111011。

:::success
**注意事項**
雖然並不常見，但只要符合寫法，迴圈可以同時使用多個控制變數。本程式碼內中的for迴圈就用了兩個變數控制迴圈運行，其中變數n代表的是檢查的次方，i代表的是轉換為二進位後的位數。
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    //宣告變數dec，表示十進位數字
    int dec;
    while(scanf("%d", &dec) != EOF) {
        int bin[32] = {}, non_zero_digit = 0;
        //從2的31次方開始檢查，次方逐次遞減
        for(int n = 31, i = 0 ; n >= 0 ; n--, i++) {
            //若該數大於等於2的n次方，就將該位數註記為1，並將其值減去2的n次方
            if(dec >= pow(2, n)) {
                bin[i] = 1;
                dec -=pow(2, n);
                non_zero_digit++;
            }
            //若該數小於2的n次方，就將該位數註記為0
            else
                bin[i] = 0;
            //輸出須注意該位數為0的可能有兩種
            //若前面沒有輸出過非0數字，則為前綴零，不輸出
            //若否，則為非前綴零，需輸出
            if(bin[i] != 0 || non_zero_digit != 0)
                printf("%d", bin[i]);
        }
        printf("\n");
    }
    return 0;
}

## [a038. 數字翻轉](https://zerojudge.tw/ShowProblem?problemid=a038)
**解題思路**
先以字元陣列的形式讀取輸入的字串，由後往前輸出，注意避開前綴0。

:::success
**注意事項**
需注意前綴零不輸出，例如5800翻轉後為85，而不是0085。至於如何判斷該位是否為前綴零，可以用前面是否出現過非零數字來判斷。若前面沒有輸出過非0數字，則為前綴零，不輸出；若否，則為非前綴零，需輸出。
:::

**程式碼**

#include <stdio.h>
#include <string.h>
int main() {
    //宣告並讀取字元陣列num，代表輸入的數字
    char num[10];
    scanf("%s", num);
    //宣告變數test，並設初始值為0，記錄前面是否有輸出過非零數字
    //若test為0，代表之前尚未輸出過非零數字，這一位數若是0即為前綴0，不需輸出
    //若test為1，代表之前已經輸出過非零數字，這一位數就算是0也不是前綴0，需輸出
    int test = 0;
    for(int i = 0 ; i < strlen(num) ; i++)
        if(num[(strlen(num)-1)-i] != '0' || test != 0) {
            printf("%c", num[(strlen(num)-1)-i]);
            //輸出後將test設為1，代表已經輸出過非零數字
            test=1;
        }
    //若test仍為0，說明直到跑完指個陣列都未曾輸出過非零數字，也就是說這個數字就是0
    if(test == 0)
        printf("0");
    return 0;
}

## [a040. 阿姆斯壯數](https://zerojudge.tw/ShowProblem?problemid=a040)
**解題思路**
由題目可知阿姆斯壯數的判斷方法為將待判斷的數字依照位數分拆成各個數字後，依照待判斷數字的位數n次方後，再判斷各位數的次方和是否等於待判斷的數字。故本題的兩個關鍵分別是判斷輸入數字的位數，以及取各個位數的n次方。

:::success
**注意事項**
本題中使用了[pow()函式](https://www.runoob.com/cprogramming/c-function-pow.html)表示指數寫法，其中第一個參數代表指數的底數，第二個參數代表次方。由於pow()函式並非標準函式庫裡的函式，使用前必須先引用<math.h>函式庫。另外需注意pow函式的回傳值為double型態，因此需使用(int)寫法轉為int型態。
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    //宣告並讀取變數n、m，代表判斷範圍的上下限
    int n, m, test = 0;
    scanf("%d %d", &n, &m);
    //利用for迴圈跑從n到m的所有數字
    for(int num = n ; num <= m ; num++) {
        //宣告變數num，代表檢查到的數；宣告變數len，代表此數的位數
        int i = num, len = 1;
        //若此數大於等於10，就將其除以10，並將len加一
        while(i >= 10) {
            i /= 10;
            len++;
        }

        //宣告變數sum，代表各個位數的總和
        int sum = 0;
        //從最高位開始，將此數的各個位數len次方後相加
        for(int i = len ; i > 0 ; i--)
            //num為目前判斷的數字，共len位數，i代表目前檢查到的位數
            //將num%pow(10, i)即可得num在i位以後（含）的數字，/pow(10, i-1)可得num在i-1位以前的數字，即為第i位數字
            sum += pow((num%(int)pow(10, i)/(int)pow(10, i-1)), len);
        //若此len位數的數字，各個位數的len次方和等於自己，即為阿姆斯壯數，需輸出
        if(sum == num) {
            printf("%d ", num);
            test++;
        }
    }
    //若範圍內的數字皆無阿姆斯壯數，輸出None
    if(test == 0)
        printf("none");
    return 0;
}

## [a042. 平面圓形切割](https://zerojudge.tw/ShowProblem?problemid=a042)
**解題思路**
已知n個圓最多可以把平面分割成n^2^-n+2個部份，因此先讀取輸入的n值，再輸出n^2^-n+2的值。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數n，代表題目給定的正整數
    int n;
    //用while迴圈搭配EOF寫法讀取每筆n值，並輸出對應的n^2-n+2值
    while(scanf("%d", &n) != EOF)
        printf("%d\n", n*n-n+2);
    return 0;
}

## [a044. 空間切割](https://zerojudge.tw/ShowProblem?problemid=a044)
**解題思路**
這題的程式寫法並不難，關鍵在於空間中的n個平面最多可將空間切成幾個區域。已知n個平面最多可以將空間分割成(n^3+5n+6)/6個區域，因此先讀取輸入的n值，再輸出(n^3+5n+6)/6的值。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數n，代表題目給定的正整數
    int n;
    //用while迴圈搭配EOF寫法讀取每筆n值，並輸出對應的(n^3+5n+6)/6值
    while(scanf("%d", &n) != EOF)
        printf("%d\n", (n*n*n+5*n+6)/6);
    return 0;
}

## [a053. Sagit's 計分程式](https://zerojudge.tw/ShowProblem?problemid=a053)
**解題思路**
以if_else條件句判斷答對題數的情形，並輸出相對應的輸出。

:::success
**注意事項**
在C語言裡，一個條件句只能有一個關係運算子，因此平時書寫的寫法10 < N < 20，需改寫成10 < N && N < 20。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數N，代表答對題數
    int N;
    scanf("%d", &N);
    //答對題數在 0~10 者，每題給6分
    if(N <= 10)
        printf("%d", 6*N);
    //題數在 11~20 者，從第11題開始，每題給2分
    else if(10 < N && N <= 20)
        printf("%d", 60+2*(N-10));
    //題數在 21~40 者，從第21題開始，每題給1分
    else if(20 < N && N <= 40)
        printf("%d", 80+1*(N-20));
    //題數在 40 以上者，一律100分
    else
        printf("100");
    return 0;
}

## [a054. 電話客服中心](https://zerojudge.tw/ShowProblem?problemid=a054)
**連結題目：[a020. 身分證檢驗](https://noah-0831.github.io/a020-%E8%BA%AB%E5%88%86%E8%AD%89%E6%AA%A2%E9%A9%97/)**

**解題思路**
本題的題意相當複雜，簡單來說就是要我們透過檢查碼反推可能的英文字母。
而檢查碼的算法如下:

1. 將身分證字號中代表出生縣市的英文代號依照附圖的方式轉換成數字。
2. 將1.的數字的個位數字乘以9倍並加上十位數字。
3. 將身分證字號的數字部分，由左到右分別乘上8、7、6、5、4、3、2、1、1。
4. 令s為2.加上3.的和，m為s的個位數，檢查碼c即為10-m。

因此，我們可以將身份證號碼的後9碼用字元陣列儲存，經由運算得到各位相對數字乘積的總和s後，推得檢查碼c，進而依據c值輸出對應的出生縣市。

:::success
**注意事項**
[switch()條件句](https://openhome.cc/Gossip/CppGossip/switchStatement.html)是條件句之一。使用時，將想要判斷的數值或字元放在switch後面的括弧裡，並在case列出可能的情況，程式就會自動依據case指定的數字、字元或判斷句的情形，執行相對應的程式區塊。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取字元陣列num，代表身份證號碼的後9碼
    char num[10];
    scanf("%s", num);
    //宣告變數s，代表身分證字號各位相對數字乘積的總和
    int s = 0;
    //將身分證字號的數字部分由左到右分別乘上8、7、6、5、4、3、2、1，最後再加上末碼
    for(int i = 0 ; i < 8 ; i++)
        s += (num[i]-48)*(8-i);
    s += num[8]-48;

    //宣告變數c，代表檢查碼
    //將10減去s的個位數後，即可得c
    int c = 10-s%10;
    //檢查碼只有一位數，因此若c=10時，則檢查碼為0
    if(c == 10)
        c = 0;
    //依據c值反推可能的出生縣市
    switch(c) {
            case 0:
                printf("BNZ");
                break;
            case 1:
                printf("AMW");
                break;
            case 2:
                printf("KLY");
                break;
            case 3:
                printf("JVX");
                break;
            case 4:
                printf("HU");
                break;
            case 5:
                printf("GT");
                break;
            case 6:
                printf("FS");
                break;
            case 7:
                printf("ER");
                break;
            case 8:
                printf("DOQ");
                break;
            case 9:
                printf("CIP");
                break;
        }
    return 0;
}

## [a058. MOD3](https://zerojudge.tw/ShowProblem?problemid=a058)
**解題思路**
利用除以3之後的餘數判斷該數字是3k、3k+1還是3k+2，使用for迴圈讀取n個數字後，輸出其中3k、3k+1、3k+2的數量。

:::success
**注意事項**
[switch()條件句](https://https://openhome.cc/Gossip/CppGossip/switchStatement.html)是條件句之一。使用時，將想要判斷的數值或字元放在switch後面的括弧裡，並在case列出可能的情況，程式就會自動依據case指定的數字、字元或判斷句的情形，執行相對應的程式區塊。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數n，代表接下來有幾個數字要判斷
    //宣告變數a、b、c，分別代表3k、3k+1、3k+2的數量
    int n, a = 0, b = 0, c = 0;
    scanf("%d", &n);
    //用for迴圈針對n個輸入的數字作相對應的判斷
    for(int i = 0 ; i < n ; i++) {
        //宣告並讀取變數num，代表輸入的數字
        int num;
        scanf("%d", &num);
        //依據num除3後的餘數，判斷其為3k、3k+1還是3k+2
        switch(num%3) {
            case 0:
                a++;
                break;
            case 1:
                b++;
                break;
            case 2:
                c++;
                break;
        }
    }
    //輸出
    printf("%d %d %d", a, b, c);
    return 0;
}

## [a059. 完全平方和](https://zerojudge.tw/ShowProblem?problemid=a059)
**解題思路**
題目希望我們求出在a、b之間的所有完全平方數總和，理論上要用for迴圈跑從a到b之間的所有數字，檢查他們是否為完全平方數，若是則將他們相加，最後再輸出其總和，但這麼做的話需要在for迴圈裡加上條件判斷。因此我們也可以換種方式思考，若 a ≤ x^2 ≤ b ，可知 √a ≤ x ≤ √b ，故只要找出在√a及√b之間的正整數，將他們的平方相加，即為在a、b之間所有完全平方數的和。

:::success
**注意事項**
本題中使用了[ceil()函式](https://www.runoob.com/cprogramming/c-function-ceil.html)對參數無條件進位（向上取整），以及[sqrt()函式](https://www.runoob.com/cprogramming/c-function-sqrt.html)對參數開根。由於ceil()函式和sqrt()函式皆非標準函式庫裡的函式，使用前必須引用 <math.h> 函式庫。
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main () {
    //宣告並讀取變數T，代表測資筆數
    int T;
    scanf("%d", &T);
    //用for迴圈跑T筆測資
    for(int i = 1 ; i <= T ; i++) {
        //宣告並讀取變數a、b，代表數字範圍的上下限
        //宣告變數sum，設初始值為0，代表a、b之間的完全平方和
        int a, b, sum = 0;
        scanf("%d %d", &a, &b);
        //用for迴圈跑從√a到√b之間的所有數，將他們的平方相加求出平方和
        for(int num = ceil(sqrt(a)) ; num <= sqrt(b) ; num++)
            sum += num*num;
        //輸出
        printf("Case %d: %d\n", i, sum);
    }
    return 0;
}

## [a065. 提款卡密碼](https://zerojudge.tw/ShowProblem?problemid=a065)
**解題思路**
根據題意，7個大寫字母之間的「距離」共6個，即為提款卡密碼。我們可以利用[ASCII碼](https://noah-0831.github.io/a020-%E8%BA%AB%E5%88%86%E8%AD%89%E6%AA%A2%E9%A9%97/)將字母轉為對應的數值，進而求出兩字母間的差值，其絕對值即為「距離」。

:::info
**注意事項**
本程式碼使用了[abs()函式](https://www.runoob.com/cprogramming/c-function-abs.html)對參數求絕對值。由於abs()函式並非標準函式庫裡的函式，使用前須引用 <math.h> 函式庫。
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    //宣告並讀取字元陣列password，代表輸入的7個相連的大寫英文字母
    /*注意以字串形式讀取輸入，再存進字元陣列的話，最後一碼會是空字元。
      因此若要存的字串有7單位長，宣告的字元陣列長度必須在8單位以上*/
    char password[8];
    scanf("%s", password);
    //用for迴圈跑前6個英文字母，輸出他們和下一個英文字母的「距離」，即為提款卡密碼
    for(int i = 0 ; i < 6 ; i++)
        printf("%d", abs(password[i]-password[i+1]));
    return 0;
}

## [a104. 排序](https://zerojudge.tw/ShowProblem?problemid=a104)
**連結題目：[a225. 明明愛排列](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a225-%E6%98%8E%E6%98%8E%E6%84%9B%E6%8E%92%E5%88%97)**

**解題思路**
[為數字排序的方法](https://totoroliu.medium.com/%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-sorting-algorithm-dfd8af673f3a)有很多種，而本題採用[氣泡排序法](https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb)，具體的作法是從第一個元素開始往下檢查，如果兩者的相對順序錯誤，就將兩者的位置對調，接著重新檢查，直到最後一個元素的位置也被確認正確無誤為止。

以本題來說，是要將正整數列由小到大排序，因此我們會從第二個數字開始檢查。如果它比前一個數字，也就是第一個數字還大的話，代表檢查到目前為止，它在數列中的位置是正確的，我們就不會移動他的位置，繼續檢查下去 ; 反之，如果它比前一個數字還小，代表它在數列中的位置不符合題目希望由小到大排序的要求，因此我們會將它與前一個數字的位置對調，然後重新檢查。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用「[EOF](https://noah-0831.github.io/a004-%E6%96%87%E6%96%87%E7%9A%84%E6%B1%82%E5%A9%9A/)寫法」。所謂 EOF 並不是一種真實存在的字元，而是「End Of File」的縮寫，意思是一份檔案的結尾，也可以說是輸入的停止。通常程式在執行時會先讀取輸入，再依據輸入進行相對的行動，但我們未必能知道輸入有幾筆、到什麼時候結束，這時候我們就可以讓電腦自動偵測。一旦它偵測到EOF條件為True，即代表輸入停止，就會結束讀取輸入，如此我們的程式就不用事先指定輸入的筆數，可以不斷讀取輸入並執行直到輸入結束。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數n，代表要排序的數字數量
    int n;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%d", &n) != EOF) {
        //宣告並讀取陣列arr，代表要排序的數字
        int arr[n];
        for(int i = 0 ; i < n ; i++)
            scanf("%d", &arr[i]);
        //氣泡排序法：檢查相鄰兩項之間的關係
        //有由小到大排序來說，若後項比前項還小，就將兩者交換
        for(int i = 1 ; i < n ; i++) {
            for(int j = 0 ; j < i ; j++) {
                if(arr[j] > arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        //輸出排序後的數字
        for(int i = 0 ; i < n ; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
    return 0;
}

## [a121. 質數又來囉](https://zerojudge.tw/ShowProblem?problemid=a121)
**解題思路**
本題給的測資較大，因此我們必須盡可能減少不必要的運算，避免出現TLE的情形。

首先，質數的定義是除了1與自己以外，沒有其他因數的數字。因此在檢查該數是否有因數的時候不用檢查1，可以直接從2開始。

再來，除了完全平方數的因數是1、自己和自己的根號共三個以外，所有數字的因數都是兩兩成對，其中一個小於自己的根號，一個大於自己的根號。因此，我們在檢查該數是否有因數的時候，不必真的逐一檢查到底，只需檢查到該數的根號就好。

最後，我們的目標在於判斷該數是否有因數，進而判斷其是否為質數，而不是找出該數所有的因數。因此，只要找到一個因數，就可以直接跳出迴圈，換下一個數字了。

:::success
**注意事項**
質數的定義是除了1與自己以外，沒有其他因數的數字。1不是質數也不是合數!
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    //宣告變數a、b，代表檢查的上下界
    int a,b;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%d%d", &a, &b) != EOF) {
        //宣告變數ans，代表a到b之間質數的數量
        int ans = 0;
        for(int num = a ; num <= b ; num++) {
            //宣告變數test，設初始值為0，代表該數為質數
            int test = 0;
            /*因為除了完全平方數另有一個因數是自己的根號以外，
              基本上所有數字的因數都是兩兩成對，
              因此可以只檢查到該數的根號就好*/
            for(int i = 2 ; i <= ceil((int)sqrt(num)) ; i++)
                //只要該數有找到一個因數，就將test令為1，然後直接結束此輪檢查
                if(num%i == 0) {
                    test++;
                    break;
                }
            //若test經檢查後仍為0，代表該數為質數
            if(test == 0)
                ans++;
        }
        if(a == 1 || b == 1) //1不是質數也不是合數，因此若a、b為1需將之扣除
            ans--;
        printf("%d\n", ans);
    }
    return 0;
}

## [a147. Print it all](https://zerojudge.tw/ShowProblem?problemid=a147)
**解題思路**
利用for迴圈檢查1到n-1的所有整數是否可被7整除，若該數除以7之後的餘數不為0，代表該數不能被7整除，就將其輸出。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，直到n等於0代表輸入結束。可能有人會想用while(scanf("%d", &n) != 0)這樣的寫法判斷程式結束執行的條件，但須注意**scanf()函式沒有[回傳值](https://noah-0831.github.io/a002-%E7%B0%A1%E6%98%93%E5%8A%A0%E6%B3%95/)**，也就是說他僅會將讀取到的數值存入變數中，而不會回傳，因此這項判斷條件永遠不會成立。如果要使用scanf()函式讀取到的輸入作為判斷條件，必須要先將輸入用指定的變數存起來，再使用該變數的值。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數n，代表判斷範圍的上限
    int n;
    //用while迴圈重複讀取變數n
    while(scanf("%d", &n)) {
        //若n為0，代表輸入結束，直接跳出迴圈
        if(n == 0)
            break;
        //檢查1到n-1之間的整數是否可被7整除
        for(int num = 1 ; num < n ; num++)
            //若該數除以7之後的餘數不為，代表該數不能被7整除，需輸出
            if(num%7 != 0)
               printf("%d ", num);
        printf("\n");
    }
    return 0;
}

## [a148. You Cannot Pass?!](https://noah-0831.github.io/a148-You-Cannot-Pass/)
**解題思路**
題目有多筆測資，當輸入為n時，代表題目希望我們對接下來輸入的n筆成績取平均，再依照平均是否大於59判斷是否過關。我們可以用for迴圈讀取n筆成績並將他們相加，除以n即可得到平均，再依照取完平均後的結果輸出相對應的輸出。

:::success
**注意事項**
注意平均可能為小數，如果用整數型態判斷的話可能會出現誤差。舉例來說，假設今天我們計算出來的平均為59.79，顯然是大於59分的，但若是用整數型態儲存只會存到59。因此此題我們需將平均先轉成浮點數再做判斷。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數n，代表成績筆數
    int n;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%d", &n) != EOF) {
        //宣告變數score，代表輸入的成績
        //宣告變數sum，賦值為0，代表總成績
        int score, sum = 0;
        //用for迴圈讀取n筆成績，並將他們相加得到總成績
        for(int i = 0 ; i < n ; i++) {
            scanf("%d", &score);
            sum += score;
        }
        //若平均大於59.0分，則輸出"no"
        if((float)sum/n > 59.0)
            printf("no\n");
        //若否，則輸出"yes"
        else
            printf("yes\n");
    }
    return 0;
}

## [a149. 乘乘樂](https://zerojudge.tw/ShowProblem?problemid=a149)
**解題思路**
題希望我們求得輸入整數的各個位數乘積。因此，為了方便運算，我們可以先將各個位數視作獨立的字元存放在字元陣列中，再將它們乘起來。

可能會有人好奇，為什麼我們不使用整數陣列存放各個位數呢？這是因為整數陣列讀取時會以空白作為各項的分界，各數字間必須要有空格才會被判定為不同項，而字元陣列則是自動將各個字元單獨存進陣列中。舉例來說，若是輸入的數字為356，因為3、5和6之間沒有以空白隔開，使用整數型態陣列讀取的話只會讀到356一個數字；而字元陣列是將356視為長度為3的字串，因此會將3、5、6分別以字元型態分開存放。

:::success
**注意事項**
為了方便將各個位數分開存放，我們使用字元陣列讀取輸入，但在運算時我們必須將其從字元型態轉回整數型態。至於如何轉換，可以參考我們之前在a009. 解碼器所說的，使用ASCII碼。透過查表可知，0的ASCII碼為48，因此阿拉伯數字的真實值即為其ASCII碼減去48。
:::

**程式碼**

#include <stdio.h>
#include <string.h>
int main() {
    //宣告並讀取變數T，代表測資筆數
    int T;
    scanf("%d", &T);
    //用for迴圈讀取T次輸入的數字
    for(int i = 0 ; i < T ; i++) {
        //以字串的方式讀取，將輸入數字的各個位數轉成字元型態存放在字元陣列中
        char num[11];
        scanf("%s", num);
        //宣告變數product，賦值為1，代表輸入數字各個位數的乘積
        //宣告變數，賦值為0，代表尚未偵測到此數字有位數為0
        int product = 1, test = 0;
        for(int i = 0 ; i < strlen(num) ; i++) {
            //若此位數不為0，就將其與前面的成績相乘
            if(num[i] != 0)
                product *= num[i]-48;
            //若此數字任一位數為0，其各位數乘積必為0，將test設為1後即可跳出迴圈
            else {
                test++;
                break;
            }
        }
        //若test為0，代表此數字沒有位數為0，輸出其乘積
        if(test == 0)
            printf("%d\n", product);
        //若test為1，代表此數字有位數為0，其乘積必為0
        else
            printf("0\n");
    }
    return 0;
}

## [a215. 明明愛數數](https://zerojudge.tw/ShowProblem?problemid=a215)
**解題思路**
題目希望我們找出從n開始，要往下加多少數字總和才會超過m。我們可以利用迴圈重複執行的特性，從n開始將跑過的數字逐一加總，直到總和大於m為止，迴圈的執行次數即為需要的數字數量。

:::success
**注意事項**
相信很多程式教材在討論for迴圈和whle迴圈這兩種常見迴圈的差別時，都會提到for迴圈的特色是可以重複運行指定次數，因此許多程式初學者會誤以為for迴圈在使用時必須指定其運行次數，但其實並非如此。for迴圈和while迴圈真正的差異在於for迴圈有一個變數叫做「迴圈變數」，他的變數值會隨著迴圈運行次數的增加而改變，進而控制for迴圈在特定條件下結束運行，因此才會衍伸出指定運行次數這樣的用法，但我們也可以將其終止條件寫成不同的形式來做更多變化。以本程式碼來說，我們for迴圈的執行條件是sum<=m，也就是說一旦sum的值大於m，for迴圈就會結束執行。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數n、m，分別代表起始數字，以及數字總和的比較標準
    int n, m;
    //使用EOF寫法讀取n、m
    while(scanf("%d %d", &n, &m) != EOF) {
        //宣告變數sum，賦值為n，代表數字總和
        //宣告變數i，代表從n開始，要加幾個數字，數字總和才會大於m
        int sum = n, i;
        //用for迴圈將從n開始的數字逐一加總，直到sum>m為止
        for(i = 1 ; sum <= m ; i++)
            sum += n+i;
        //輸出
        printf("%d\n", i);
    }
    return 0;
}

## [a216. 數數愛明明](https://zerojudge.tw/ShowProblem?problemid=a216)
**解題思路**
這題最直觀的方式是使用迴圈求出f、g值，但有鑑於本題的測資較大，為了避免出現TLE的情況，建議直接找出f(n)、g(n)的關係式以節省運算時間。如果一時之間看不出f(n)、g(n)關係式的話，可以多寫幾項觀察他們的規律。我們會發現f(n)就是連續正整數和，公式為 (n*(n+1))/2；g(n)則可以用數學上的遞迴關係式求得，公式為n*(n+1)*(n+2)/6。

:::success
本題測資較大，部分測資的g(n)會超過int型態變數所能儲存的最大數值，因此需使用[long long型態](https://noah-0831.github.io/a001-%E5%93%88%E5%9B%89/)變數，寫法是%lld。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數n
    long long n;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%lld", &n)!=EOF)
        //輸出f(n)=n*(n+1)/2，輸出g(n)=n*(n+1)*(n+2)/6
        printf("%lld %lld\n", n*(n+1)/2, n*(n+1)*(n+2)/6);
    return 0;
}

## [a224. 明明愛明明](https://zerojudge.tw/ShowProblem?problemid=a224)
**連結題目：[a022. 迴文](https://hackmd.io/8wBqbi0mSV6mPg9bcNGJ3Q?view#a022-%E8%BF%B4%E6%96%87)**

**解題思路**
本題乍看之下就是單純判斷輸入字串是否為迴文，但須注意本題對迴文的定義是「只要重新安排順序後，符合迴文條件就算迴文」，也就是說字串的在輸入時的排列順序未必與可以形成迴文的順序相同。因此我們不能用當時[a022. 迴文](https://noah-0831.github.io/a022-%E8%BF%B4%E6%96%87/)的想法，直接頭尾一組檢查字元是否相同，必須換種作法才行。

根據定義，迴文字串必定頭尾對稱，換句話說最多只能有一種字母出現奇數次。因此，我們可以藉由檢查測資中各字母出現的次數，來判斷重新排列後是否可以形成迴文字串。若有一種以上的字母出現奇數次則非迴文；而若是26個字母檢查完接皆未出現上述情況則為迴文。

:::success
**注意事項**
在了解如何判斷迴文字串後，本題還有另兩點需要注意。
第一，本題的測資夾雜了非英文字母的字元，在判斷時需將這些字元忽略。
第二，大寫和小寫字母在本題視為相同，在判斷字母出現次數時須特別注意。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告字元陣列input，並以字串形式讀取，代表輸入的測資
    char input[1000];
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%s", input) != EOF) {
        //宣告陣列alphabet，代表各個英文字母出現的次數（不分大小寫）
        //宣告變數num，代表出現次數為偶數的英文字母數量
        //宣告變數test，代表是否為迴文字串
        int alphabet[26] = {}, num = 0, test = 1;
        //逐一判斷輸入字元為何，計算各個英文字母出現的次數
        for(int i = 0 ; input[i] != '\0' ; i ++)
            switch(input[i]) {
                case 65: //檢查A
                case 97: //檢查a
                    alphabet[0] ++;
                    break;
                case 66: //檢查B
                case 98: //檢查b
                    alphabet[1] ++;
                    break;
                case 67: //檢查C
                case 99: //檢查c
                    alphabet[2] ++;
                    break;
                case 68: //檢查D
                case 100: //檢查d
                    alphabet[3] ++;
                    break;
                case 69: //檢查E
                case 101: //檢查e
                    alphabet[4] ++;
                    break;
                case 70: //檢查F
                case 102: //檢查f
                    alphabet[5] ++;
                    break;
                case 71: //檢查G
                case 103: //檢查g
                    alphabet[6] ++;
                    break;
                case 72: //檢查H
                case 104: //檢查h
                    alphabet[7] ++;
                    break;
                case 73: //檢查I
                case 105: //檢查i
                    alphabet[8] ++;
                    break;
                case 74: //檢查J
                case 106: //檢查j
                    alphabet[9] ++;
                    break;
                case 75: //檢查K
                case 107: //檢查k
                    alphabet[10] ++;
                    break;
                case 76: //檢查L
                case 108: //檢查l
                    alphabet[11] ++;
                    break;
                case 77: //檢查M
                case 109: //檢查m
                    alphabet[12] ++;
                    break;
                case 78: //檢查N
                case 110: //檢查n
                    alphabet[13] ++;
                    break;
                case 79: //檢查O
                case 111: //檢查o
                    alphabet[14] ++;
                    break;
                case 80: //檢查P
                case 112: //檢查p
                    alphabet[15] ++;
                    break;
                case 81: //檢查Q
                case 113: //檢查q
                    alphabet[16] ++;
                    break;
                case 82: //檢查R
                case 114: //檢查r
                    alphabet[17] ++;
                    break;
                case 83: //檢查S
                case 115: //檢查s
                    alphabet[18] ++;
                    break;
                case 84: //檢查T
                case 116: //檢查t
                    alphabet[19] ++;
                    break;
                case 85: //檢查U
                case 117: //檢查u
                    alphabet[20] ++;
                    break;
                case 86: //檢查V
                case 118: //檢查v
                    alphabet[21] ++;
                    break;
                case 87: //檢查W
                case 119: //檢查w
                    alphabet[22] ++;
                    break;
                case 88: //檢查X
                case 120: //檢查x
                    alphabet[23] ++;
                    break;
                case 89: //檢查Y
                case 121: //檢查y
                    alphabet[24] ++;
                    break;
                case 90: //檢查Z
                case 122: //檢查z
                    alphabet[25] ++;
                    break;
            }

        for(int i = 0 ; i < 26 ; i ++) {
            //若有一種以上的字母出現奇數次，則非迴文
            if(alphabet[i]%2 == 1)
                num ++;
            if(num == 2) {
                printf("no...\n");
                test = 0;
                break;
            }
        }
        //若26個字母檢查完接皆未出現上述情況，則為迴文
        if(test == 1)
            printf("yes !\n");
    }
    return 0;
}

## [a225. 明明愛排列](https://zerojudge.tw/ShowProblem?problemid=a225)
**連結題目：[a104. 排序](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a104-%E6%8E%92%E5%BA%8F)**

**解題思路**
[為數字排序的方法](https://totoroliu.medium.com/%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-sorting-algorithm-dfd8af673f3a)有很多種，而本題採用[氣泡排序法](https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb)，具體的作法是從第一個元素開始往下檢查，如果兩者的相對順序錯誤，就將兩者的位置對調，接著重新檢查，直到最後一個元素的位置也被確認正確無誤為止。

以本題來說，是要將輸入的數字按個位數由小到大排列，因此我們會從第二個數字開始檢查。如果它的個位數比前一個數字的個位數還大的話，代表檢查到目前為止，它在數列中的位置是正確的，我們就不會移動他的位置，繼續檢查下去；反之則需將它與前一個數字的位置對調，然後重新檢查；若是兩個數字的個位數相同，則依照數字的數值由大到小排列。

:::success
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用「[EOF](https://noah-0831.github.io/a004-%E6%96%87%E6%96%87%E7%9A%84%E6%B1%82%E5%A9%9A/)寫法」。所謂 EOF 並不是一種真實存在的字元，而是「End Of File」的縮寫，意思是一份檔案的結尾，也可以說是輸入的停止。通常程式在執行時會先讀取輸入，再依據輸入進行相對的行動，但我們未必能知道輸入有幾筆、到什麼時候結束，這時候我們就可以讓電腦自動偵測。一旦它偵測到EOF條件為True，即代表輸入停止，就會結束讀取輸入，如此我們的程式就不用事先指定輸入的筆數，可以不斷讀取輸入並執行直到輸入結束。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告變數n，代表有幾個數字需要排序
    int n;
    //使用EOF寫法判斷程式執行的條件
    while(scanf("%d", &n) != EOF) {
        //宣告並讀取陣列arr，代要排序的數字
        int arr[n];
        for(int i = 0 ; i < n ; i++)
            scanf("%d", &arr[i]);
        //氣泡排序法：檢查相鄰兩項之間的關係
        //有由小到大排序來說，若後項比前項還小，就將兩者交換
        for(int i = 1 ; i < n ; i++)
            for(int j = 0 ; j < i ; j++) {
                //以個位數做排序標準，依個位數數值由小到大排列
                if(arr[j]%10 > arr[i]%10) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
                //若個位數相同，則將其由大到小排列
                else if(arr[j]%10 == arr[i]%10 && arr[j] < arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        //輸出排序後的數字
        for(int i = 0 ; i < n ; i++)
            printf("%d ", arr[i]);
        printf("\n");
    }
    return 0;
}

## [a229. 括號匹配問題](https://zerojudge.tw/ShowProblem?problemid=a229)
**連結題目：[a524. 手機之謎](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a524-%E6%89%8B%E6%A9%9F%E4%B9%8B%E8%AC%8E)**

**解題思路**
根據題意，我們要找出對於n個左括號和n個右括號來說，所有合法的，也就是說「任一點左括號數量皆大於等於右括號」的匹配組合。因為相信多數人和我一樣，沒辦法從題目敘述中找出規律，因此本題我們使用[遞迴](https://openhome.cc/Gossip/CGossip/Recursion.html)排除已經輸出的情況，列舉出所有的可能性。

想要了解什麼是遞迴，必須先知道有關函數的觀念。在[a002. 簡易加法](https://noah-0831.github.io/a002-%E7%B0%A1%E6%98%93%E5%8A%A0%E6%B3%95/)，我們曾經提過函式是一種可以執行特定功能的程式區塊。當我們呼叫函式時，電腦就會執行函式內的程式。那麼，如果我在函式內呼叫了這個函式本身，會發生什麼事情呢？因為每當電腦執行函式時，都會再次收到我們的函式呼叫，因此電腦將不斷重複執行這個函式。這就是遞迴，藉由在函式內呼叫函式本身，形成循環以重複執行程式。

以本題來說，假設我們今天有num組括號要匹配，可以想像成是有一個長度為 2 x num 的陣列，在這個陣列的每個項，我們都可以選擇要放左括號還是右括號。因此，我們宣告一個函式，讓他從第1項跑到第 2 x num 項。在討論每個項，或者說跑到每個節點時，我們都使用遞迴分別跑一次選擇左括號和右括號的情況，直到跑到最後一個節點，即跑完所有的匹配組合。

在確定所有可能的匹配組合都有被討論到後，接下來我們要為遞迴加上限制條件，將我們真正想要的匹配組合留下。首先，雖然我們在各個位子都有左括號和右括號兩種選擇，但因為括號是兩兩一組的，因此左括號和右括號的總數都不應超過num個，如果我們跑一跑發現左括號或右括號的總數超過num的話，就不用再跑下去了；再來，合法的匹配組合在任一點的左括號數量一定大於等於右括號，因此如果我們跑一跑發現左括號的數量小於右括號，代表這不是合法的匹配組合，也不用再跑下去了。如此一來，跑到最後的匹配組合，一定都是合法的，就可以放心輸出了！

:::success
**注意事項**
遞迴是一種重複執行程式的方法，概念是先宣告一個函式，藉由在函式內呼叫函式本身，讓程式不斷跑下去。和同樣是重複執行程式的迴圈不同的是，迴圈的每一次運行都是從頭開始，常用於重複執行指定的動作；而遞迴因為會返回距離最近的「節點」，可以跑過每個節點、每個選擇的所有可能性，完成具有「分支」的討論，進一步運用在[深度優先演算法(DFS)](https://dotblogs.com.tw/ilikedogs/2020/03/23/151856)上。因此，推薦大家在學習完函式與迴圈後，可以試著[學習遞迴](https://medium.com/appworks-school/%E9%80%B2%E5%85%A5%E9%81%9E%E8%BF%B4-recursion-%E7%9A%84%E4%B8%96%E7%95%8C-%E4%B8%80-59fa4b394ef6)。
:::

**程式碼**

#include <stdio.h>
//宣告變數n，代表總共有幾組括號要匹配
//宣告變數num，令其值為2*n，代表總共有幾個位子要討論
int n, num;
//宣告一長度為30的陣列arr，代表可能的括號匹配組合
char arr[30];
//宣告回傳值為void型態（不回傳）的函式dfs，討論每一項的可能性
//宣告變數now，代表現在討論到第幾項，或者說跑到第幾個節點
//宣告變數left、right，分別代表現在左括號和右括號的數量
void dfs(int now, int left, int right) {
    //若左括號或右括號數量大於n，或是左括號數量小於右括號，皆為不合法的匹配組合，可以直接返回
    if(left > n || left < right)
        return;
    //若跑到第num個節點，而沒有被終止，代表這是合法的匹配組合，可以輸出
    /*在結尾補/0再輸出字串，比以for迴圈輸出字元陣列快*/
    if(now == num) {
        arr[num] = '\0'; 
        printf("%s\n", arr);
        return;
    }
    //若此節選擇的是左括號，將左括號數量加一後進入下一項的討論
    arr[now] = '('; 
    dfs(now+1, left+1, right); 
    //若此節選擇的是右括號，將右括號數量加一後進入下一項的討論
    arr[now] = ')';
    dfs(now+1, left, right+1);
}
//主函式
int main() {
    //使用EOF寫法讀取每次輸入的n值
    while(scanf("%d", &n) != EOF) {
        /*在這裡先把num算出來，每筆測資只需算一次，比每次遞迴時都將條件設為2*n快*/
        num = 2*n;
        //呼叫函式dfs，藉由遞迴跑過所有可能的括號匹配組合，再將合法的匹配組合輸出 
        dfs(0, 0, 0);
    }
    return 0;
}

## [a240. 1/17小數第 n 位](https://zerojudge.tw/ShowProblem?problemid=a240)
**連結題目：[a248. 新手訓練 ~ 陣列應用](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a248-%E6%96%B0%E6%89%8B%E8%A8%93%E7%B7%B4--%E9%99%A3%E5%88%97%E6%87%89%E7%94%A8)**

**解題思路**
我們可以模擬直式除法，將運算過程拆成一位一位來看，每次都先將現在的數字乘上10倍作被除數，取商數後將其存進陣列中，再將餘令為新的被除數，最後輸出陣列即可得商。

舉例來說，我們先將1乘以10變10，10除以17得0，因此1除以17的小數點後第一位即為0。接者我們再將10乘以10變100作新的被除數，100除以17得5，即為1除以17的小數點後第二位。接著我們將100減去17乘5後得15，再乘以10就會是新的被除數150，以此類推。

:::info
**注意事項**
這一題和[a248. 新手訓練 ~ 陣列應用](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a248-%E6%96%B0%E6%89%8B%E8%A8%93%E7%B7%B4--%E9%99%A3%E5%88%97%E6%87%89%E7%94%A8)的概念十分相似。或者說，本題其實就是a248在a=1，b=17時的情況。因此，如果已經寫完本題的人，可以試著挑戰a248。
:::

**程式碼**

#include <stdio.h>
int main() {
    int t;
    scanf("%d", &t);
    for(int i=0;i<t;i++) {
        int n;
        scanf("%d", &n);
        int num=1, ans[n], sum=0;
        for(int i=0;i<n;i++) {
            num*=10;
            ans[i]=num/17;
            num-=ans[i]*17;
            sum+=ans[i];
        }
        printf("%d %d\n", ans[n-1], sum);
    }
    return 0;
}

## [a244. 新手訓練 ~ for + if](https://zerojudge.tw/ShowProblem?problemid=a244)
**解題思路**
使用scanf()函式讀取測資，再使用switch()函式依照a值輸出不同種類的運算結果。

:::success
**注意事項**
在[a002. 簡易加法](https://noah-0831.github.io/a002-%E7%B0%A1%E6%98%93%E5%8A%A0%E6%B3%95/)，我們曾提過不同種類的資料型態。以整數來說，較常使用的資料型態是int，可儲存-2,147,483,648至2,147,483,647的整數。但本題測資較大，部分測資的運算結果會超過int型態變數所能儲存的最大數值，因此需使用long long型態的變數儲存輸入，寫法是%lld。
:::

**程式碼**

#include <stdio.h>
int main() {
    //宣告並讀取變數N，代表測資筆數
    int N;
    scanf("%d", &N);
    //使用for迴圈跑過每一筆測資
    for(int i = 0 ; i < N ; i++) {
        //宣告並讀取變數a、b、c
        long long a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        //根據a值輸出相對應的結果
        switch(a) {
            //若a為1，輸出b+c
            case 1:
                printf("%lld\n", b+c);
                break;
            //若a為2，輸出b-c
            case 2:
                printf("%lld\n", b-c);
                break;
            //若a為3，輸出b*c
            case 3:
                printf("%lld\n", b*c);
                break;
            //若a為4，輸出b/c
            case 4:
                printf("%lld\n", b/c);
                break;
        }
    }
    return 0;
}

## [a248. 新手訓練 ~ 陣列應用](https://zerojudge.tw/ShowProblem?problemid=a248)
**連結題目：[a240. 1/17小數第 n 位](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a240-117%E5%B0%8F%E6%95%B8%E7%AC%AC-n-%E4%BD%8D)**

**解題思路**
一般來說，要顯示除法運算後所得的商數，可以直接用將商數用一浮點數型態的變數儲存起來，在輸出時再設定要顯示到第幾位。然而根據輸出說明，本題最多要顯示到小數點後第10000位，明顯超出任何資料型態的變數的儲存範圍。因此，我們可以改模擬直式除法，將運算過程拆成一位一位來看，每次都先將現在的數字乘上10倍作被除數，取商數後將其存進陣列中，再將餘令為新的被除數，最後輸出陣列即可得商。

舉1除以17為例，我們先將1乘以10變10，10除以17得0，因此1除以17的小數點後第一位即為0。接者我們再將10乘以10變100作新的被除數，100除以17得5，即為1除以17的小數點後第二位。接著我們將100減去17乘5後得15，再乘以10就會是新的被除數150，以此類推。

:::info
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](
https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    int a, b, N;
    while(scanf("%d%d%d", &a, &b, &N)!=EOF) {
        printf("%d.", a/b);
        a%=b;

        int ans[N];
        for(int i=0;i<N;i++) {
            a*=10;
            ans[i]=a/b;
            a-=ans[i]*b;
            printf("%d", ans[i]);
        }
        printf("\n");

    }
    return 0;
}

## [a263. 日期差幾天](https://zerojudge.tw/ShowProblem?problemid=a263)
**解題思路**
根據題意，我們必須求出兩個日期相差幾天。因為對我們來說，完整的一年或是一個月的天數比較好算，所以我們先算從第一筆日期的下個到第二筆日期的上個月之間的天數，再把頭尾沒算到的天數補上。

舉例來說，假如測資的兩個日期分別是2020年1月28日和2023年4月3日，我們可以先算2020年2月初到2023年3月底的天數，也就是335+365+365+90=1155天。接著我們再算剛剛還沒算到的頭尾的天數，也就是3+3=6天。據此，可知2020年1月28日到2023年4月3日共相差1155+6=1161天。

:::info
**注意事項**
注意第二筆日期未必比第一筆日期晚。因此如果我們要用第二筆日期減去第一筆日期來計算兩者間隔幾天，需先檢查兩筆日期何者較晚。若第二筆日期比第一筆日期早，須將兩者交換。
:::

**程式碼**

#include <stdio.h>
int main() {
    int year1, month1, date1, year2, month2, date2;
    while(scanf("%d%d%d%d%d%d", &year1, &month1, &date1, &year2, &month2, &date2)!=EOF) {

        if(year1>year2) {
            int temp=year1;
            year1=year2;
            year2=temp;
            temp=month1;
            month1=month2;
            month2=temp;
            temp=date1;
            date1=date2;
            date2=temp;
        }
        else if(year1==year2 && month1>month2) {
            int temp=month1;
            month1=month2;
            month2=temp;
        }
        else if(year1==year2 && month1==month2 && date1>date2) {
            int temp=date1;
            date1=date2;
            date2=temp;
        }

        int output=0;
        for(int i=year1+1;i<year2;i++) {
            if(i%4==0 && i%100!=0 || i%100==0 && i%400==0)
                output+=366;
            else
                output+=365;
        }

        output=output-date1;
        for(int i=month1;i<=12;i++) {
            if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12)
                output+=31;
            else if(i==2) {
                if(year1%4==0 && year1%100!=0 || year1%100==0 && year1%400==0)
                    output+=29;
                else
                    output+=28;
            }
            else
                output+=30;
        }

        for(int i=1;i<month2;i++) {
            if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12)
                output+=31;
            else if(i==2) {
                if(year2%4==0 && year2%100!=0 || year2%100==0 && year2%400==0)
                    output+=29;
                else
                    output+=28;
            }
            else
                output+=30;
        }
        output+=date2;

        if(year1==year2)
            if(year1%4==0 && year1%100!=0 || year1%100==0 && year1%400==0)
                output-=366;
            else
                output-=365;

        printf("%d\n", output);
    }
    return 0;
}

## [a271. 彩色蘿蔔](https://zerojudge.tw/ShowProblem?problemid=a271)
**解題思路**
根據題意，本題有多筆測資。
每筆測資的第一行有x, y, z, w, n, m六個數字，分別代表:
x:吃紅蘿蔔後，體重+x公斤
y:吃白蘿蔔後，體重+y公斤
z:吃黃蘿蔔後，體重-z公斤
w:吃黑蘿蔔後，體重-w公斤，並且進入中毒狀態(可疊加)
n:進入中毒狀態後，體重每日-n公斤
m:兔子初始的體重
每筆測資的第二行有未知個數字(可能沒有數字)，分別代表:
0:沒吃蘿蔔
1:吃紅蘿蔔
2:吃白蘿蔔
3:吃黃蘿蔔
4:吃黑蘿蔔
而我們的目標是計算並輸出兔子的體重，一旦過程中兔子體重小於等於0，則必須立即輸出「bye~Rabbit」。

比起體重的計算，本題最困難的地方在於讀取輸入測資，有兩個比較需要注意的地方。第一是**測資第一行和第二行之間存在回車鍵(\n)**，因此為了避免在讀取每日吃的蘿蔔種類時將其讀入，我們可以先將其用字元變數c讀起來 ; 第二是**每筆測資的第二行數字的數量並不固定，甚至有可能沒有輸入**。如果用常見的scanf()函式偵測輸入，我們會不知道要在哪裡停止偵測而TLE。這裡的做法是使用gets()函式將整行輸入連同空白，以字串的形式讀進來。

再讀取到輸入以後，我們可以用for迴圈從第0項開始，以switch()函式判斷每日吃的蘿蔔種類，再對體重進行相對應的運算。這裡比較需要注意的地方有三個。第一是**空白項的避免**。因為剛剛讀取輸入的時候是整行連同空白讀進來，因此每項之間會夾雜一項空格，可以使用continue敘述略過對空白項的判斷，或是直接將for迴圈控制變數的遞增條件設定成+=2跳過空白項 ; 第二是**中毒狀態的計算**。因為兔子是早上先中毒，晚上才吃東西，所以吃到黑蘿蔔後要到隔天早上才會進入中毒狀態，吃黑蘿蔔當天的體重不會-n。第三是**兔子是否死亡的判斷**，兔子可能死亡的情況有兩個，分別是因中毒狀態而死，以及吃到不好的蘿蔔後體重減輕而死。因此在判斷兔子因中毒狀態導致的體重變化和吃完蘿蔔後的體重判斷後，都必須判斷兔子體重是否小於等於0。在注意上述幾點後，相信你也可以AC的!

:::info
**注意事項**
本程式碼使用了strlen()函式表示字串的長度。由於strlen()函式並非標準函式庫裡的函式，使用前必須引用<string.h>函式庫。
:::

**程式碼**

#include <stdio.h>
#include <string.h>
int main() {
    int N;
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        int x, y, z, w, n, m, poison=0;
        scanf("%d%d%d%d%d%d", &x, &y, &z, &w, &n, &m); /*讀取測資第一行的輸入*/
        char c=getchar(); /*讀取測資第一行和第二行之間的回車鍵，避免在讀取每日吃到的蘿蔔種類時讀到*/
        char carrot[1000]={}; /*注意這裡的測資數量較大，因此這裡的陣列大小也要令大一點，否則會出現記憶體區段錯誤，系統會呼叫abort()函式中斷程式執行*/
        gets(carrot); /*讀取測資第二行的輸入，直接以字串形式整行連同空白讀進來*/

        for(int j=0;j<strlen(carrot);j+=2) { /*因為剛剛有讀到空白，因此設定i+=2跳過空白項*/
            m-=poison*n; /*早上進入中毒狀態，體重因中毒而減輕*/
            if(m<=0) { /*判斷兔子是否因中毒狀態而死*/
                printf("bye~Rabbit\n");
                break;
            }
            switch(carrot[j]) { /*根據兔子每日吃的蘿蔔種類，對體重進行相對應的運算*/
                case '0': /*沒吃蘿蔔*/
                    break;
                case '1': /*吃紅蘿蔔*/
                    m+=x; /*體重+x公斤*/
                    break;
                case '2': /*吃白蘿蔔*/
                    m+=y; /*體重+y公斤*/
                    break;
                case '3':  /*吃黃蘿蔔*/
                    m-=z; /*體重-z公斤*/
                    break;
                case '4':  /*吃黑蘿蔔*/
                    m-=w; /*體重-w公斤*/
                    poison++;  /*隔天早上才進入中毒狀態，因此先註記起來但不用減少體重*/
                    break;
            }
            if(m<=0) { /*判斷兔子是否因吃到不好的蘿蔔後體重減輕而死*/
                printf("bye~Rabbit\n");
                break;
            }
        }
        if(m>0)
           printf("%dg\n", m);
    }
    return 0;
}

## [a291. nAnB problem](https://zerojudge.tw/ShowProblem?problemid=a291)
**解題思路**
由題目可知輸入的數字可以被分為三種情況。第一種是A，代表該數字有出現在密碼中，且位置與密碼相同；第二種是B，代表該數字有出現在密碼中，但位置與密碼不同；第三種是該數字並未出現在密碼中。而我們的目標，是找到並輸出A與B的數量。

其中A的部分只要用for迴圈檢查輸入數列與密碼在各個位置相同的數量即可，但B的數量就比較難判斷了，因為可能有「該數字的確有出現在密碼中，可是數量沒這麼多」的情況。舉密碼為1234，輸入數列為1111的情況為例，雖然輸入數列的四個數字都有出現在密碼中，但密碼只有一個1，因此正確答案應該是1A0B，而不是1A3B。為了避免誤判這樣的情況，這裡的想法是先比對密碼與輸入數列各個數字的數量，由兩者中較小的值可知該數字重複出現在兩者的次數，也就是A+B，減去A之後就可以得到B了!

:::info
**注意事項**
在本程式碼第101行，我們會看到「[條件運算子](https://shengyu7697.github.io/cpp-ternary-operator/)」的寫法，也就是「(條件)？(敘述1)：(敘述2)」。在執行到這行程式的時候，會依據條件決定接下來的動作。如果符合條件就回傳敘述1的值，否則回傳敘述2的值。以本程式碼為例，若password_class[i]大於等於input_class[i]，那麼q的值將會加上input_class[i]，否則會加上password_class[i]。

雖然對於初學者來說，這的確是一個較少機會接觸的寫法。但因為概念簡單且使用便利，在這裡就先介紹給大家了。事實上用if條件句也可以達成一樣的功能，只是程式碼會比較長，就看各位的取捨了。
:::

**程式碼**

#include <stdio.h>
int main() {
    int temp;
    while(scanf("%d", &temp)!=EOF) {

        int password_class[10];
        for(int i=0;i<10;i++)
            password_class[i]=0;

        int password[4];
        for(int i=0;i<4;i++) {
            if(i==0)
                password[i]=temp;
            else
                scanf("%d", &password[i]);

            switch(password[i]) {
                case 0:
                    password_class[0]++;
                    break;
                case 1:
                    password_class[1]++;
                    break;
                case 2:
                    password_class[2]++;
                    break;
                case 3:
                    password_class[3]++;
                    break;
                case 4:
                    password_class[4]++;
                    break;
                case 5:
                    password_class[5]++;
                    break;
                case 6:
                    password_class[6]++;
                    break;
                case 7:
                    password_class[7]++;
                    break;
                case 8:
                    password_class[8]++;
                    break;
                case 9:
                    password_class[9]++;
                    break;
            }
        }

        int n;
        scanf("%d", &n);
        for(int i=0;i<n;i++) {

            int input_class[10];
            for(int i=0;i<10;i++)
                input_class[i]=0;

            int input[4], p=0, q=0;
            for(int j=0;j<4;j++) {
                scanf("%d", &input[j]);

                if(input[j]==password[j])
                    p++;

                switch(input[j]) {
                    case 0:
                        input_class[0]++;
                        break;
                    case 1:
                        input_class[1]++;
                        break;
                    case 2:
                        input_class[2]++;
                        break;
                    case 3:
                        input_class[3]++;
                        break;
                    case 4:
                        input_class[4]++;
                        break;
                    case 5:
                        input_class[5]++;
                        break;
                    case 6:
                        input_class[6]++;
                        break;
                    case 7:
                        input_class[7]++;
                        break;
                    case 8:
                        input_class[8]++;
                        break;
                    case 9:
                        input_class[9]++;
                        break;
                }
            }

            for(int i=0;i<10;i++)
                q+=(password_class[i]>=input_class[i]) ? input_class[i] : password_class[i];
            q-=p;

            printf("%dA%dB\n", p, q);
        }
    }
    return 0;
}

## [a410. 解方程](https://zerojudge.tw/ShowProblem?problemid=a410)
**解題思路**
根據國中所學，二元一次聯立方程式解的情形有三種，分別是恰一組解、無(實數)解或是有無限多組解。本程式碼採用[克拉瑪公式](https://www.ehanlin.com.tw/app/keyword/%E9%AB%98%E4%B8%AD/%E6%95%B8%E5%AD%B8/%E5%85%8B%E6%8B%89%E7%91%AA%E5%85%AC%E5%BC%8F.html)，是一種利用兩方程式的係數比關係，判斷二元一次聯立方程式解的情況的方法。在確定方程式恰有一組解後，就可以利用加減消去法、代入消去法等方式求解了。


:::info
**注意事項**
本題要求輸出解至小數點後二位，但方程式的係數是整數。而我們知道如果將兩int型態的變數相除，商也會是int型態，也就是說程式會自動將其無條件捨去至整數位。因此求解的時候須注意資料型態的轉換。

另外在本程式碼第8行，我們會看到「%.2」。這是一個特殊寫法，可以控制讀取與輸入的精確度。以「%a.b」來說，a代表的是總長度，b是精確度，即小數點後的位數。
:::

**程式碼**

#include <stdio.h>
int main() {
    int a, b, c, d, e, f;
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    float x, y;

    if(a*e-b*d!=0) /*利用克拉瑪公式判斷解的情形*/
        printf("x=%.2f\ny=%.2f\n", (float)(c*e-f*b)/(float)(a*e-d*b), (float)(c*d-f*a)/(float)(b*d-e*a)); /*利用加減消去法求解*/
    else if(a*e-b*d==0 && (a*e-b*d!=0) || (a*f-c*d!=0))
        printf("No answer");
    else
        printf("Too many");
    return 0;
}

## [a414. 位元運算之進位篇](https://zerojudge.tw/ShowProblem?problemid=a414)
**解題思路**
根據題意，我們必須求出一個十進制數字加1後，在二進制中進位的次數。而因為在二進制中，只要該位數的數值大於等於二就會進位，因此所謂「加1後在二進制中進位的次數」，其實就是「該數字在二進制中，從右側數來連續的1的個數」。舉例來說，十進制的11在二進制中為1011，從右側數來連續的1有2個，因此可知需進位2次。

據此，我們可以藉由將輸入的數字不斷除以2，從該數字在二進制中最高的位數開始降次檢查。並藉由該數字除以2是否餘1，判斷該數字在二進制中最右側的數字是否為1。進而得知該數字在二進制中，從右側數來連續的1的個數。

:::info
**注意事項**
布林代數是一種變數，可分為0和1，當其值為0的時候代表false，為1(或其他正整數)時代表true。在下面的程式碼中，我們會看到while(1){}的寫法，這裡的1即為布林值，也就是說這個while迴圈的條件永遠成立，會不斷執行下去，直到遇到break敘述為止。
:::

**程式碼**

#include <stdio.h>
int main() {
    while(1) {
        int num, time=0;
        scanf("%d", &num);
        if(num==0)
            break;
        while(num%2==1) {
            num/=2;
            time++;
        }
        printf("%d\n", time);
    }
    return 0;
}

## [a417. 螺旋矩陣](https://zerojudge.tw/ShowProblem?problemid=a417)
**解題思路**
透過觀察規律可知，本題螺旋矩陣中的元素是從1到N^2^的連續正整數。順序是從左上角的1開始，若方向是順時鐘則先往右、再往下、再往左、再往上，若方向是逆時鐘則則先往下、再往右、再往上、再往左，逐一填入元素，形成一個循環。因此，我們可以宣告一個二維陣列，從(0,0)開始，藉由迴圈與條件句，判斷下一步移動的方向，進而填完整個陣列。

本題的解題關鍵是判斷要移動幾步再變換方向。第一次移動時會移動N步再換方向，接下來的步數從N-1開始，每兩次遞減。舉N=3、M=1的情況微例，因為是順時鐘方向，因此從(0,0)出發，先往右3步到(2,0)，再往下2步到(2,2)，再往左2步到(0,2)，再往上1步到(0,1)，最後再往右一步到(1,1)。

:::info
**注意事項**
根據題意，矩陣值之間寬度為5。因此在本程式碼第59行，我們會看到「printf("%5d", arr[row][column]);」的寫法，其中%5d的5指的就是每筆輸出之間的距離，會以空白補上。(注意不要用手動輸出空白的方式，很容易出錯)
:::

**程式碼**

#include <stdio.h>
int main() {
    int T;
    scanf("%d", &T);
    for(int i=0;i<T;i++) {
        int N, M;
        scanf("%d %d", &N, &M);
        int arr[N][N], direction=0, row=0, column=0, length=N, test=1, time=0;
        for(int j=0;j<N*N;j++) {
            arr[row][column]=j+1;
            test++;
            
            if(M==1)
                switch(direction) {
                    case 0:
                        column++;
                        break;
                    case 1:
                        row++;
                        break;
                    case 2:
                        column--;
                        break;
                    case 3:
                        row--;
                        break;
                }
            else if(M==2)
                switch(direction) {
                    case 0:
                        row++;
                        break;
                    case 1:
                        column++;
                        break;
                    case 2:
                        row--;
                        break;
                    case 3:
                        column--;
                        break;
                }

            if(test==length) {
                direction++;
                direction%=4;
                time++;
                test=1;
                if((time==3 && length==N) || (time==2 && length!=N)) {
                    length--;
                    time=0;
                }
            }
        }

        for(row=0;row<N;row++) {
            printf("%d", arr[row][0]);
            for(column=1;column<N;column++)
                    printf("%5d", arr[row][column]);

            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

## [a524. 手機之謎](https://zerojudge.tw/ShowProblem?problemid=a524)
**連結題目：[a981. 求和問題](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a981-%E6%B1%82%E5%92%8C%E5%95%8F%E9%A1%8C)**

**解題思路**
根據題意，本題希望我們列舉出從1到n的連續正整數集合可能的排列情形。因為我們必須排除已經輸出的情況，列舉出所有的可能性，因此我們採用[遞迴](https://medium.com/appworks-school/%E9%80%B2%E5%85%A5%E9%81%9E%E8%BF%B4-recursion-%E7%9A%84%E4%B8%96%E7%95%8C-%E4%B8%80-59fa4b394ef6)來解決這題。具體的想法是從n開始檢查，若該數字未被輸出過則將其輸出並加以後標註，直到組成1個長度為n的陣列後輸出結果並返回，藉由遞迴走過所有可能性。

:::info
**注意事項**
[遞迴](https://medium.com/appworks-school/%E9%80%B2%E5%85%A5%E9%81%9E%E8%BF%B4-recursion-%E7%9A%84%E4%B8%96%E7%95%8C-%E4%B8%80-59fa4b394ef6)是一種基本的程式運用，概念是先宣告一個函式，藉由在函式內呼叫函式本身，形成一個可以不斷重複執行的循環。作為一種重複執行的方式，遞迴常會被和迴圈比較，但遞迴因為會返回距離最近的「節點」，可以完成具有「分支」的討論，並進一步運用在[深度優先演算法(DFS)](https://dotblogs.com.tw/ilikedogs/2020/03/23/151856)上。因此，希望大家在熟練條件句與迴圈的運用後，可以開始學習遞迴!
:::

**程式碼**

#include <stdio.h>
int n, step[9], check[9]={};
void dfs(int now) {
    if(now==n+1) { /*若已經走過n個數字，代表已經完成一種情況的討論，輸出後返回*/
        for(int i=1;i<=n;i++)
            printf("%d", step[i]);
        printf("\n");
        return;
    }
    for(int i=n;i>0;i--) /*從n開始檢查*/
        if(check[i]==0) { /*若該數還未走過*/
            step[now]=i; /*將陣列當下的項設為該數*/
            check[i]=1; /*將該數標記為走過*/
            dfs(now+1); /*遞迴*/
            check[i]=0; /*遞迴完是新的情況討論，須將該數是否走過的標記歸零*/
        }
}
int main() {
    while(scanf("%d", &n)!=EOF)
        dfs(1);
    return 0;
}

## [a647. 投資專家](https://zerojudge.tw/ShowProblem?problemid=a647)
**解題思路**
由題意可知本題測資會有n、m、p三種數字。其中n代表測資數量，m代表當時買進藝術品的成本，p代表該藝術品現在的價值。我們必須計算從m到p的獲利率，並根據獲利率的數值決定是否出售。因此，只要用p/m-1計算出獲利率，再根據其數值輸出相對應的數值即可。

:::info
**注意事項**
感謝k963852741大的解題報告!

可能很多人的獲利率會在第三筆測資出錯，這是因為所謂「精度」的問題。當進行除法運算，商數的位數超出其資料型態所能儲存的最大位數時，會將其後的數字無條件捨去。然而本題要求四捨五入，因此當無條件捨去與四捨五入所得數值存在誤差時就會WA。如0.249999...這樣後面為9循環的小數，在數學上應被判讀為0.25，但若是變數的資料型態只能存到小數點後第二位，會自動從小數點第二位無條件捨去而被儲存為0.24，進而產生誤差。

對此，本程式碼採用的解法是，根據獲利率的正負加減一值極小的小數如0.0001，使其在不影響大部分測資獲利率數值的情況下，能在獲利率是後面為9循環的小數時強制進位，以確保四捨五入的正確性。
:::

**程式碼**

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++) {
        int m, p;
        scanf("%d %d", &m, &p);
        
        float x=(((float)p/(float)m-1)*100);
        if(x>=0)
            x+=+0.00001;
        else
            x-=+0.00001;        
        
        char c='%';
        printf("%.2f%c ", x, c);
        
        if(x>=10.00 || x<=-7.00)
            printf("dispose\n");
        else
            printf("keep\n");
    }
    return 0;
}

## [a693. 吞食天地](https://zerojudge.tw/ShowProblem?problemid=a693)
**連結題目：[a694. 吞食天地二](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a694-%E5%90%9E%E9%A3%9F%E5%A4%A9%E5%9C%B0%E4%BA%8C)**

**解題思路**
本題會有多組測資，我們必須找出輸入的數列中，第l項到第r項之間的和。

可能有些人會想用迴圈從第i項到第r項逐項累加，但從題目的輸入說明可知，本題測資最多達100000筆，每筆測資的食物的數量最多達100000個，如果用迴圈運算的話很可能超時。因此，在這裡要介紹一個新的概念:[前綴和 (preflix sum)](https://cp.wiwiho.me/prefix-sum/)。

前綴和是指數列在此項以前(含)所有元素的總和，比如說前綴和n就是數列從第一項加到第n項的和。由此可知，數列第l項到第r項之間的和，其實就是前綴和r與前綴和l-1的差。由於前綴和的計算可以在讀取數列時候一併完成，在讀取到l和r的數值後只需把兩者的前綴和相減，運算複雜度及所需時間比用迴圈逐項累加要少很多，就可以順利避免超時的問題了!

:::info
**注意事項**
在上面的解題思路有提到，使用迴圈累加的運算時間較前綴和相減長。雖然這是很直觀的想法，但背後其實牽涉到[時間複雜度](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)的概念。考量到對於進階的題目，或甚至是程式競賽來說，縮短程式的運行時間是很重要的，建議程式基礎較強的人可以參考看看。
:::

**程式碼**

#include <stdio.h>
int main() {
    int n, m;
    while(scanf("%d%d", &n, &m)!=EOF) {
        int food[n], sum[n];
        /*本題若直接用迴圈計算兩數間的的飽足感數，會因數字間距過大而超時，因此需用前綴和的概念解題。
    　     在讀取陣列時先得出前綴和的陣列，將兩前綴和相減即得算兩排間的飽足感數*/
        for(int i=0;i<n;i++) {
            scanf("%d", &food[i]);
            sum[i+1]=sum[i]+food[i];
        }
        for(int i=0;i<m;i++) {
            int l, r;
            scanf("%d%d", &l ,&r);
            printf("%d\n", sum[r]-sum[l-1]);
        }
    }
    return 0;
}

## [a694. 吞食天地二](https://zerojudge.tw/ShowProblem?problemid=a694)
**連結題目：[a693. 吞食天地](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a693-%E5%90%9E%E9%A3%9F%E5%A4%A9%E5%9C%B0)**

**解題思路**
本題會有多組測資，我們必須找出輸入的數列中，第(x1,y1)項到第(x2,y2)項之間的和。

可能有些人會想用雙層迴圈從第(x1,y1)項到第(x2,y2)項逐項累加，但從題目的輸入說明可知，本題測資最多達100000筆，每筆測資的食物的數量最多達500x500個，如果用雙層迴圈運算的話很可能超時。因此，在這裡要介紹一個新的概念:[前綴和 (preflix sum)](https://cp.wiwiho.me/prefix-sum/)。

前綴和是指數列在此項以前(含)所有元素的總和，比如說前綴和n就是數列從第一項加到第n項的和。由此可知，數列第y1項到第y2項之間的和，其實就是前綴和y2與前綴和y1-1的差。據此，我們可以將二維陣列分行做前綴和，運算複雜度及所需時間比用迴圈逐項累加要少很多，就可以順利避免超時的問題了!

:::info
**注意事項**
在上面的解題思路有提到，使用迴圈累加的運算時間較前綴和相減長。雖然這是很直觀的想法，但背後其實牽涉到[時間複雜度](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)的概念。考量到對於進階的題目，或甚至是程式競賽來說，縮短程式的運行時間是很重要的，建議程式基礎較強的人可以參考看看。
:::

**程式碼**

#include <stdio.h>
int main() {
    int n, m;
    while(scanf("%d%d", &n, &m)!=EOF) {
        int food[n][n], sum[n+1][n+1];
        for(int row=0;row<n+1;row++)
            for(int column=0;column<n+1;column++)
                sum[row][column]=0;

        for(int row=0;row<n;row++)
            for(int column=0;column<n;column++) {
                scanf("%d", &food[row][column]);
                sum[row+1][column+1]=sum[row+1][column]+food[row][column];
            }

        for(int i=0;i<m;i++) {
            int x1, y1, x2, y2, output=0;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            for(int row=x1;row<=x2;row++)
                output+=sum[row][y2]-sum[row][y1-1];
            printf("%d\n", output);
        }
    }
    return 0;
}

## [a738. 最大公约数](https://zerojudge.tw/ShowProblem?problemid=a738)
除了有多筆測資直到EOF結束以外，本題的概念與[a024](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a024%E6%9C%80%E5%A4%A7%E5%85%AC%E5%9B%A0%E6%95%B8GCD)完全相同，可以點擊藍色字體的連結參考!

**程式碼**

#include <stdio.h>
int main() {
    int a, b, big, small;
    while(scanf("%d%d", &a, &b)!=EOF) {

        if(a>b) {
            big=a;
            small=b;
        }
        else {
            big=b;
            small=a;
        }

        while(small!=0) {
            int temp=big;
            big=small;
            small=temp%small;
        }
        printf("%d\n", big);
    }
    return 0;
}

## [a740. 质因数之和](https://zerojudge.tw/ShowProblem?problemid=a740)
**連結題目：[a010. 因數分解](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a010-%E5%9B%A0%E6%95%B8%E5%88%86%E8%A7%A3)**

**解題思路**
本題希望我們能得出輸入數字的質因數之和，因此我們必須對輸入數字做質因數分解。具體的做法是從最小的質數開始檢查，當遇到該數的因數時，就把該數除以此質數得到商數，然後再重複上述動作，直到確定商數已經不能再被此質數整除為止。重複上述動作直到商數剩下一為止，即完成因數分解。

:::info
**注意事項**
注意本題要求的不是「因數和」，而是「質因數和」，因此1不能計入!
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    long long x;
    while(scanf("%lld", &x)!=EOF) {
        long long sum=0, r;
        for(int i=2;i<=sqrt(x);i++) {
            r=x%i;
            while(r==0) {
                sum+=i;
                x/=i;
                r=x%i;
            }
        }
        if(x!=1) /*若x不等於1，代表x本身為質數*/
            sum+=x;
        printf("%lld\n", sum);
    }
    return 0;
}

## [a746. 画蛇添足](https://zerojudge.tw/ShowProblem?problemid=a746)
**解題思路**本題希望我們可以將二維陣列的外框分別用-和|表示，內部的點若特別被提到則用*表示並連線，否則輸出空白。

首先，我們可以宣告一大小為[N+2][N+2]的二維陣列，並將column=0和column=N+1的點設值為|，將row=0和row=N+1的點設值為-，而內部的點則設為空白。

再來，既然題目保證前一個點和後一個點所確定的線段一定平行於圍欄的一邊，代表前後兩點一定擁有相同的x座標或y座標。因此，我們可以根據前後兩點相同的是x座標還y座標將情況分為鉛直線和水平線兩類，將兩點所連成的線段上的點都設為*。

最後，在將二為陣列的點設值完成後，再輸出二維陣列即可。

:::info
**注意事項**
在二維陣列的表示法中，前面的參數代表行數(y)，後面代表列數(x)。而在數學的坐標系中，前面的參數代表的是x，後面代表y。兩者恰好順序相反，在寫程式的時候別搞錯了!
:::

**程式碼**

#include <stdio.h>
int main () {
    int n, m;
    while(scanf("%d%d", &n, &m)!=EOF) {
        char matrix[n+2][n+2]; /*建立包含外框的初始二維陣列*/
        for(int row=0;row<n+2;row++)
            for(int column=0;column<n+2;column++)
                matrix[column][row]=' ';
        for(int i=0;i<n+2;i++) {
            matrix[0][i]='|';
            matrix[n+1][i]='|';
        }
        for(int i=0;i<n+2;i++) {
            matrix[i][0]='-';
            matrix[i][n+1]='-';
        }

        int x[m], y[m]; /*讀取輸入的點，兩點連成一線*/
        for(int i=0;i<m;i++)
            scanf("%d%d", &x[i], &y[i]);
        for(int i=0;i<m-1;i++) {
            if(x[i]==x[i+1]) {
                int start=(y[i]<y[i+1]) ? y[i] : y[i+1];
                int end=(y[i]<y[i+1]) ? y[i+1] : y[i];
                for(int j=start;j<=end;j++)
                    matrix[j][x[i]]='*';
            }
            else if(y[i]==y[i+1]) {
                int start=(x[i]<x[i+1]) ? x[i] : x[i+1];
                int end=(x[i]<x[i+1]) ? x[i+1] : x[i];
                for(int j=start;j<=end;j++)
                    matrix[y[i]][j]='*';
            }
        }

        for(int row=0;row<n+2;row++) { /*輸出二維陣列*/
            for(int column=0;column<n+2;column++)
                printf("%c", matrix[column][row]);
            printf("\n");
        }
    }
    return 0;
}

## [a799. 正值國](https://zerojudge.tw/ShowProblem?problemid=a799)
**解題思路**
將題目輸入的測資取絕對值後輸出。

:::info
**注意事項**
本程式碼使用了abs()函式表示絕對值寫法。由於abs()函式並非標準函式庫裡的函式，使用前必須引用<math.h>函式庫。
:::

**程式碼**

#include <stdio.h>
#include <math.h>
int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", abs(N));
    return 0;
}

## [a915. 二维点排序](https://zerojudge.tw/ShowProblem?problemid=a915)
**連結題目：[a225. 明明愛排列](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a225-%E6%98%8E%E6%98%8E%E6%84%9B%E6%8E%92%E5%88%97)**

**解題思路**
根據題意，我們必須將輸入的點座標按x座標的大小，由小到大排列。而若是x座標的大小相同，再按y座標的大小由大到小排列。

[為數字排序的方法](https://totoroliu.medium.com/%E6%8E%92%E5%BA%8F%E6%BC%94%E7%AE%97%E6%B3%95-sorting-algorithm-dfd8af673f3a)有很多種，而本題採用[氣泡排序法](https://medium.com/@oturngo/study-note-01-%E6%B0%A3%E6%B3%A1%E6%8E%92%E5%BA%8F%E6%B3%95-bubble-sort-ee534b6f91eb)，具體的作法是從第一個元素開始往下檢查，如果兩者的相對順序錯誤，就將兩者的位置對調，接著重新檢查，直到最後一個元素的位置也被確認正確無誤為止。

以由小到大排列為例，我們會從第二個數字開始檢查，若它比前一個數字，也就是第一個數字還大的話，代表檢查到目前為止，它在數列中的位置是正確的，我們就不會移動他的位置，繼續檢查下去 ; 反之，如果它比後一個數字還小，代表它在數列中的位置不符合題目希望由小到大排序的要求，因此我們會將它與前一個數字的位置對調，然後重新檢查。

:::info
**注意事項**
根據題意，測資檔會包含多組測資，因此需使用[EOF寫法](
https://www.796t.com/content/1544817994.html)判斷程式執行的條件。
:::

**程式碼**

#include <stdio.h>
int main() {
    int n;
    while(scanf("%d", &n)!=EOF) {
        int x[n], y[n];
        for(int i=0;i<n;i++)
            scanf("%d %d", &x[i], &y[i]);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                if(x[i]>x[j] || (x[i]==x[j] && y[i]>y[j])) {
                    int temp=x[i];
                    x[i]=x[j];
                    x[j]=temp;

                    temp=y[i];
                    y[i]=y[j];
                    y[j]=temp;
                }
        for(int i=0;i<n;i++)
            printf("%d %d\n", x[i], y[i]);
    }
    return 0;
}

## [a981. 求和問題](https://zerojudge.tw/ShowProblem?problemid=a981)
**連結題目：[a524. 手機之謎](https://hackmd.io/DwmkclCaTUOO48NYFW8AHw?view#a524-%E6%89%8B%E6%A9%9F%E4%B9%8B%E8%AC%8E)**

**解題思路**
根據題意，本題希望我們列舉出總和恰好為m的所有可能。因為我們必須排除已經輸出的情況，列舉出所有的可能性，因此我們採用遞迴來解決這題。具體的想法是從第一項數字開始，決定是否要選取該數字，直到所有數字都跑完為止，若總和為m則輸出組合後返回，若否則直接返回。

:::info
**注意事項**
從遞迴會運算每種可能性的特質可知其所需的運算時間較久，因此我們常會進行「剪枝」，也就是終止討論確定不可能的情況，直接返回並進入下一次討論。以本程式碼來說，由於題目希望我們輸出總合為m的情況，因此若是還沒討論完總和就已經大於m，就可以直接返回並進行下一次遞迴。
:::

**程式碼**

#include <stdio.h>
int n, m, arr[31], step[31]={}, check[31]={}, no_solution=1;
void dfs(int now, int sum) {
    if(now==n) {
        if(sum==m) {
            int test=0;
            for(int i=0;i<n;i++) {
                if(check[i]!=0) {
                    if(test==1)
                        printf(" ");
                    printf("%d", arr[i]);
                    test=1;
                }
            }
            printf("\n");
            no_solution=0;
        }
        return;
    }
    if(sum>m) /*若sum已經大於m，為不合法的可能，可以直接返回*/
        return;
    check[now]=1; /*選取該數字*/
    dfs(now+1, sum+arr[now]); /*將sum加上該數字後進入下一項的討論*/
    check[now]=0; /*不選該數字*/
    dfs(now+1, sum); /*直接進入下一項的討論*/
}
int main() {
    while(scanf("%d%d", &n, &m)!=EOF) {
        int sum=0;
        for(int i=0;i<n;i++) {
            scanf("%d", &arr[i]);
            sum+=arr[i];
        }
        if(sum<m) {
            printf("-1\n");
            continue;
        }
        for(int i=0;i<n;i++) {
            for(int j=i+1;j<n;j++) {
                if(arr[i]>arr[j]) {
                    int temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                }
            }
        }
        dfs(0, 0);
        if(no_solution==1)
            printf("-1\n");
        no_solution=1;
    }
    return 0;
}