## Promise
### 解題思路
這是一題非常引人深思的題目，綜合了助教們當助教以來的所有心血所出的題目。它看似平平無奇卻又富含深度，充分考驗著學生對於程式設計課的理解。只要你多花一點時間看看這題你就會發現，你花了一點時間。
好的，~~以上幹話結束。~~
注意測資範圍，小心被卡long long。
### AC code

#include<stdio.h>
#include<stdlib.h> 

int main(){
    long long n;
    scanf("%lld",&n);
    printf("%lld\n",n*50);
    return 0;
}

## Sneaker
### 解題思路
這題其實就只是費式數列的小改版，只需要保證時間複雜度不是$O(2^n)$，就不會被卡掉。最簡單的解法是用loop去解，想要加速也可以用矩陣快速冪去解。
### AC code
#### Loop $O(n)$解

#include<stdio.h>
#include<stdlib.h>
int main(){
    int t;
    int a,b,c,d,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&n);
        long long *nums = (long long *)calloc(n,sizeof(long long));
        nums[0] = a;
        nums[1] = b;
        for(int i = 2 ; i < n ; i++){
            nums[i] = c*nums[i-1]+d*nums[i-2];
            nums[i]%=1000000007;
        }
        printf("%lld\n",nums[n-1]);
    }
        
    return 0;
}

#### 矩陣快速冪 $O(log n)$解

#include<stdio.h>
#include<stdlib.h>
#include <time.h>

#define MAX 1000000007

long long int** matrix_mult(long long int **A,long long int **B){
    long long int **sum = (long long int**)malloc(2*sizeof(long long int*));
    for(int i = 0 ; i < 2 ;i++){
        sum[i] = (long long int*)calloc(2,sizeof(long long int));
    }
    for(int i = 0 ; i < 2 ; i++){
        for(int j = 0 ; j < 2 ; j++){
            for(int k = 0 ; k < 2 ; k++){
                sum[i][j] += (A[i][k]*B[k][j])%MAX;
                sum[i][j]%=MAX;
            }
        }
    }
    return sum;
}

long long int** fast_compute(long long int **A,int n){//n是次方
    if(n == 1)  return A;
    if(n%2 == 0){
        return fast_compute(matrix_mult(A,A),n/2);
    }
    else{
        return matrix_mult(A,fast_compute(matrix_mult(A,A),(n-1)/2));
    }
}

int main(){
    long long int t;
    scanf("%lld",&t);
    long long int **start_matrix = (long long int**)malloc(2*sizeof(long long int*));
    for(int i = 0 ; i < 2 ;i++){
        start_matrix[i] = (long long int*)calloc(2,sizeof(long long int));
    }
    long long int **mult_matrix = (long long int**)malloc(2*sizeof(long long int*));
    for(int i = 0 ; i < 2 ; i++){
        mult_matrix[i] = (long long int*)calloc(2,sizeof(long long int));
    }
    while(t--){
        long long int a,b,c,d,n;
        scanf("%lld %lld %lld %lld %lld",&a,&b,&c,&d,&n);
        start_matrix[0][0] = a*d+b*c;//f(3)
        start_matrix[0][1] = b;
        start_matrix[1][0] = b;
        start_matrix[1][1] = a;
        mult_matrix[0][0] = c;
        mult_matrix[0][1] = d;
        mult_matrix[1][0] = 1;
        mult_matrix[1][1] = 0;
        if(n == 1)  printf("%lld\n",a);
        else if(n == 2) printf("%lld\n",b);
        else if(n == 3) printf("%lld\n",start_matrix[0][0]);
        else{
            long long int **B = fast_compute(mult_matrix,n-3);
            long long int **ans = matrix_mult(B,start_matrix);
            printf("%lld\n",ans[0][0]%MAX);
        }
        
    }
    return 0;
}

## XYZ
### 相關演算法
* Stack

### 解題思路
這題使用到了 Stack 的概念，配和指標的移動，對輸入的算試做處理。先從字串的第一個字元開始(*expr)，如果是 '(' ，就把之後的兩個數字利用移動指標的方式，型成一個新指標並放入堆疊，最後在將指標移動到 ')' 之後的運算符號上，當下次迴圈執行時，如果指到的是 '*' 則將堆疊最上面的向量和下一個向量做內積，由於是拿出一個向量再放入一個向量，所以 vtop 不變，如果是 '+' 則直接跳過，最後指標指到字串結尾時 (＊expr == '\0') 迴圈結束，最後將所有在堆疊中的向量相加，便可以達到先內積後加減的效果。

### AC code

#include <stdio.h>
#include <stdlib.h>

// 定義向量結構
typedef struct Vec {
    int x;
    int y;
} Vec;

int main() {
    char *expr = (char *)calloc(10000, sizeof(char));
    scanf("%s", expr);
    
    // 定義堆疊
    Vec *vstack = (Vec *)calloc(2000, sizeof(Vec));
    int vtop = 0;

    while (*expr != '\0') {
        switch (*expr) {
            // 將下個向量加入堆疊並將指標向後移動
            case '(':
                expr++;
                Vec v;
                v.x = *expr - '0';
                expr += 2;
                v.y = *expr - '0';
                expr++;
                vstack[vtop++] = v;
                break;
            // 將堆疊中最上面的向量和新的向量做內積
            case '*':
                expr += 2;
                vstack[vtop - 1].x *= *expr - '0';
                expr += 2;
                vstack[vtop - 1].y *= *expr - '0';
                expr++;
                break;
            // 加號，先跳過
            default:
                expr++;
                break;
        }
    }
    
    // 將堆疊中的所有向量相加
    while (vtop > 1) {
        vstack[vtop - 2].x += vstack[vtop - 1].x;
        vstack[vtop - 2].y += vstack[vtop - 1].y;
        vtop--;
    }

    printf("%d %d\n", vstack[0].x, vstack[0].y);
    
    // 釋放記憶體
    free(vstack);
    return 0;
}

## Final_Battle
### 相關演算法
* sorting
* greedy
### 解題思路
這題的關鍵是找到 "第一個違反最佳字母擺放順序" 的位置

ex: eacbd 中，第二個位置的最佳字母應為 "d"，但 "d" 卻跑到第五個位置去了

於是我們想辦法把 "d" 拉到正確的位置去就好了 (透過反轉)，剩餘的實作細節請參考程式碼

給定字串: eacbd
最佳答案: edcba

### AC code

#include <stdio.h>
typedef long long int llt;

int cmp(const void* a, const void* b)
{
    return *(char*)a<*(char*)b;
}

llt Size(char s[30])
{
    llt i=0;
    while(1)
    {
        if(s[i]=='\0') return i;

        i++;
    }
}

int main()
{
    llt t;
    scanf("%lld\n", &t);
    for(llt i=0;i<t;i++)
    {
        char s[30];
        scanf("%s", s);

        llt size_s=Size(s);

        char s_sorted[30];
        for(llt j=0;j<size_s;j++)
        {
            s_sorted[j]=s[j];
        }

        llt a[26]; // 存字母在原字串中出現的位置 (0-indexed)
        for(llt j=0;j<26;j++)
        {
            a[j]=-1;
        }

        llt j=0;
        while(s[j]!='\0')
        {
            a[s[j]-'a']=j;
            j++;
        }

        qsort((void*)s_sorted, size_s, sizeof(s_sorted[0]), cmp);

        llt left=0, right=-1;
        while(1)
        {
            if(left==size_s) break;

            if(s[left]==s_sorted[left])
            {
                left++;
                continue;
            }
            else
            {
                //printf("%lld %lld\n", left, a[s_sorted[left]-'a']);
                right=a[s_sorted[left]-'a'];
                break;
            }
        }

        if(right!=-1)
        {
            char s_temp[30];
            for(llt j=0;j<size_s;j++)
            {
                s_temp[j]=s[j];
            }

            llt r=right;
            for(llt j=left;j<=right;j++)
            {
                s[j]=s_temp[r];
                r--;
            }
        }

        for(llt j=0;j<size_s;j++)
        {
            printf("%c", s[j]);
        }
        printf("\n");
    }
}

## Death_Zone
### 相關演算法
* 二分搜

### 解題思路
這題是一題藏的很深的 binary search 的題目，根據題目給定的奇怪公式 i\*j + max(i, j)\*max(i, j)，可以觀察到當 i 變大、j 不變的情況下，計算出來的命定值保證變大
如此一來便可以針對每個 column 做一次二分搜，快速找出有幾個元素小於芙莉連所選座標的命定值了

時間複雜度: O(nlogn)


### AC code

# include <stdio.h>
typedef long long int llt;

llt CalculateMax(llt a, llt b)
{
    if(a>b) return a;
    else return b;
}

int main()
{
    llt n, x, y;
    scanf("%lld %lld %lld", &n, &x, &y);

    llt target=x*y+CalculateMax(x, y)*CalculateMax(x, y);

    llt ans=0;
    for(llt j=1;j<=n;j++)
    {
        llt left=0, right=n, mid;
        llt Max=0;
        while(1)
        {
            mid=(left+right)/2;

            if(mid*j+CalculateMax(mid, j)*CalculateMax(mid, j)<=target)
            {
                Max=CalculateMax(Max, mid);
            }

            if(left==right) break;
            if(mid*j+CalculateMax(mid, j)*CalculateMax(mid, j)<=target) left=mid+1;
            else right=mid;
        }
        ans+=Max;
    }
    printf("%lld\n", ans);

    return 0;
}

## Chest_Hunter
### 相關演算法
* BFS

### 解題思路
這題使用到了 BFS 的技巧 (counter 初始化成 0)
1. 先從起點把所有可以走到的位置走完
2. 炸掉跟 "目前可以走到的位置" 相鄰的所有牆壁，且counter ++
3. 反覆執行第 1、2 步，直到走到其中一個寶箱怪所在位置，此時 counter 即為答案

這邊需要注意的是，第二步炸掉的是一整層牆壁，而非一格牆壁，這是因為炸掉牆壁的過程是同步進行的 (就像 BFS 找最短路徑時，也是同時像各方向擴散一格一樣)

時間複雜度: O(n*m)

ans=0
.#####V#
.#######
.####.#V
.###..##
.###..#.

ans=0
O#####V#
O#######
O####.#V
O###..##
O###..#.

ans=1
O.####V#
O.######
O.###.#V
O.##..##
O.##..#.

ans=1
OO####V#
OO######
OO###.#V
OO##..##
OO##..#.

ans=2
OO.###V#
OO.#####
OO.##.#V
OO.#..##
OO.#..#.

ans=2
OOO###V#
OOO#####
OOO##.#V
OOO#..##
OOO#..#.

ans=3
OOO.##V#
OOO.####
OOO.#.#V
OOO...##
OOO...#.

ans=3
OOOO##V#
OOOO####
OOOO#O#V
OOOOOO##
OOOOOO#.

ans=4
OOOO.#V#
OOOO..##
OOOO.O.V
OOOOOO.#
OOOOOO..

### AC code

# include <stdio.h>

// 定義座標結構
typedef struct {
    int x;
    int y;
} Coordinate;

// 定義循環隊列
#define MAX_SIZE 100001

typedef struct {
    Coordinate data[MAX_SIZE];
    int front, rear;
    int size; // 新增隊列大小的變數
} CircularQueue;

// 初始化循環隊列
void initQueue(CircularQueue *queue) {
    queue->front = -1;
    queue->rear = -1;
    queue->size = 0; // 初始化隊列大小為 0
}

// 檢查循環隊列是否為空
int isEmpty(CircularQueue *queue) {
    return (queue->front == -1 && queue->rear == -1);
}

// 檢查循環隊列是否已滿
int isFull(CircularQueue *queue) {
    return ((queue->rear + 1) % MAX_SIZE == queue->front);
}

// 將元素推入循環隊列
void push(CircularQueue *queue, Coordinate coord) {
    if (isFull(queue)) {
        printf("Queue is full. Cannot push element.\n");
        return;
    } else if (isEmpty(queue)) {
        queue->front = 0;
        queue->rear = 0;
    } else {
        queue->rear = (queue->rear + 1) % MAX_SIZE;
    }
    queue->data[queue->rear] = coord;
    queue->size++; // 推入元素後增加隊列大小
}

// 將元素彈出循環隊列
Coordinate pop(CircularQueue *queue) {
    Coordinate poppedCoord;
    if (isEmpty(queue)) {
        printf("Queue is empty. Cannot pop element.\n");
        poppedCoord.x = -1; // 表示出錯
        poppedCoord.y = -1;
        return poppedCoord;
    } else if (queue->front == queue->rear) {
        poppedCoord = queue->data[queue->front];
        queue->front = -1;
        queue->rear = -1;
    } else {
        poppedCoord = queue->data[queue->front];
        queue->front = (queue->front + 1) % MAX_SIZE;
    }
    queue->size--; // 彈出元素後減少隊列大小
    return poppedCoord;
}

// 查看循環隊列的頂部元素
Coordinate top(CircularQueue *queue) {
    Coordinate topCoord;
    if (isEmpty(queue)) {
        printf("Queue is empty. Cannot get top element.\n");
        topCoord.x = -1; // 表示出錯
        topCoord.y = -1;
        return topCoord;
    } else {
        return queue->data[queue->front];
    }
}

// 取得隊列大小
int getSize(CircularQueue *queue) {
    return queue->size;
}

int main()
{
    int n, m;
    scanf("%d %d\n", &n, &m);

    char Map[n][m];
    int visited[n][m];
    int dx[4]={1, -1, 0, 0};
    int dy[4]={0, 0, 1, -1};

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%c", &Map[i][j]);
            visited[i][j]=0;
        }
        if(i!=n-1) scanf("\n");
    }

    CircularQueue queue;
    initQueue(&queue);

    Coordinate start={0, 0};
    push(&queue, start);
    visited[0][0]=1;

    int counter=0;
    while(!isEmpty(&queue))
    {
        CircularQueue temp_queue; // 存那些下一輪會被炸掉的牆壁位置
        initQueue(&temp_queue);
        while(!isEmpty(&queue))
        {
            Coordinate poppedCoord = pop(&queue);

            if(Map[poppedCoord.x][poppedCoord.y]=='V')
            {
                printf("%d\n", counter);
                return 0;
            }

            for(int i=0;i<4;i++)
            {
                int x=poppedCoord.x+dx[i];
                int y=poppedCoord.y+dy[i];

                if(x<n && x>=0 && y<m && y>=0 && visited[x][y]==0)
                {
                    if(Map[x][y]!='#')
                    {
                        Coordinate coord = {x, y};
                        push(&queue, coord);
                        visited[x][y]=1;
                    }
                    else
                    {
                        Coordinate coord = {x, y};
                        push(&temp_queue, coord);
                    }
                }
            }
        }

        while(!isEmpty(&temp_queue))
        {
            Coordinate poppedCoord = pop(&temp_queue);
            push(&queue, poppedCoord);
            visited[poppedCoord.x][poppedCoord.y]=1;
        }

        counter++;
    }

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

## Puzzle
### 相關演算法
* DFS

### 解題思路
這一題是類似解數獨的題目，用DFS的方式，每一次對於未解出的格子選一個可能的解，再往下一格試試
如果錯誤了就會退回上一格繼續嘗試下一個可能

### AC code

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool check(char **map, int x, int y, char symbol){
    for(int i = 0; i < 9; i++){
        if(map[x][i] == symbol || map[i][y] == symbol){
            return false;
        }
    }

    int start_x = x - x % 3;
    int start_y = y - y % 3;
    for(int i = start_x; i < start_x + 3; i++){
        for(int j = start_y; j < start_y + 3; j++){
            if(map[i][j] == symbol){
                return false;
            }
        }
    }

    return true;
}

bool solve(char *label, char **map, int x, int y){
    if(y == 9){
        y = 0;
        x++;
        if(x == 9){
            return true;
        }
    }

    if(map[x][y] != '.'){
        return solve(label, map, x, y+1);
    }

    for(int i = 0; i < 9; i++){
        if(check(map, x, y, label[i])){
            map[x][y] = label[i];
            if(solve(label, map, x, y+1)){
                return true;
            }
            map[x][y] = '.';
        }
    }
    return false;
}

int main(){
    char *label = malloc(10 * sizeof(char));
    char **map = malloc(9 * sizeof(char *));
    for(int i = 0; i < 9; i++) map[i] = malloc(10 * sizeof(char));

    scanf("%s", label);
    for(int i = 0; i < 9; i++){
        scanf("%s", map[i]);
    }

    solve(label, map, 0, 0);
    for(int i = 0; i < 9; i++){
        printf("%s\n", map[i]);
    }
    return 0;
}

## Holiday
### 相關演算法
* 暴力搜尋法

### 解題思路
簡單版: 這題由於 n 非常小，只要能暴力找出每一組解，便可以通過這題

以 n = 3 舉例，六個數字依序代表:
第一個人收到的第一份祝福來自?
第一個人收到的第二份祝福來自?
第二個人收到的第一份祝福來自?
第二個人收到的第二份祝福來自?
第三個人收到的第一份祝福來自?
第三個人收到的第二份祝福來自?

可以觀察出一些規則
1. 答案是 1~n 各出現兩次的 permutation (祝福隨便分配給所有人)
2. 但同一個人分到的兩份祝福，要按照遞增順序排序 (例如 12 12 33、13 12 23 等等)，這是因為"某個人先收到第 1 個人的祝福再收到第 2 個人的祝福"、以及"某個人先收到第 2 個人的祝福再收到第 1 個人的祝福"，這兩種情況是完全相同的，故只需要算一次就好

### AC code

#include <stdio.h>

typedef long long int llt;

llt counter=0;
llt n;
llt a[8*2];
llt used[8*2];

void f(llt now_index)
{
    if(now_index>=2*n)
    {
        for(llt i=0;i<2*n;i+=2)
        {
            if(a[i+1]<a[i]) return;
        }
        counter++;
        for(llt i=0;i<2*n;i++)
        {
            printf("%d ", a[i]);
        }
        printf("\n");

        return;
    }

    for(int i=0;i<n;i++)
    {
        if(used[i]<2)
        {
            used[i]++;
            a[now_index]=i+1;
            f(now_index+1);
            used[i]--;
        }
    }
}

void Solve()
{
        scanf("%lld", &n);
        //pirntf("第一個人收到的第一份祝福來自? 第一個人收到的第二份祝福來自? 第二個人收到的第一份祝福來自? 第二個人收到的第二份祝福來自? 第三個人收到的第一份祝福來自? 第三個人收到的第二份祝福來自?");
        counter=0;
        for(llt i=0;i<n*2;i++)
        {
            used[i]=0;
        }

        f(0);

        printf("%lld\n", counter);
}
int main()
{
    llt t=1;
    for(llt i=1;i<=t;i++)
    {
        Solve();
    }

    return 0;
}

## Holiday_extra
### 相關演算法
* 動態規劃

### 解題思路
我們可以將每個人的情況分成 3種
A. 還沒被分配到
B. 被分配到一個
C. 都被分配完了

每次分配兩個箭頭，就會有四種不同的分法
1. 兩個箭頭都給同一個人 (當然這種人肯定是A情況，給完後變成C)
2. 兩個箭頭給不同人(給兩個A，給完後這兩個變成B)
3. 兩個箭頭給不同人(給一個A 一個B，給完後A變成B，B變成C)
4. 兩個箭頭給不同人(給兩個B，這兩個人都變成C)

可以先把答案定義成F(A的數量,B的數量)
F(A,B)=
第一種分法 * F(A-1,B)
\+ 第二種分法 * F(A-2, B+2)
\+ 第三種分法 * F(A-1, B)
\+ 第四種分法 * F(A, B-2)

因此，若是題目輸入n，就代表一開始有n個A情況的人需要被分配
也就是F(n, 0)

只要把上述的算式寫出來，記得加一些判斷式
不要讓A 或 B 變成負數 譬如 F(A,B-2) 就肯定B要>=2
同時也要記得加上算完的中止情況，否則會無止盡的算完下去
也就是 F(1,0)=F(0,2)=1
F(1,0)代表剩一個人都還沒分到，那兩個箭頭都給他，只有這種情況
F(0,2)代表剩兩個人都差一個箭頭，因此把箭頭都各自分給他們，也只有這種情況

### AC code

#include <stdio.h>
#include <stdlib.h>

#define int long long

int mod = 1e9 + 7;

int **arr = NULL;

int f(int d, int s){
    if(d < 0 || s < 0){
        return 0;
    }

    if(arr[d][s] != 0){
        return arr[d][s];
    }

    if(d >= 1 && arr[d-1][s] == 0){
        arr[d-1][s] = f(d-1, s);
    }
    if(s >= 2 && arr[d][s-2] == 0){
        arr[d][s-2] = f(d, s-2);
    }
    if(d >= 2 && arr[d-2][s+2] == 0){
        arr[d-2][s+2] = f(d-2, s+2);
    }

    int ans = 0;
    if(d >= 1) ans += (d * (s+1) * arr[d-1][s] % mod);
    if(s >= 2) ans += ((s * (s-1) / 2) * arr[d][s-2] % mod);
    if(d >= 2) ans += ((d * (d-1) / 2) * arr[d-2][s+2] % mod);
    arr[d][s] = ans % mod;
    return ans % mod;
}

int main(){
    int n;
    scanf("%lld", &n);
    arr = (int **)malloc((n+1) * sizeof(int*));
    for(int i = 0; i <= n; i++){
        arr[i] = (int *)calloc(2*n+1, sizeof(int));
    }
    arr[1][0] = 1;
    arr[0][2] = 1;
    f(n, 0);
    printf("%lld\n", arr[n][0]);
}