# week 3
## The_Burden_Of_Love
### 解題思路
利用前綴和紀錄資訊，，O(n) 跑一次即可以便之後能快速以 O(1) 的時間查詢某個區間內的數字總和
接著利用二分搜 "猜" 哪個答案是最好的
共有 q 個 query，每輪花費 O(logn) 的時間，故總時間複雜度為 O(q*logn)
### AC 程式

#include <stdio.h>

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

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

    int prefix[n+1];
    prefix[0]=0;
    for(int i=1;i<=n;i++)
    {
        prefix[i]=prefix[i-1]+a[i-1];
    }

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

        int left=t, right=n-1, mid;
        int ans=0;
        while(1)
        {
            mid=(left+right)/2;

            if(m>=prefix[mid+1]-prefix[t])
            {
                if(mid-t+1>ans) ans=mid-t+1;
            }
            if(left==right) break;
            if(m>=prefix[mid+1]-prefix[t]) left=mid+1;
            else right=mid;
        }

        printf("%d\n", ans);
    }

    return 0;
}

## The_Dintance_Of_Love
### 解題思路
使用遞迴搭配 for 迴圈，暴力列舉出所有可能的 permutation 即可
時間複雜度 O(N!)
### AC 程式

#include <stdio.h>

int counter=0;
int n, k;
void f(int* a,int* used, int now_index)
{
    if(now_index>=n)
    {
        int reverse_count=0;
        for(int i=0;i<n-1;i++)
        {
            if(a[i]>a[i+1]) reverse_count++;
        }

        if(reverse_count<=k) counter++;

        return;
    }

    for(int i=0;i<n;i++)
    {
        if(used[i]==0)
        {
            used[i]=1;
            a[now_index]=i+1;
            f(a, used, now_index+1);
            used[i]=0;
        }
    }
}
int main()
{
    scanf("%d %d", &n, &k);

    int used[n];
    int a[n];
    for(int i=0;i<n;i++)
    {
        used[i]=0;
    }

    f(a, used, 0);

    printf("%d\n", counter);

    return 0;
}

## The_Trial
### 解題思路
利用DFS遞迴進行地圖遍歷，確認是否可以到達終點（熒的位置）。
### AC 程式

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

int direct[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
int check = 0;

bool is_road(int **map,int x,int y,int length,int width){
    if( x == length || x < 0 || y < 0 || y == width ||map[y][x] == 1)   return false;
    return true;
}

void dfs(int **map,int length,int width,int x_src,int y_src,int x_dst,int y_dst){
    if(x_src == x_dst && y_src == y_dst){
        check = 1;
    }
    map[y_src][x_src] = 1;
    for(int i = 0 ; i < 4 ; i++){
        int new_x = x_src + direct[i][1];
        int new_y = y_src + direct[i][0];
        if(is_road(map,new_x,new_y,length,width)){
            dfs(map,length,width,new_x,new_y,x_dst,y_dst);
        }
    }
}

int main(){
    int length, width, x_src, y_src, x_dst, y_dst;
    scanf("%d %d",&width,&length);
    scanf("%d %d %d %d", &y_src, &x_src, &y_dst, &x_dst);
    int **map = (int**)malloc(width * sizeof(int*));
    for(int i = 0 ; i < width ; i++){
        map[i] = (int*)malloc(length*sizeof(int));
    }
    for(int i = 0 ; i < width ; i++){
        for(int j = 0 ; j < length ; j++){
            scanf("%d",&map[i][j]);
        }
    }
    dfs(map,length,width,x_src,y_src,x_dst,y_dst);
    if(check == 1){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}