---
# System prepended metadata

title: Yang-109

---

{%hackmd BJrTq20hE %}
本篇均為短解無注釋，在這裡你可以學到把code寫短寫美跟一些小技巧
通常AC了才來這裡看呦。有問題、建議、不懂可以在右上旁邊留言

[oj離線網址](https://nthuoj-archive.yikuo.dev)
:::spoiler 如何寫得更快更精簡
1. 數學運算用','隔開，善用'='
```c=
a = 1;
b = 0;
c = 0;
------寫成 ------
a = 1, b = c = 0;
```
2. define for 成你想要的名字(我是REP)
```c= 
int n,m,z,x[10][10][10];
int main(void){
    scanf("%d%d%d",&n,&m,&z);
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            for(int k=0;k<z;k++)
                scanf("%d",&x[i][j][k]);
}
------寫成------
#define REP(i,j,k) for(int i=j;i<k;i++)
int n,m,z,x[10][10][10];
int main(void){
    scanf("%d%d%d",&n,&m,&z);
    REP(i,0,n) REP(j,0,m) REP(k,0,z) 
        scanf("%d",&x[i][j][k]);
}
```
:::
# Yang-109
## Lab 
### [lab1](https://acm.cs.nthu.edu.tw/contest/2092/)
-
    :::spoiler 11543 - number reverse and average   
    ```c=
    #include<stdio.h>
    int a,b,c;
    main(){
        scanf("%d",&a), c = a;
        while(c) b = b*10+c%10, c/=10;
        printf("%.1lf",(a+b)*0.5);
    }
    ```
    :::
    :::spoiler 12872 - Ruby and Sapphire  
    ```c=
    #include<stdio.h>
    int a,b;
    main(){
        scanf("%d%d",&a,&b);
        printf("%d %d\n",a-(b-a*5)/2,(b-a*5)/2);
    }
    ```
    :::
### [lab2](https://acm.cs.nthu.edu.tw/contest/2100/)
-
    :::spoiler 11111 - Encode number   
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    char a[3];
    main(){
        REP(i,0,3) scanf("%c",&a[i]);
        REP(i,0,3) printf("%c",'A'+a[i]-'1');
    }
    ```
    :::
    ::: spoiler 12886 - Thousands Separator Lite  
    ```c=
    #include<stdio.h>
    int a[3],b[3];
    main(){
        scanf("%d,%d,%d",&a[0],&a[1],&a[2]);
        scanf("%d,%d,%d",&b[0],&b[1],&b[2]);
        printf("%d\n",(a[0]+b[0])*1000000+(a[1]+b[1])*1000+a[2]+b[2]);
    }
    ```
    :::
### [lab3](https://acm.cs.nthu.edu.tw/contest/2111/)
-
    :::spoiler 12893 - Let's build a sequence
    ```c=
    #include<stdio.h>
    int main(void){
        int n,a1,a2,a3,cnt,ans;
        scanf("%d%d%d%d",&n,&a1,&a2,&a3);
        printf("%d %d %d",a1,a2,a3);
        ans = a3, cnt = a3-a2;
        for(int i=3;i<n;i++){
            cnt += a3-2*a2+a1, ans += cnt;
            printf(" %d",ans);
        }
        printf("\n");
    }
    ```
    :::
    :::spoiler 11134 - Swap number
    ```c=
    #include<stdio.h>
    int main(void){
        int n,a,b,c,ans[5];
        scanf("%d",&n);
        for(int i=0;i<5;i++) ans[i] = i;
        while(n--){
            scanf("%d%d",&a,&b);
            c = ans[a], ans[a] = ans[b], ans[b] = c;
        }
        for(int i=0;i<5;i++) printf("%s%d",i?" ":"",ans[i]);
    }
    ```
    :::
### [lab4](https://acm.cs.nthu.edu.tw/contest/2125/)
-
    :::spoiler 11146 - Find the maximum/minimum values
    ```c=
    #include <stdio.h>
    #include <stdlib.h>
    int main(void){      
        int n,m,ma=-1e9,mi=1e9,a,max,may,mix,miy;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                scanf("%d",&a);
                if(a>ma) ma = a,max = i,may = j;
                if(a<mi) mi = a,mix = i,miy = j;
            }
        printf("%d %d",abs(max-mix)+abs(may-miy),ma-mi);
    }
    ```
    :::
    :::spoiler 12901 - Prepare Exam
    ```c=
    #include <stdio.h>
    #define MX 100005
    int main(void){
        int n,x[MX],y[MX],c[105][105]={1},ans = 1,mo = 10007;
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&x[i]);
        for(int i=0;i<n;i++) scanf("%d",&y[i]);
        for(int i=1;i<101;i++){
            c[i][0] = 1;
            for(int j=1;j<101;j++)
                c[i][j] = (c[i-1][j]+c[i-1][j-1])%mo;
        }
        for(int i=0;i<n;i++) ans = ans*c[x[i]][y[i]]%mo;
        printf("%d\n",ans);
    }
    ```
    ```c=
    #include<stdio.h>
    #define MOD 10007
    int combi[500][500]={};

    int gen(int n, int k)
    {
        int ans;
        if(combi[n][k]) return combi[n][k];
        if(k == 0 || n == k) ans = 1;
        else ans = gen(n-1, k) + gen(n-1, k-1);
        ans %= MOD;
        combi[n][k] = ans;
        return ans;
    }
    int main()
    {
        int N, x[100005]={}, y[100005]={};
        scanf("%d", &N);
        for(int i = 0; i < N; i++) scanf("%d",&x[i]);
        for(int i = 0; i < N; i++) scanf("%d",&y[i]);
        int ans = 1; 
        for(int i = 0; i < N; i++)
        {
            ans = (ans * gen(x[i], y[i])) % MOD;
        }
        printf("%d\n", ans);
        return 0;
    }
    ```
    :::  
### [lab5](https://acm.cs.nthu.edu.tw/contest/2136/)
-
    :::spoiler 10769 - Two-dimensional array rotation
    ```c=
    #include<stdio.h>
    int main()
    {
        int N, arr[25][25]={};
        scanf("%d", &N);
        for(int row = 0; row < N; row++)
            for(int col = 0; col < N; col++)
                scanf("%d", &arr[row][col]);
        int yHead = 0, xHead = 0, layer = 0;
        while(layer++ < 2*N-1)
        {
            int y = yHead, x = xHead;
            for(int i = 0; i < layer && i < 2*N-layer; i++)
            {
                i == layer-1 || i == 2*N-layer-1 ? printf("%d\n", arr[y][x]) : printf("%d ", arr[y][x]);
                i == layer-1 || i == 2*N-layer-1 ? 0 : y--, x++;
            }
            if(layer < N) yHead++;
            else xHead++;
        }
    }
    ```
    :::
    :::spoiler 12879 - Flash Card Game   
    ```c=
    #include<stdio.h>
    int main(void){
        int a,p=0,n=0; 
        for(int i=0;i<4;i++){
            scanf("%d",&a);
            if(a%2==0 && a>0) p++;
            if(a%2==0 && a<0) n++;
        }
        if(p>n) printf("Sammy\n");
        else if(p>=n-1) printf("Tie\n");
        else printf("Rachel\n");
    }
    ```
    :::
### [lab6](https://acm.cs.nthu.edu.tw/contest/2143/)
-
    :::spoiler 12446 - Bacteria Widespread   
    ```c=
    #include<stdio.h>
    int r,c,t,v,tim,x[10000+5],y[10000+5],dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
    char ari[105][105];
    int main(){
        scanf("%d %d %d\n",&r,&c,&t);
        for(int i=0;i<r;i++) for(int j=0;j<c+1;j++) scanf("%c",&ari[i][j]); 
        while(t--){
            v=0;tim=0;
            for(int i=0;i<r;i++) for(int j=0;j<c+1;j++) 
                if(ari[i][j]=='F') x[v]=i, y[v]=j, v++, tim++;        
            for(int i=0;i<tim;i++) for(int j=0;j<4;j++)
                if(ari[x[i]+dx[j]][y[i]+dy[j]]=='C') ari[x[i]+dx[j]][y[i]+dy[j]]='F';
        }
        for(int i=0;i<r;i++) for(int j=0;j<c+1;j++)  printf("%c",ari[i][j]);
    }
    ```
    :::
    :::spoiler Let's build a Nonogram Validator   
    只數個數是錯的
    ```c=
    !!!!!!!!!!這是假解
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int t,n,m,a,b,x[50],y[50],cnt,ok;
    char c[50][50];
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m), ok = 1;
            REP(i,0,n){
                scanf("%d",&a), x[i] = 0;
                REP(j,0,a) scanf("%d",&b), x[i] += b;
            }
            REP(i,0,m){
                scanf("%d",&a), y[i] = 0;
                REP(j,0,a) scanf("%d",&b), y[i] += b;
            }
            REP(i,0,n) scanf("%s",&c[i]);
            REP(i,0,n){
                cnt = 0;
                REP(j,0,m) if(c[i][j]=='o') cnt++;
                if(cnt!=x[i]) ok = 0;
            }
            REP(i,0,m){
                cnt = 0;
                REP(j,0,n) if(c[j][i]=='o') cnt++;
                if(cnt!=y[i]) ok = 0;
            }
            printf(ok?"Yes\n":"No\n");
        }
    }
    ```
    ```c=
    //這才是正解
    #include<stdio.h>
    int t,n,m,dx[50],dy[50],x[50][50],y[50][50],cnt,p,ok;
    char c[50][50];
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m), ok = 1;
            for(int i=0;i<n;i++){
                scanf("%d",&dx[i]);
                for(int j=0;j<dx[i];j++) scanf("%d",&x[i][j]);
            }
            for(int i=0;i<m;i++){
                scanf("%d",&dy[i]);
                for(int j=0;j<dy[i];j++) scanf("%d",&y[i][j]);
            }
            for(int i=0;i<n;i++) scanf("%s",&c[i]);
            for(int i=0;i<n;i++){
                cnt = p = 0;
                for(int j=0;j<m;j++){
                    if(c[i][j]=='o') cnt++;
                    if((c[i][j]=='x' || cnt && j==m-1) && cnt){
                        if(x[i][p]!=cnt) ok = 0;
                        p++, cnt = 0;
                    }
                }
                if(p!=dx[i]) ok = 0;
            }
            for(int i=0;i<m;i++){
                cnt = p = 0;
                for(int j=0;j<n;j++){
                    if(c[j][i]=='o') cnt++;
                    if((c[j][i]=='x' || j==n-1) && cnt){
                        if(y[i][p]!=cnt) ok = 0;
                        p++, cnt = 0;
                    }
                }
                if(p!=dy[i]) ok = 0;
            }
            printf("%s\n",ok?"Yes":"No");
        }
    }
    ```
    :::
### [mid1](https://acm.cs.nthu.edu.tw/contest/2152/)
-
    :::spoiler 11146 - Find the maximum/minimum values
    ```c=
    #include <stdio.h>
    #include <stdlib.h>
    int main(void){      
        int n,m,ma=-1e9,mi=1e9,a,max,may,mix,miy;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                scanf("%d",&a);
                if(a>ma) ma = a,max = i,may = j;
                if(a<mi) mi = a,mix = i,miy = j;
            }
        printf("%d %d",abs(max-mix)+abs(may-miy),ma-mi);
    }
    ```
    :::
    :::spoiler 12941 - The Game of Life   
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #include<string.h>
    int t,n,m,a[505][505],b[505][505],cnt;
    int main(){
        scanf("%d%d%d",&n,&m,&t);
        REP(i,1,n+1) REP(j,1,m+1) scanf("%d",&a[i][j]);
        while(t--){
            REP(i,1,n+1) REP(j,1,m+1){
                cnt = 0;
                if(a[i][j]){
                    REP(ii,-1,2) REP(jj,-1,2)
                        if(ii || jj) cnt += a[i+ii][j+jj];
                    if(cnt==2 || cnt==3) b[i][j] = 1;
                }
                else{
                    REP(ii,-1,2) REP(jj,-1,2)
                        cnt += a[i+ii][j+jj];
                    if(cnt==3) b[i][j] = 1;
                }
            }
            REP(i,1,n+1) REP(j,1,m+1) a[i][j] = b[i][j], b[i][j] = 0;
        }
        REP(i,1,n+1){
            REP(j,1,m+1){
                printf("%d",a[i][j]);
                if(j!=m) printf(" ");
            }
            printf("\n");
        }
    }
    ```
    :::
    :::spoiler 12950 - How Many Magic Spells 
    ```c=
    #include<stdio.h>
    #include<string.h>
    int t,q,l,r,ans[2005][2005],la,lb;
    char a[2005],b[2005];
    int main(){
        scanf("%d",&t);
        while(t--){
            scanf("%s%s%d",a,b,&q);
            la = strlen(a), lb = strlen(b);
            for(int i=0;i<la;i++)
                for(int j=0;j<la;j++)
                    ans[i][j] = 0;
            for(int i=0;i<la;i++){
                for(int j=0;j<lb && i+j<la;j++){
                    if(a[i+j]!=b[j]) break;
                    ans[i][i+j]++;
                }
            }
            for(int i=la-1;i>=0;i--)
                for(int j=0;j<la;j++) 
                    ans[i][j] += ans[i+1][j];
            while(q--){
                scanf("%d%d",&l,&r);
                printf("%d\n",ans[l][r]+1);
            }
        }
    }
    ```
    :::
### [lab7](https://acm.cs.nthu.edu.tw/contest/2165/)
-
    :::spoiler 12439 - Little Brick's Functions 
    ```c=
    #include<stdio.h>
    int GCD(int a,int b){
        while(b){
            int c = a%b;
            a = b, b = c;
        }
        return a;
    }
    int LCM(int a,int b){ 
        return a*b/GCD(a,b);
    }
    int POWER(int a,int b){
        int c=1;
        for(int i=0;i<b;i++) c*=a;
        return c;
    }
    int A,B,C,D;
    int main(){
        scanf("%d%d%d%d",&A,&B,&C,&D);
        printf("%d\n%d\n%d\n%d\n%d\n%d\n",GCD(LCM(POWER(A, B), C), D), 
                                          GCD(POWER(LCM(A, B), C), D), 
                                          LCM(GCD(POWER(A, B), C), D), 
                                          LCM(POWER(GCD(A, B), C), D), 
                                          POWER(GCD(LCM(A, B), C), D), 
                                          POWER(LCM(GCD(A, B), C), D));
    }
    ```
    :::
    :::spoiler 12974 - Let's Puzzle   

    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,m,t,c,r,ans,ok;
    char a[100][100],b[100][100];
    int main(){
        scanf("%d%d",&n,&m);
        REP(i,0,n) scanf("%s",a[i]);
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&c,&r), ans = 0;
            REP(i,0,c) scanf("%s",b[i]);
            REP(i,0,n) REP(j,0,m){
                ok = 1;
                REP(ii,0,c) REP(jj,0,r) 
                    if(b[ii][jj]=='#' && a[i+ii][j+jj]!='o') ok = 0;
                if(ok) ans = 1;
            }
            printf(ans?"Yes\n":"No\n");
        }
    }
    ```
    :::
### [lab8](https://acm.cs.nthu.edu.tw/contest/2174/)
-
    :::spoiler 11200 - Tower of Hanoi  
    ```c=
    #include <stdio.h>
    void hanoi(int n, char A, char B, char C) {
        if (n == 0)
            return;
        hanoi(n - 1, A, C, B);
        /* Original output
         * printf("Move disk %d from %c to %c", n, A, C);
         */
        printf("%d\n", n);
        hanoi(n - 1, B, A, C);
    }
    int main() {
        int n;
        scanf("%d", &n);
        hanoi(n, 'A', 'B', 'C');
        return 0;
    }
    ```
    :::
    ::: spoiler 12991 - Toad Jumping   
    ```c=
    #include <stdio.h>

    int n, s, t;
    int color[25], height[25];
    int vis[25];
    int ans, maxJ; // maxJ -> max jump

    int abs(int x) {
        return x > 0 ? x : -x;
    }
    int max(int x, int y) {
        return x > y ? x : y;
    }

    void find(int pos, int sum, int jumps) { // pos -> current position
        int i;
        if (pos == t) {
            if (sum >= ans) {
                ans = sum;
                maxJ = max(maxJ, jumps);
            }
            return;
        }
        vis[pos] = 1;
        for (i = 1; i <= n; i++) {
            if (vis[i] == 0 && (abs(i - pos) == 1 || color[i] == color[pos])) {
                find(i, sum + abs(i - pos) * abs(height[i] - height[pos]), jumps + 1);
            }
        }
        vis[pos] = 0;
    }

    int main() {
        int i;
        scanf("%d %d %d", &n, &s, &t);
        for (i = 1; i <= n; i++) {
            scanf("%d", &height[i]);
        }
        for (i = 1; i <= n; i++) {
            scanf("%d", &color[i]);
        }
        find(s, 0, 0);
        printf("%d %d\n", ans, maxJ);
        return 0;
    }
    ```
    :::
### [lab9](https://acm.cs.nthu.edu.tw/contest/2181/)
-
    :::spoiler 11222 - N queens
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int n,ans,cc[15],oo[25],xx[25];
    void f(int level){
        if(level==n) ans++;
        else 
            REP(i,0,n) if(cc[i]+oo[n+level-i]+xx[level+i]==0){
                cc[i] = oo[n+level-i] = xx[level+i] = 1;
                f(level+1);
                cc[i] = oo[n+level-i] = xx[level+i] = 0;
            }
    }
    main(){
        scanf("%d",&n);
        f(0);
        printf("%d",ans);
    }
    ```
    :::
    :::spoiler 13000 - Let's build a more powerful hacker script   
    ```c=
    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int t,ans,la,lb;
    char a[30],b[30];
    void f(int aa,int bb,int c){
        if(aa==la && bb==lb) ans++;
        else if(b[bb]=='#' && aa<la){
            f(aa+1,bb,0);
            f(aa+1,bb+1,0);
        }
        else if(b[bb]=='$' && aa<la && (!c || c==a[aa])){
            f(aa+1,bb,a[aa]);
            f(aa+1,bb+1,0);
        }
        else if(aa<la && bb<lb && a[aa]==b[bb]) f(aa+1,bb+1,0);
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%s%s",a,b);
            la = strlen(a), lb = strlen(b), ans = 0;
            f(0,0,0);
            printf("%d\n",ans);
        }
    }
    ```
    :::
### [lab10](https://acm.cs.nthu.edu.tw/contest/2190/)
-
    :::spoiler 11291 - Mouse Maze 
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    #define oo 1e9
    int t,n,m,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0},d[505][505],ans;
    char c[505][505];
    void dfs(int x,int y){
        if(c[x][y]=='F'){ 
            if(ans==-1 || d[x][y]<ans) ans = d[x][y];
        }
        else{
            REP(i,0,4){
                int nx = x+dx[i], ny = y+dy[i];
                if(0<=nx && nx<n && 0<=ny && ny<m && c[nx][ny]!='#' && d[x][y]+1<d[nx][ny]) 
                    d[nx][ny] = d[x][y]+1, dfs(nx,ny);
            }
        }
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m), ans = -1;
            REP(i,0,n) scanf("%s",c[i]);
            REP(i,0,n) REP(j,0,m) d[i][j] = oo;
            REP(i,0,n) REP(j,0,m) 
                if(c[i][j]=='S') d[i][j] = 0, dfs(i,j);
            printf("%d\n",ans);
        }
    }
    ```
    :::
    :::spoiler 13022 - Message Recover   
    ```c=
    void solver(char **ptr, int *n, int P, char *M){
        int num=0,cnt[1005]={},lum,len = strlen(M),ok = 0;
        for(int i=0;i<len;i++){
            if('0'<=M[i] && M[i]<='9') num = num*10+M[i]-'0',ok = 1;
            else{
                if(ok) lum = num, num = ok = 0;
                ptr[lum%P][cnt[lum%P]++] = M[i];
            }
        }
        for(int i=0;i<P;i++) if(cnt[i]) *n = *n+1;
    } 
    ```
    :::
### [mid2](https://acm.cs.nthu.edu.tw/contest/2207/)
-
    :::spoiler 12073 - character replacement
    ```c=
    int changeCharacter(char *str, char a, char b){
        int len = strlen(str);
        for(int i=0;i<len;i++) if(str[i]==a) str[i] = b;
        return 0;
    }
    ```
    :::    
    :::spoiler 12945 - Magicka Spell
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define swap(a,b) a^=b^=a^=b
    #define max(i,j) i>j?i:j
    int n,l;
    char s[505][505];
    main(){
        scanf("%d",&n);
        REP(t,0,n){
            scanf("%s",s[t]);
            l = strlen(s[t]);
            REP(i,0,l) REP(j,0,i)
                if(s[t][i]>s[t][j]) swap(s[t][i],s[t][j]);
        }
        REP(i,0,n) REP(j,0,n){
            if(strlen(s[i])>strlen(s[j]) || (strlen(s[i])==strlen(s[j]) && strcmp(s[i],s[j])>0)){
                l = max(strlen(s[i]),strlen(s[j]));
                REP(k,0,l) swap(s[i][k],s[j][k]);
            }
        }
        REP(i,0,n) if(i==0 || strcmp(s[i],s[i-1])) printf("%s\n",s[i]);
    }
    ```
    :::
    :::spoiler 13036 - Let's regular expression matching 
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int t,la,lb,ans[505][505]={1};           
    char a[505],b[505];
    main(){
        scanf("%s%s%d",&a,&b,&t);
        la = strlen(a), lb = strlen(b);
        REP(i,0,la+1) REP(j,1,lb+1){
            if(i && (b[j-1]=='.' || a[i-1]==b[j-1]))        // '.'或者是字母 
                ans[i][j] |= ans[i-1][j-1];
            else if(b[j-1]=='*'){                           // '*' 
                ans[i][j] |= ans[i][j-2];                   //擺0個  前綴字母 
                if(i && (b[j-2]=='.' || b[j-2]==a[i-1]))    //擺連續個前綴字母
                    ans[i][j] |= ans[i-1][j];
            }
        }
        while(t--){
            scanf("%d%d",&la,&lb);
            printf(ans[la][lb]?"True\n":"False\n");
        }
    }
    ```
    :::
### [lab12](https://acm.cs.nthu.edu.tw/contest/2232/)
-
    :::spoiler 12577 - Bank Data   
    ```c=
    typedef struct _AccountData{
        char* name;
        int money;
    } AccountData;
    AccountData* createData(char* name, int money){
        AccountData* newdata=(AccountData*)malloc(sizeof(AccountData));
        newdata->name=(char*)malloc(strlen(name)*sizeof(char));
        strcpy(newdata->name,name);
        newdata->money=money;
        return newdata;
    }
    AccountData* userQuery(AccountData* data){ return createData(data->name,data->money); }
    ```
    :::
    :::spoiler 13089 - Another text editor   
    ```c=
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define NU(i,j,k) for(int i=0;i<k;i++)
    char love[1314];
    int christmas,f;
    typedef struct node{
        char c;
        struct node *l, *r;
    }Node;                                          
    void erase(Node *a){ 
        a->l->r = a->r;                                      //將a前面的跟a後面的接起
        if(a->r!=NULL) a->r->l = a->l; 
    }
    void add(Node *a, char c, int f){                 	     //把b插入a與a後面的之間 
        Node *b = (Node*)malloc(sizeof(Node));
        b->r = NULL, b->c = c;
        if(a->r!=NULL) b->r = a->r, a->r->l = b;             //將a後面的與b的接起 
        b->l = a, a->r = b;	          		  //將a與b接起 
        if(f && b->r!=NULL && b->r->c!='\n') erase(b->r);    //如果是replace 
    }
    main(){
        Node *head = (Node*)malloc(sizeof(Node));     		 //head 為開頭 
        head->r = NULL, head->l = head;
        Node *lover = head;            		                 //lover 為游標位置
        fgets(love,1314,stdin), christmas = strlen(love);
        NU(i,0,christmas-1){
            if(love[i]=='/'){
                if(love[i+1]=='I') f^=1;                                
                else if(love[i+1]=='B') erase(lover), lover = lover->l;
                else if(love[i+1]=='n') add(lover,'\n',f), lover = lover->r;
                else if(love[i+1]=='L'){ if(lover->l!=NULL) lover = lover->l;}
                else if(love[i+1]=='R'){ if(lover->r!=NULL) lover = lover->r;}
                i++;
            }
            else add(lover,love[i],f), lover = lover->r;
        }
        head = head->r;
        while(head!=NULL) printf("%c",head->c), head = head->r;
    }
    ```
    :::
### [lab13](https://acm.cs.nthu.edu.tw/contest/2243/)
-
    :::spoiler 12568 - Reverse Linked List ver 2
    ```c=
    #include"function.h"
    void Push(Node** ptr_head,int x){
        Node *a = (Node*)malloc(sizeof(Node));
        a->data = x, a->next = *ptr_head, *ptr_head = a;
    }
    void Pop(Node** ptr_head){
        if(*ptr_head==NULL) return;
        Node *a = *ptr_head;
        *ptr_head = (*ptr_head)->next;
        free(a);
    }
    void Reverse_List(Node** ptr_head){
        Node *a = NULL;
        while(*ptr_head!=NULL) Push(&a,(*ptr_head)->data), Pop(ptr_head); 
        *ptr_head = a;
    }
    ```
    :::
    :::spoiler 13099 - Wish List   
    ```c=
    #include"function.h"
    Item* CreateList(int N){
        Item *L = (Item*)malloc(sizeof(Item)*N);
        for(int i=0;i<N;i++) L[i].name = (char*)malloc(sizeof(char)*101);
        return L;
    }
    void AddItem(Item* L, int idx, char* name, int price, int discount, int quality){
        strcpy(L[idx].name,name), L[idx].price = price, L[idx].discount = discount, L[idx].quality = quality;
    }
    void DeleteList(Item* L, int N){
        for(int i=0;i<N;i++) free(L[i].name);    
        free(L);
    }

    int price_cmp( const void* lhs, const void* rhs ){
        Item a = *(Item*)lhs, b = *(Item*)rhs;
        if(a.price-a.discount <  b.price-b.discount) return -1;
        if(a.price-a.discount == b.price-b.discount) return 0;
        if(a.price-a.discount >  b.price-b.discount) return 1;
    }
    int discount_cmp( const void* lhs, const void* rhs ){
        Item a = *(Item*)lhs, b = *(Item*)rhs;
        if(a.discount <  b.discount) return 1;
        if(a.discount == b.discount) return 0;
        if(a.discount >  b.discount) return -1;
    }
    int quality_cmp( const void* lhs, const void* rhs ){
        Item a = *(Item*)lhs,b = *(Item*)rhs;
        if(a.quality <  b.quality) return 1;
        if(a.quality == b.quality) return 0;
        if(a.quality >  b.quality) return -1;
    }
    ```
    :::
### [Final](https://acm.cs.nthu.edu.tw/contest/2245/)
-
    :::spoiler 12845 - Integer pointer array 
    ```c=
    #include"function.h"
    int** malloc_ptr(int array_size){
        int **ptr = (int**)malloc(sizeof(int*)*array_size);
        return ptr;
    }
    void malloc_array(int **array, int array_size){
        *array = (int*)malloc(sizeof(int)*array_size);
    }
    void pointer_ptr_to_array(int *array, int **ptr,int N){
        for(int i=0;i<N;i++) ptr[i] = &array[(i+1)*i/2];
    }
    ```
    :::
    :::spoiler 12846 - Reverse Linked List ver 2
    ```c=
    #include"function.h"
    void Push(Node** ptr_head,int x){
        Node *a = (Node*)malloc(sizeof(Node));
        a->data = x, a->next = *ptr_head, *ptr_head = a;
    }
    void Pop(Node** ptr_head){
        if(*ptr_head==NULL) return;
        Node *a = *ptr_head;
        *ptr_head = (*ptr_head)->next;
        free(a);
    }
    void Reverse_List(Node** ptr_head){
        Node *a = NULL;
        while(*ptr_head!=NULL) Push(&a,(*ptr_head)->data), Pop(ptr_head); 
        *ptr_head = a;
    }
    ```
    :::
    :::spoiler 12847 - Small Cat Society
    ```c=
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define MX 10005
    int n,m,ans[MX],age[MX],num[MX];
    char name[MX][35],oc[MX][35],p[4] = "eka";
    int cmp(const void *a,const void *b){
        int i = *(int*)a, j = *(int*)b;
        if(num[i]!=num[j]) return num[i]<num[j]?-1:1;
        if(age[i]!=age[j]){
            if(num[i]==2) return age[i]<age[j]?-1:1;
            return age[i]>age[j]?-1:1;
        }
        return strcmp(name[i],name[j]);
    }
    main(){
        while(~scanf("%d%d",&n,&m)){
            REP(i,0,n){
                scanf("%s%s%d",name[i],oc[i],&age[i]), ans[i] = i;
                REP(j,0,3) if(oc[i][0]==p[j]) num[i] = j;	
            }
            qsort(ans,n,sizeof(int),cmp);
            if(m<n) n=m;                               //爛題敘 
            REP(i,0,n) printf("%s\n",name[ans[i]]);
        }
    }
    ```
    :::
    :::spoiler 13100 - oitaR nedloG Solarbeam 
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    long long t,f[80],n,k;
    char s[2][105];
    void dfs(long long n,long long k){
        if(n<2) printf("%c\n",s[n][k]);
        else if(k<f[n-2]) dfs(n-2,f[n-2]-k-1);
        else dfs(n-1,f[n-1]-k+f[n-2]-1);
    }
    main(){
        scanf("%lld",&t);
        while(t--){
            scanf("%s%s",s[0],s[1]), f[0] = strlen(s[0]), f[1] = strlen(s[1]);
            REP(i,2,80) f[i] = f[i-2]+f[i-1];
            scanf("%lld%lld",&n,&k);
            if(n>=80){
                if(n%3==1) dfs(79,k);
                else if(n%3==2) dfs(77,k);
                else dfs(78,k);
            }
            else dfs(n,k);
        }
    }
    ```
    :::
    :::spoiler 13101 - Let's solve the last ouo 
    ```c=
    // Author: justin0u0<mail@justin0u0.com>

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

    #define MAX_LINES 1000
    #define max(a, b) (a > b ? a : b)
    #define min(a, b) (a < b ? a : b)

    #define NormalMode false
    #define InsertMode true

    char s[2010];
    char buf[2010];

    int main() {
      int T, testcase = 0;
      scanf("%d", &T);

      while (T--) {
        scanf("%s", s);
        // Initialize
        char** ans = malloc((MAX_LINES + 10) * sizeof(char*));
        int* size = malloc((MAX_LINES + 10) * sizeof(int));
        int* capacity = malloc((MAX_LINES + 10) * sizeof(int));
        for (int i = 0; i < (MAX_LINES + 10); i++) {
          size[i] = 0;
          capacity[i] = 1;
          ans[i] = malloc(sizeof(char));
        }
        int cursorX = 0;
        int cursorY = 0;
        int startX = -1;
        int repeat = 1;
        bool mode = NormalMode;

        for (int i = 0; s[i] != '\0'; i++) {
    #ifndef ONLINE_JUDGE
          printf("%d, %c, cursorX=%d, size[cursorY]=%d\n", i, s[i], cursorX, size[cursorY]);
    #endif
          if (s[i] == ':' && s[i + 1] == 'w' && s[i + 2] == 'q') break;

          if (mode == NormalMode) {
            if (s[i] == 'h' || s[i] == 'l' || s[i] == 'x') {
              if (s[i] == 'h') {
                cursorX = max(cursorX - repeat, 0);
              } else if (s[i] == 'l') {
                cursorX = max(min(cursorX + repeat, size[cursorY] - 1), 0);
              } else if (s[i] == 'x') {
                repeat = min(repeat, size[cursorY] - cursorX);
                for (int j = cursorX + repeat; j < size[cursorY]; j++)
                  ans[cursorY][j - repeat] = ans[cursorY][j];
                size[cursorY] -= repeat;
                cursorX = max(min(cursorX, size[cursorY] - 1), 0);
              }
              repeat = 1;
              startX = -1;
            } else if (s[i] == 'j' || s[i] == 'k') {
              if (s[i] == 'j') {
                if (startX == -1) startX = cursorX;
                cursorY = min(cursorY + repeat, MAX_LINES - 1);
                cursorX = max(min(startX, size[cursorY] - 1), 0);
              } else if (s[i] == 'k') {
                if (startX == -1) startX = cursorX;
                cursorY = max(cursorY - repeat, 0);
                cursorX = max(min(startX, size[cursorY] - 1), 0);
              }
              repeat = 1;
            } else if (s[i] == 'a' || s[i] == 'A' || s[i] == 'i' || s[i] == 'I') {
              mode = InsertMode;
              if (s[i] == 'a') {
                cursorX = min(cursorX + 1, size[cursorY]);
              } else if (s[i] == 'A') {
                cursorX = size[cursorY];
              } else if (s[i] == 'i') {
                cursorX = cursorX;
              } else if (s[i] == 'I') {
                cursorX = 0;
              }
              startX = -1;
            } else if (s[i] >= '0' && s[i] <= '9') {
              repeat = s[i] - '0';
              while (s[i + 1] >= '0' && s[i + 1] <= '9') {
                i++;
                repeat = repeat * 10 + s[i] - '0';
              }
            }
          } else if (mode == InsertMode) {
            if (s[i] == 'E' && s[i + 1] == 'S' && s[i + 2] == 'C') {
              mode = NormalMode;
              i += 2; // Skip ESC
              cursorX = max(cursorX - 1, 0);
            } else {
              int idx = 0;
              buf[idx++] = s[i];
              while (s[i + 1] >= 'a' && s[i + 1] <= 'z') {
                i++;
                buf[idx++] = s[i];
              }
              // Increase capacity if needed
              if (idx * repeat + size[cursorY] >= capacity[cursorY]) {
                while (idx * repeat + size[cursorY] >= capacity[cursorY]) {
                  capacity[cursorY] *= 2;
                }
                char *copied = malloc(capacity[cursorY] * sizeof(char));
                for (int j = 0; j < size[cursorY]; j++)
                  copied[j] = ans[cursorY][j];
                free(ans[cursorY]);
                ans[cursorY] = copied;
              }

              for (int j = size[cursorY] - 1; j >= cursorX; j--)
                ans[cursorY][j + idx * repeat] = ans[cursorY][j];
              for (int j = 0; j < idx * repeat; j++)
                ans[cursorY][j + cursorX] = buf[j % idx];
              size[cursorY] += idx * repeat;
              cursorX += idx * repeat;
            }
            repeat = 1;
          }
        }

        printf("Case #%d:\n", ++testcase);
        for (int i = 0; i < MAX_LINES; i++) {
          if (size[i] > 0) {
            ans[i][size[i]] = '\0';
            printf("%d: %s\n", i + 1, ans[i]);
          }
        }

        for (int i = 0; i < (MAX_LINES + 10); i++) {
          free(ans[i]);
        }
        free(size);
        free(capacity);
        free(ans);
      }
      return 0;
    }
    ```
    :::
Homework [close]
---
### [HW1](https://acm.cs.nthu.edu.tw/contest/2087/)
-
    :::spoiler 11543 - number reverse and average   
    ```c=
    #include<stdio.h>
    int a,b,c;
    main(){
        scanf("%d",&a), c = a;
        while(c) b = b*10+c%10, c/=10;
        printf("%.1lf",(a+b)*0.5);
    }
    ```
    :::
    :::spoiler 12353 - C is for Cat   
    ```c=
    #include<stdio.h>
    main(){
        printf(" ^   ^      \n(=-w-=)----?\n  \" \"   \" \" \n");
    }
    ```
    :::
### [HW2](https://acm.cs.nthu.edu.tw/contest/2097/)
-
    :::spoiler 11576 - Time conversion   
    ```c = 
    #include<stdio.h>
    int a;
    main(){
        scanf("%d",&a);
        printf("%02d:%02d %c.m.",(a/100)%12,a%100,(a/100/12)%2?'p':'a');
    }
    ```
    :::
    :::spoiler 12366 - svool dliow 
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    char c[5];
    main(){
        REP(i,0,5) scanf("%c",&c[i]);
        REP(i,0,5) printf("%c",'z'-c[i]+'a');
        printf("\n");
    }
    ```
    :::
### [HW3](https://acm.cs.nthu.edu.tw/contest/2105/)
-
    :::spoiler 11112 - Big Number   
    ```c=
    #include <stdio.h>
    int first4(int x){ return x/10000;}
    int last4(int x){ return x%10000;}
    int first8(int x){ return x/100000000;}
    int last8(int x){ return x%100000000;}
    int shift4(int x){ return x*10000;}
    int main(void){
        int x;
        int a, b;
        int c1, c2, c3;
        /* Assume that the input is always an 8-digit positive integer. */
        scanf("%d",&x); 
        a = first4(x);
        b = last4(x);
        c3 = last4(b*b);
        c2 = shift4(last4(a*a))+2*a*b+first4(b*b);
        c1 = first4(a*a);
        printf("%4d%08d%04d",c1+first8(c2),last8(c2),c3);  
        /* %04d will display a 4-digit number and add 0 as padding before the number if necessary */
        return 0;
    }
    ```
    :::
    :::spoiler 11127 - Binary representation&sum   
    ```c=
    #include<stdio.h>
    int n,a[11],cnt,p;
    int main(){
        scanf("%d",&n);
        while(n) a[cnt++] = n%2, n/=2; 
        a[0]++;
        while(a[p]==2) a[p++] = 0, a[p]++;
        for(int i=(cnt>p?cnt:p)-1;i>=0;i--) printf("%d",a[i]);
        printf(" %d",p);
    }
    ```
    :::
    :::spoiler 12880 - Let's build a RPG game
    ```c=
    #include<stdio.h>
    int ph,pa,pd,eh,ea,ed;
    int main(){
        scanf("%d%d%d%d%d%d",&ph,&pa,&pd,&eh,&ea,&ed);
        printf("Battle Start \\^_^/\n");
        while(ph>0 && eh>0){
            printf("The player dealt %d damage to the enemy and the enemy dealt %d damage to the player\n",pa-ed,ea-pd);
            printf("The player has %d HP left and the enemy has %d HP left\n",ph=ph-ea+pd,eh=eh-pa+ed);
        }
        printf("Battle End \\^_^/\n");
    }
    ```
    :::
### [HW4](https://acm.cs.nthu.edu.tw/contest/2114/)
-
    :::spoiler 11593 - Mexican Wave
    ```c=
    #include<stdio.h>
    //Mexican Wave
    int main()
    {
        int T, n, m, t;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d", &n, &m, &t);
            //
            for(int i = 0; i < n && i < t-m; i++) printf("-");
            for(int i = 0; i < t && i < m && i < n-t+m; i++) printf("^");
            for(int i = 0; i < n-t; i++) printf("-");
            printf("\n");
        }
        return 0;
    }
    ```
    :::
    :::spoiler 12009 - Caesar salad
    ```c=
    #include<stdio.h>
    //Caesar salad
    int main()
    {
        char inp[4];
        int n;
        scanf("%s%d", inp, &n);
        for(int i = 0;i < 3; i++) inp[i] = (inp[i] - 'A' + n % 26 + 26) % 26 + 'A';
        printf("%s\n", inp);
    }
    ```
    :::
    :::spoiler 12891 - Longest Row Vector
    ```c=
    #include<stdio.h>
    //Longest Row Vector
    int main()
    {
        //printf("start\n");
        int m, n, K;
        short arr[1005][1005];
        scanf("%d %d %d", &m, &n, &K);
        // read input
        for(int row = 0; row < m; row++)
        for(int col = 0; col < n; col++)
        {
            scanf("%d", &arr[row][col]);
        }
        // read tasks  //這個大括號可以省略（因為敘述只有一行）
        while(K--)
        {
            int cmd, i, j;
            scanf("%d%d%d", &cmd, &i, &j);
            if(cmd == 0)for(int col = 0; col < n; col++)
            {
                //swap
                arr[i][col] += arr[j][col];
                arr[j][col] = arr[i][col] - arr[j][col];
                arr[i][col] = arr[i][col] - arr[j][col];
            }
            else for(int col = 0; col < n; col++) arr[i][col] += arr[j][col];
        }

        int max = 0, rowidx;
        for(int row = 0, tmp = 0; row < m; row++)
        {
            for(int col = 0; col < n; col++)
            {
                //count sum of square
                tmp += arr[row][col] * arr[row][col];
            }
            if(tmp > max)
            {
                //replace max and rowidx to the bigger one
                max = tmp;
                rowidx = row;
            }
        }
        for(int col = 0; col < n; col++)
        {
            //output answer
            col == n-1 ? printf("%d\n", arr[rowidx][col]) : printf("%d ", arr[rowidx][col]);
        }
        return 0;
    }
    ```
    :::
### [HW5](https://acm.cs.nthu.edu.tw/contest/2126/)
-
    :::spoiler 9015 - Palindrome
    ```c=
    #include<stdio.h>
    int main()
    {
        char s[100005];
        while(scanf("%s", s)!=EOF)
        {
            int len = 0, ispalin = 1;
            for(int i = 0; s[i] != '\0'; i++) len++;
            for(int l = 0, r = len-1; l < r; l++, r--) if(s[l] != s[r])
            {
                ispalin = 0;
                break;
            }
            if(ispalin) printf("Yes\n");
            else printf("No\n");
        }
    }
    ```
    :::
    :::spoiler 10769 - Two-dimensional array rotation
    ```c=
    #include<stdio.h>
    int main()
    {
        int N, arr[25][25]={};
        scanf("%d", &N);
        for(int row = 0; row < N; row++)
            for(int col = 0; col < N; col++)
                scanf("%d", &arr[row][col]);
        int yHead = 0, xHead = 0, layer = 0;
        while(layer++ < 2*N-1)
        {
            int y = yHead, x = xHead;
            for(int i = 0; i < layer && i < 2*N-layer; i++)
            {
                i == layer-1 || i == 2*N-layer-1 ? printf("%d\n", arr[y][x]) : printf("%d ", arr[y][x]);
                i == layer-1 || i == 2*N-layer-1 ? 0 : y--, x++;
            }
            if(layer < N) yHead++;
            else xHead++;
        }
    }
    ```
    :::
    :::spoiler 12898 - Enola
    ```c=
    //c version
    #include<stdio.h>
    int main()
    {
        int n, m;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            char a[1005], b[1005];
            int acnt[30]={}, bcnt[30]={}, iscorrect = 1;
            scanf("%s %s", a, b);
            for(int i = 0; a[i]!='\0'; i++) acnt[a[i]-'a']++;
            for(int i = 0; b[i]!='\0'; i++) bcnt[b[i]-'a']++;
            for(int i = 0; i < 26; i++) if(acnt[i] != bcnt[i])
            {
                iscorrect = 0;
                break;
            }
            if(iscorrect) printf("YES\n");
            else printf("NO\n");
        }
    }
    ```
    ```cpp=
    //(請用C++17)
    #include<bits/stdc++.h>   //無敵標頭檔 (要用C++17)
    using namespace std;
    int n,m;
    string a,b;
    int main(void){
        while(cin>>n>>m){
            cin>>a>>b;
            sort(a.begin(),a.end()); 
            sort(b.begin(),b.end());
            if(a==b) cout<<"YES\n";
            else cout<<"NO\n";
        }
    }
    ```
    :::
### [HW6](https://acm.cs.nthu.edu.tw/contest/2137/)
-
    :::spoiler 12430 - Sudoku Validator   
    ```c=
    #include<stdio.h>
    int main(void){
        int a=0,b=0,is_que=0,no=0,num[10];
        char m[9][9],s[20];
        for(int i=0;i<13;i++){
            scanf("%s",s);
            if(i%4){
                b = 0;
                for(int j=0;j<13;j++)
                    if(j%4) m[a][b++] = s[j], is_que += (s[j]=='x');
                a++;
            }
        }
        for(int i=0;i<9;i++){        //row
            for(int k=1;k<10;k++) num[k] = 0;
            for(int j=0;j<9;j++) if(m[i][j]!='x') num[m[i][j]-'0']++;
            for(int k=1;k<10;k++) no += (num[k]>1);
        }
        for(int i=0;i<9;i++){		 //column
            for(int k=1;k<10;k++) num[k] = 0;
            for(int j=0;j<9;j++) if(m[j][i]!='x') num[m[i][j]-'0']++;
            for(int k=1;k<10;k++) no += (num[k]>1);
        }
        for(int i=0;i<9;i+=3)		 //block
            for(int j=0;j<9;j+=3){
                for(int k=1;k<10;k++) num[k] = 0;
                for(int ii=0;ii<3;ii++) for(int jj=0;jj<3;jj++)
                    if(m[i+ii][j+jj]!='x') num[m[i+ii][j+jj]-'0']++;
                for(int k=1;k<10;k++) no += (num[k]>1);
            }
        printf("%s",is_que?"question, ":"solution, ");
        printf("%s\n",no?"invalid":"valid");
    }
    ```
    :::spoiler if you want to solve the sodoku
    ```c=
    #include<stdio.h>
    int sodoku[9][9]={};
    int ans[9][9]={};
    int check_row(int y, int all)
    {
        int numcnt[10]={};
        for(int col = 0; col < 9; col++) numcnt[ sodoku[y][col] ]++;
        if(!all) 
        {
            for(int i = 1; i <= 9; i++) if(numcnt[i] > 1) return 0;
        }
        else for(int i = 1; i <= 9; i++) if(numcnt[i] != 1) return 0;
        return 1;
    }
    int check_col(int x, int all)
    {
        int numcnt[10]={};
        for(int row = 0; row < 9; row++) numcnt[ sodoku[row][x] ]++;
        if(!all) 
        {
            for(int i = 1; i <= 9; i++) if(numcnt[i] > 1) return 0;
        }
        else for(int i = 1; i <= 9; i++) if(numcnt[i] != 1) return 0;
        return 1;
    }
    int check_block(int y, int x, int all)
    {
        int numcnt[10]={};
        for(int row = y - y % 3; row < y - y % 3 + 3; row++) for(int col = x - x % 3; col < x - x % 3 + 3; col++)
            numcnt[ sodoku[row][col] ]++;
        if(!all)
        {
            for(int i = 1; i <= 9; i++) if(numcnt[i] > 1) return 0;
        }
        else for(int i = 1; i <= 9; i++) if(numcnt[i] != 1) return 0;
        // printf("block clear %d %d\n", y, x);
        return 1;
    }
    int check_point(int y, int x)
    {
        if(!check_row(y, 0) || !check_col(x, 0) || !check_block(y, x, 0)) return 0;
        return 1;
    }
    int check_all()
    {
        for(int i = 0; i < 9; i++) if(!check_row(i, 1)) return 0;
        for(int i = 0; i < 9; i++) if(!check_col(i, 1)) return 0;
        for(int i = 0; i < 9; i+=3) for(int j = 0; j < 9; j+=3) if(!check_block(i, j, 1)) return 0;
        return 1;
    }
    void copy_ans()
    {
        for(int i = 0; i < 9; i++) for(int j = 0; j < 9; j++) ans[i][j] = sodoku[i][j];
    }
    int solve(int y, int x)
    {
        if(sodoku[y][x] != -1)
        {
            int found = 0;
            for(int row = y; row < 9 && !found; row++) for(int col = row == y ? x + 1 : 0; col < 9 && !found; col++)
            {
                if(sodoku[row][col] == -1) y = row, x = col, found = 1;
                else if(row == 8 && col == 8 && check_all())
                {
                    copy_ans();
                    return 1;
                }
            }
        }
        for(int i = 1; i <= 9; i++)
        {
            sodoku[y][x] = i;
            if(check_point(y, x))
            {
                if(y == 8 && x == 8)
                {
                    copy_ans();
                    return 1;
                }
                else if(solve(y, x)) return 1;
            }
        }
        sodoku[y][x] = -1;
        return 0;
    }
    int main()
    {
        char inp[20];
        int needsolve = 0;
        for(int i = 0; i < 9; i++)
        {
            if(i % 3 == 0) scanf("%s", inp);
            scanf("%s", inp);

            for(int j = 0, x = 0; j < 12; j++, x++)
            {
                if(inp[j] == '|') j++;
                if(inp[j] == 'x') sodoku[i][x] = -1, needsolve = 1;
                else sodoku[i][x] = inp[j]-'0';
            }
            if(i == 8) scanf("%s", inp);
        }
        if(needsolve)
        {
            if(solve(0, 0)) printf("question, valid\n");
            else printf("question, invalid\n");
        }
        else 
        {
            if(check_all()) printf("solution, valid\n");
            else printf("solution, invalid\n");
        }
        for(int row = 0; row < 9; row++) 
            for(int col = 0; col < 9; col++) col == 8 ? printf("%2d\n", sodoku[row][col]) : printf("%2d ", sodoku[row][col]);
        return 0;
    }
    ```
    :::
    :::spoiler 12446 - Bacteria Widespread
    ```c=
    #include<stdio.h>
    int r,c,t,v,tim,x[10000+5],y[10000+5],dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
    char ari[105][105];
    int main(){
        scanf("%d %d %d\n",&r,&c,&t);
        for(int i=0;i<r;i++) for(int j=0;j<c+1;j++) scanf("%c",&ari[i][j]); 
        while(t--){
            v=0;tim=0;
            for(int i=0;i<r;i++) for(int j=0;j<c+1;j++) 
                if(ari[i][j]=='F') x[v]=i, y[v]=j, v++, tim++;        
            for(int i=0;i<tim;i++) for(int j=0;j<4;j++)
                if(ari[x[i]+dx[j]][y[i]+dy[j]]=='C') ari[x[i]+dx[j]][y[i]+dy[j]]='F';
        }
        for(int i=0;i<r;i++) for(int j=0;j<c+1;j++)  printf("%c",ari[i][j]);
    }
    ```
    :::
### [mid1](https://acm.cs.nthu.edu.tw/contest/2138/)
-
    :::spoiler 9015 - Palindrome
    ```c=
    #include<stdio.h>
    int main()
    {
        char s[100005];
        while(scanf("%s", s)!=EOF)
        {
            int len = 0, ispalin = 1;
            for(int i = 0; s[i] != '\0'; i++) len++;
            for(int l = 0, r = len-1; l < r; l++, r--) if(s[l] != s[r])
            {
                ispalin = 0;
                break;
            }
            if(ispalin) printf("Yes\n");
            else printf("No\n");
        }
    }
    ```
    :::
    :::spoiler 11146 - Find the maximum/minimum values
    ```c=
    #include <stdio.h>
    #include <stdlib.h>
    int main(void){      
        int n,m,ma=-1e9,mi=1e9,a,max,may,mix,miy;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                scanf("%d",&a);
                if(a>ma) ma = a,max = i,may = j;
                if(a<mi) mi = a,mix = i,miy = j;
            }
        printf("%d %d",abs(max-mix)+abs(may-miy),ma-mi);
    }
    ```
    :::
    :::spoiler 11617 - pA - Arranging a Sequence 
    ```c=
    #include<stdio.h>
    int main()
    {
        int n, m, x, printed[200005]={}, oparr[100005]={}, idx = -1;
        scanf("%d %d", &n, &m);
        while(m--)
        {
            scanf("%d", &x);
            oparr[++idx] = x; // stack the numbers on
        }
        // because the number will only appear once, so if u printed it, don't print it again
        for(int i = idx; i >= 0; i--) if(!printed[ oparr[i] ])
        {
            printf("%d\n", oparr[i]);
            printed[ oparr[i] ] = 1;
        }
        for(int i = 1; i <= n; i++) if(!printed[i]) printf("%d\n", i);
        return 0;
    }
    ```
    :::
    :::spoiler 11622 - pF - Full House 
    ```c=
    #include<stdio.h>
    int t,three,two,s[300];
    char c;
    int main(void){
        scanf("%d\n",&t);
        while(t--){
            three = two = 0;
            for(int i=0;i<300;i++) s[i] = 0;
            for(int i=0;i<5;i++){
                scanf(" %c",&c), s[c]++;
                if(c=='1') scanf("%c",&c);
            }
            for(int i=0;i<300;i++) 
                three += (s[i]==3), two += (s[i]==2);
            printf("%s",three&&two?"YES\n":"NO\n");
        }
    } 
    ```
    :::
    ::: spoiler 11628 - Spiral
    ```c=
    #include<stdio.h>
    int t,n,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},d,x,y;
    char ans[5005][5005];
    int main(void){
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n), d=0, x=0, y=-1;
            for(int i=0;i<n;i++) 
                for(int j=0;j<n;j++) ans[i][j] = ' ';
            for(int k=n;k>0;k--,d=(d+1)%4)
                for(int i=0;i<k;i++) 
                    x += dx[d], y += dy[d], ans[x][y] = '#';
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++) printf("%c",ans[i][j]);
                printf("\n");
            }
        }
    } 
    ```
    :::
    :::spoiler 12446 - Bacteria Widespread
    ```c=
    #include<stdio.h>
    int r,c,t,v,tim,x[10000+5],y[10000+5],dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
    char ari[105][105];
    int main(){
        scanf("%d %d %d\n",&r,&c,&t);
        for(int i=0;i<r;i++) for(int j=0;j<c+1;j++) scanf("%c",&ari[i][j]); 
        while(t--){
            v=0;tim=0;
            for(int i=0;i<r;i++) for(int j=0;j<c+1;j++) 
                if(ari[i][j]=='F') x[v]=i, y[v]=j, v++, tim++;        
            for(int i=0;i<tim;i++) for(int j=0;j<4;j++)
                if(ari[x[i]+dx[j]][y[i]+dy[j]]=='C') ari[x[i]+dx[j]][y[i]+dy[j]]='F';
        }
        for(int i=0;i<r;i++) for(int j=0;j<c+1;j++)  printf("%c",ari[i][j]);
    }
    ```
    :::
    :::spoiler 12898 - Enola
    ```c=
    //c version
    #include<stdio.h>
    int main()
    {
        int n, m;
        while(scanf("%d %d", &n, &m) != EOF)
        {
            char a[1005], b[1005];
            int acnt[30]={}, bcnt[30]={}, iscorrect = 1;
            scanf("%s %s", a, b);
            for(int i = 0; a[i]!='\0'; i++) acnt[a[i]-'a']++;
            for(int i = 0; b[i]!='\0'; i++) bcnt[b[i]-'a']++;
            for(int i = 0; i < 26; i++) if(acnt[i] != bcnt[i])
            {
                iscorrect = 0;
                break;
            }
            if(iscorrect) printf("YES\n");
            else printf("NO\n");
        }
    }
    ```
    :::
    :::spoiler 12911 - Magic spells
    ```c=
    #include<stdio.h>
    #include<string.h>

    int main()
    {
        int n;
        scanf("%d", &n);
        while(n--)
        {
            int len1, len2, avalible;
            char s1[1005], s2[1005];
            scanf("%s%s", s1,s2);
            len1 = strlen(s1), len2 = strlen(s2);
            for(int i = len1 - len2 >= 0 ? len1 - len2 : 0; i < len1; i++)
            {
                avalible = 1;
                for(int i2 = 0, i1 = i; i1 < len1; i2++, i1++) if(s1[i1] != s2[i2])
                {
                    avalible = 0;
                    break;
                }
                if(avalible)
                {
                    s1[i] = '\0';
                    break;
                }
            }
            printf("%s%s\n", s1, s2);
        }
    }
    ```
    :::
    :::spoiler 12926 - Money Flow
    ```c=
    #include<stdio.h>
    int n,t;
    double x[505],r[505][505],cnt[505];
    main(){
        scanf("%d%d",&n,&t);
        for(int i=0;i<n;i++) scanf("%lf",&x[i]);
        for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%lf",&r[i][j]);
        while(t--){
            for(int i=0;i<n;i++) for(int j=0;j<n;j++) 
                cnt[i] += x[j]*r[j][i];
            for(int i=0;i<n;i++){
                x[i] = cnt[i], cnt[i] = 0;
                if(x[i]<10) for(int j=0;j<n;j++) 
                    if(i!=j) r[j][j] += r[j][i], r[j][i] = r[i][j] = 0;
                    else r[j][j] = 1;
            }
        }
        for(int i=0;i<n;i++) printf("%.1lf\n",x[i]);
    }
    ```
    :::
    :::spoiler 12927 - How Much Bateria
    ```c=
    #include<stdio.h>
    #define MX 1000005
    int n,q,a[MX],l,r,p[32][MX],ans;
    int main(void){
        scanf("%d%d",&n,&q);
        for(int i=1;i<n+1;i++){
            scanf("%d",&a[i]);
            for(int j=0;j<32;j++) p[j][i] = p[j][i-1]; 
            p[a[i]][i]++;
        }
        while(q--){
            scanf("%d%d",&l,&r), ans = 0;
            for(int j=0;j<32;j++) ans += (p[j][r+1]-p[j][l]>0);
            printf("%d\n",ans);
        }
    } 
    ```
    :::
### [HW7](https://acm.cs.nthu.edu.tw/contest/2158/)
-
    :::spoiler 12439 - Little Brick's Functions 
    ```c=
    #include<stdio.h>
    int GCD(int a,int b){
        while(b){
            int c = a%b;
            a = b, b = c;
        }
        return a;
    }
    int LCM(int a,int b){ 
        return a*b/GCD(a,b);
    }
    int POWER(int a,int b){
        int c=1;
        for(int i=0;i<b;i++) c*=a;
        return c;
    }
    int A,B,C,D;
    int main(){
        scanf("%d%d%d%d",&A,&B,&C,&D);
        printf("%d\n%d\n%d\n%d\n%d\n%d\n",GCD(LCM(POWER(A, B), C), D), 
                                          GCD(POWER(LCM(A, B), C), D), 
                                          LCM(GCD(POWER(A, B), C), D), 
                                          LCM(POWER(GCD(A, B), C), D), 
                                          POWER(GCD(LCM(A, B), C), D), 
                                          POWER(LCM(GCD(A, B), C), D));
    }
    ```
    :::
    :::spoiler 12910 - Let's build a Tetris  
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define RREP(i,j,k) for(int i=j-1;i>=k;i--)
    int n,m,no,cnt;                           
    char c[50][50];
    int main(){
        scanf("%d%d",&n,&m);
        REP(i,0,n) scanf("%s",c[i]);
        while(1){                                       //將'o'往下移 
            REP(i,0,n) REP(j,0,m)
                if(c[i][j]=='o' && (i==n-1 || c[i+1][j]=='x'))
                    no = 1;
            if(no) break;
            RREP(i,n,0) REP(j,0,m) 
                if(c[i][j]=='o') c[i+1][j] = 'o', c[i][j] = '.';
        }
        RREP(i,n,0){                                    //消除全滿，上往下掉 
            no = 0; 
            REP(j,0,m) 
                if(c[i][j]=='.') no = 1;                //判斷是不是全滿 
                else if(c[i][j]=='o') c[i][j] = 'x';    //順便把'o'改'x' 
            if(!no){                                    
                RREP(ii,i+1,1) REP(j,0,m) c[ii][j] = c[ii-1][j];
                REP(j,0,m) c[0][j] = '.';
                i++;
            }
        }
        REP(i,0,n) printf("%s\n",c[i]);
    }
    ```
    :::
### [HW8](https://acm.cs.nthu.edu.tw/contest/2168/)
-
    ::: spoiler 11200 - Tower of Hanoi   
    ```c=
    #include<stdio.h>
    void h(int n){
        if(n==0) return;
        h(n-1);
        printf("%d\n",n);
        h(n-1);
    }
    int n;
    int main(){
        scanf("%d",&n);
        h(n);
    }
    ```
    :::
    ::: spoiler 11224 - Prefix   
    ```c=
    #include<stdio.h>
    double f(){
        int num=0,isn=0;
        char c;
        while(scanf("%c",&c) && '0'<=c && c<='9') num = num*10+c-'0', isn = 1;
        if(isn) return printf("%d ",num), num;     //是數字輸出，return num 
        scanf(" ");                                //把多餘空白讀掉 
        printf("( ");
        double a = f();							    
        printf("%c ",c);
        double b = f();
        printf(") ");
        if(c=='/') return a/b;
        if(c=='*') return a*b;
        if(c=='+') return a+b;
        if(c=='-') return a-b;
    }
    int t;                                                                
    int main(){
        scanf("%d\n",&t);
        while(t--){
            double ans = f();
            if(ans!=(int)ans) printf("= %.1lf\n",ans);
            else printf("= %.0lf\n",ans);
        }
    }
    ```
    :::
    :::spoiler 12481 - Frog Jumping   
    ```c=
    #include<stdio.h>
    #include<math.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,a[30],ans=1e9,t;
    void dfs(int v,int sum,int cnt){
        if(v==n-1){
            if(sum<ans) ans = sum, t = cnt;
            else if(sum==ans && cnt<t) t = cnt;
        }	
        if(v+1<n) dfs(v+1,sum+abs(a[v+1]-a[v]),cnt+1);
        if(v+2<n) dfs(v+2,sum+abs(a[v+2]-a[v]),cnt+1);
    }
    int main(){
        scanf("%d",&n);
        REP(i,0,n) scanf("%d",&a[i]);
        dfs(0,0,0);
        printf("%d %d\n",ans,t);
    }
    ```
    :::
    ::: spoiler 12979 - Diet   
    ```c=
    #include<stdio.h>
    #include<math.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,k,a[30],ok;
    void dfs(int v,int cnt){
        if(v==n) ok += (cnt==k);
        else{
            dfs(v+1,cnt);
            dfs(v+1,cnt+a[v]);
        }
    }
    int main(){
        scanf("%d%d",&n,&k);
        REP(i,0,n) scanf("%d",&a[i]);
        dfs(0,0);
        printf(ok?"YES\n":"NO\n");
    }
    ```
    ```c=
    #include<stdio.h>                         //二進位枚舉寫法
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int n,k,a[30],cnt,ok;
    int main(){
        scanf("%d%d",&n,&k);
        REP(i,0,n) scanf("%d",&a[i]);
        REP(i,0,(1<<n)){
            cnt = 0;
            REP(j,0,n) if((1<<j) & i) cnt += a[j];
            if(cnt==k) ok = 1;
        }
        printf(ok?"YES\n":"NO\n");
    }
    ```
    :::
### [HW9](https://acm.cs.nthu.edu.tw/contest/2175/)
-
    :::spoiler 11222 - N queens
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int n,ans,cc[15],oo[25],xx[25];
    void f(int level){
        if(level==n) ans++;
        else 
            REP(i,0,n) if(cc[i]+oo[n+level-i]+xx[level+i]==0){
                cc[i] = oo[n+level-i] = xx[level+i] = 1;
                f(level+1);
                cc[i] = oo[n+level-i] = xx[level+i] = 0;
            }
    }
    main(){
        scanf("%d",&n);
        f(0);
        printf("%d",ans);
    }
    ```
    :::
    :::spoiler 12460 - Little Brick's Choice   
    ```c=
    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int ok,n;
    char s[20],ans[20];
    void f(int level,int cnt){
        if(level<n){
            // chose
            ans[cnt] = s[level];
            if(cnt+1>=4){
                if(ok) printf(", ");
                REP(i,0,cnt+1) printf("%c",ans[i]);
                ok = 1;
            }
            f(level+1,cnt+1);
            //not chose
            f(level+1,cnt);
        }
    }
    main(){
        scanf("%s",s);
        n = strlen(s);
        REP(i,0,n) REP(j,i+1,n) if(s[i]>s[j]){                //bubble sort
            char c = s[i];														
            s[i] = s[j], s[j] = c;
        }
        f(0,0);
        printf("\n");
    }
    ```
    :::
    :::spoiler 12987 - Let's build a hacker script  
    ```c=
    #include <stdio.h>
    #include <string.h>

    char strA[25], strB[25];
    int lenA, lenB;
    int haveAns = 0;
    int out[25];
    void find(int indexA, int indexB) {
        int i, j;
        if (indexA == lenA && indexB == lenB) {
            int printed = 0;
            for (i = j = 0; i < lenB; i++) {
                if (out[j] == -1) {
                    j++;
                    continue;
                }
                if (printed) printf(" ");
                while (j < lenA && out[j] == i) {
                    printf("%c", strA[j]);
                    printed = 1;
                    j++;
                }
            }
            printf("\n");
            haveAns = 1;
        }else if (indexA < lenA && indexB < lenB) {
            if (strB[indexB] == '#') {
                out[indexA] = indexB;
                find(indexA + 1, indexB + 1);
                find(indexA + 1, indexB);
            }else {
                out[indexA] = -1;
                if (strA[indexA] == strB[indexB])
                    find(indexA + 1, indexB + 1);
            }
        }
    }
    int main() {
        scanf("%s %s", strA, strB);
        lenA = strlen(strA);
        lenB = strlen(strB);
        find(0, 0);
        if (!haveAns) {
            printf("What the hack!?\n");
        }
        return 0;
    }
    ```
    :::
### [HW10](https://acm.cs.nthu.edu.tw/contest/2182/)
-
    :::spoiler 11291 - Mouse Maze 
    ```c=
    //這題T、N、M 範圍超怪，測資範圍沒那麼大， dfs+剪枝過的了
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    #define oo 1e9
    int t,n,m,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0},d[505][505],ans;
    char c[505][505];
    void dfs(int x,int y){
        if(c[x][y]=='F'){ 
            if(ans==-1 || d[x][y]<ans) ans = d[x][y];
        }
        else{
            REP(i,0,4){
                int nx = x+dx[i], ny = y+dy[i];
                if(0<=nx && nx<n && 0<=ny && ny<m && c[nx][ny]!='#' 
                && d[x][y]+1<d[nx][ny])   //剪枝
                    d[nx][ny] = d[x][y]+1, dfs(nx,ny);
            }
        }
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m), ans = -1;
            REP(i,0,n) scanf("%s",c[i]);
            REP(i,0,n) REP(j,0,m) d[i][j] = oo;
            REP(i,0,n) REP(j,0,m) 
                if(c[i][j]=='S') d[i][j] = 0, dfs(i,j);
            printf("%d\n",ans);
        }
    }
    ```
    ![](https://i.imgur.com/jBThCnC.gif)
    ```c=
    //測資不夠強，否則正確應該用 bfs
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    #define oo 1e9
    int t,n,m,Qx[1000005],Qy[1000005],qf,qe,d[505][505],x,y,dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
    char c[505][505];
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m), qf = qe = 0;             //qf, qe 為queue的頭尾 
            REP(i,0,n) scanf("%s",c[i]);
            REP(i,0,n) REP(j,0,m){
                d[i][j] = oo;                             //最短距離，預設無限大 
                if(c[i][j]=='S') d[i][j] = 0,Qx[qe] = i, Qy[qe] = j, qe++;        //把起點加入queue 起點距離為0 
            }
            while(qf<qe){
                x = Qx[qf], y = Qy[qf], qf++;                 //取出Q頭 Q頭往後 
                if(c[x][y]=='F') break;                       //找到終點 
                REP(i,0,4){
                    int nx = x+dx[i], ny = y+dy[i];           //4方位擴散 
                    if(0<=nx && nx<n && 0<=ny && ny<m && c[nx][ny]!='#' && d[nx][ny]==oo)
                        d[nx][ny] = d[x][y]+1, Qx[qe] = nx, Qy[qe] = ny, qe++;    //新的點就加到queue 新點距離為現在+1     
                }
            }
            printf("%d\n",c[x][y]=='F'?d[x][y]:-1);           //是不是走到終點 
        }
    }
    ```
    ![](https://i.imgur.com/tUonC4Z.gif)
    :::
    :::spoiler 11711 - Dynamic 3D array   
    ```c=
    #define K unsigned
    #define REP(i,j,k) for(int i=j;i<k;i++)
    K*** new_3d_array(K n,K m,K k){
        K*** p1 = (K***)malloc(sizeof(K**)*n+sizeof(K*)*m*n+sizeof(K)*m*n*k);
        K** p2 = (K**)(p1+n);
        K* p3 = (K*)(p1+n+n*m);
        REP(i,0,n){
            p1[i] = &p2[i*m];
            REP(j,0,m) p1[i][j] = &p3[i*m*k+j*k];
        }
        return p1; 
    }
    void delete_3d_array(K ***arr){ free(arr);}
    ```
    :::
    :::spoiler 12490 - Little Brick's Calculator   
    ```c=
    #include<string.h>
    int solver(int **ptr, int *sum, char *s){
        int f = 1,num = 0,n = 0,ok = 0,len=strlen(s);
        for(int i=0;i<=len;i++){
            if('0'<=s[i] && s[i]<='9') num = num*10+s[i]-'0',ok = 1;
            else{
                if(ok) *ptr[n] = f*num, *sum += f*num, n++;
                f = (s[i]=='-')?-1:1, ok = num = 0;
            }
        }
        return n;
    }
    ```
    :::
### [mid2](https://acm.cs.nthu.edu.tw/contest/2183/)
-
    :::spoiler 12073 - character replacement
    ```c=
    int changeCharacter(char *str, char a, char b){
        int len = strlen(str);
        for(int i=0;i<len;i++) if(str[i]==a) str[i] = b;
        return 0;
    }
    ```
    :::
    :::spoiler 12458 - Writing APP
    很難
    ```c=
    #include<stdio.h>
    #define max(a,b) a>b?a:b
    int n,k,dp[1005][1005];           //dp存算過的答案(為了加速)
    char s[1005];
    int f(int l,int r){              //l,r區間最長回文多少
        if(l>r) return 0;
        if(l==r) return dp[l][r] = 1;
        if(dp[l][r]) return dp[l][r];
        if(s[l]==s[r]) return dp[l][r] = 2+f(l+1,r-1);
        return dp[l][r] = max(f(l+1,r),f(l,r-1));
    }
    main(){
        scanf("%d%d%s",&n,&k,s);
        printf(f(0,n-1)>=n-k?"Yes\n":"No\n");
    }
    ```
    :::
    :::spoiler 12510 - Hakka's Maze 
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    int t,n,m,dx[4]={0,0,-1,1},dy[4]={1,-1,0,0},ok;
    char c[1005][1005];
    void dfs(int x,int y){
        if(c[x][y]=='T') ok = 1;
        c[x][y] = 'K';                         //走過就標示，確保每點只會被拜訪一次 
        REP(i,0,4){
            int nx = x+dx[i], ny = y+dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m && c[nx][ny]!='#' && c[nx][ny]!='K') 
                dfs(nx,ny);
        }
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&m), ok = 0;
            REP(i,0,n) scanf("%s",c[i]);
            dfs(0,0);
            if(ok)                              //只要走到一個'T'，所有'T'都能到 
                REP(i,0,n) REP(j,0,m) if(c[i][j]=='T') dfs(i,j);
            printf(c[n-1][m-1]=='K'?"Yes\n":"No\n");
        }
    }
    ```
    :::
    :::spoiler 12519 - The Secrecy between Bob and Alice 
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define swap(a,b) a^=b^=a^=b
    #define MX 5005
    int t,n,ans[MX],num[MX],len,ok;
    char p[MX],s[MX][MX],E[26];
    main(){
        scanf("%d%s",&t,p), len = strlen(p);
        REP(k,0,t){
            scanf("%s",s[k]), ok = 1;
            if(n && !strcmp(s[k],s[ans[n-1]])) num[n-1]++;                      //跟上一個字串一樣並且為答案 
            else if(strlen(s[k])==len){                                         //長度一樣才有可能 
                REP(i,0,26) E[i] = 0;                            
                REP(i,0,len)
                    if(!E[s[k][i]-'a']) E[s[k][i]-'a'] = p[i];
                    else if(E[s[k][i]-'a']!=p[i]) ok = 0;                       //一對多
                REP(i,0,26) REP(j,0,i) if(E[i] && E[i]==E[j]) ok = 0;           //多對一 
                if(ok) ans[n] = k, num[n] = 1, n++;
            } 
        }
        REP(j,0,n) REP(i,0,n-1) if(num[i]<num[i+1])                            //bubble sort注意一樣的別改到順序
            swap(ans[i],ans[i+1]), swap(num[i],num[i+1]);
        printf("%d\n",n);
        REP(i,0,n) printf("%s %d\n",s[ans[i]],num[i]);
    }
    ```
    :::
    :::spoiler 12526 - Split String   
    ```c=
    #define REP(i,j,k) for(int i=j;i<k;++i)
    char **split_str_by_pattern(char* str, char* pattern, int* split_num){
        int n = 520, ls = strlen(str), lp = strlen(pattern), last = 0;
        char** p1 = (char**)malloc(sizeof(char*)*n+sizeof(char)*n*n);
        char* p2 = (char*)(p1+n);
        REP(i,0,n) p1[i] = p2+i*n;
        REP(i,0,ls+1){
            if(strncmp(str+i,pattern,lp)==0 || i==ls){
                if(last<i){
                    REP(j,last,i) p1[*split_num][j-last] = str[j];
                    *split_num = *split_num+1;
                }
                last = i+lp, i = i+lp-1; 
            }
        }
        return p1;
    }
    void free_result(char **result, int split_num){ free(result); }
    ```
    :::
    :::spoiler 12987 - Let's build a hacker script  
    ```c=
    #include <stdio.h>
    #include <string.h>

    char strA[25], strB[25];
    int lenA, lenB;
    int haveAns = 0;
    int out[25];
    void find(int indexA, int indexB) {
        int i, j;
        if (indexA == lenA && indexB == lenB) {
            int printed = 0;
            for (i = j = 0; i < lenB; i++) {
                if (out[j] == -1) {
                    j++;
                    continue;
                }
                if (printed) printf(" ");
                while (j < lenA && out[j] == i) {
                    printf("%c", strA[j]);
                    printed = 1;
                    j++;
                }
            }
            printf("\n");
            haveAns = 1;
        }else if (indexA < lenA && indexB < lenB) {
            if (strB[indexB] == '#') {
                out[indexA] = indexB;
                find(indexA + 1, indexB + 1);
                find(indexA + 1, indexB);
            }else {
                out[indexA] = -1;
                if (strA[indexA] == strB[indexB])
                    find(indexA + 1, indexB + 1);
            }
        }
    }
    int main() {
        scanf("%s %s", strA, strB);
        lenA = strlen(strA);
        lenB = strlen(strB);
        find(0, 0);
        if (!haveAns) {
            printf("What the hack!?\n");
        }
        return 0;
    }
    ```
    :::
    :::spoiler 13000 - Let's build a more powerful hacker script   
    ```c=
    #include<bits/stdc++.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int t,ans,la,lb;
    char a[30],b[30];
    void f(int aa,int bb,int c){
        if(aa==la && bb==lb) ans++;
        else if(b[bb]=='#' && aa<la){
            f(aa+1,bb,0);
            f(aa+1,bb+1,0);
        }
        else if(b[bb]=='$' && aa<la && (!c || c==a[aa])){
            f(aa+1,bb,a[aa]);
            f(aa+1,bb+1,0);
        }
        else if(aa<la && bb<lb && a[aa]==b[bb]) f(aa+1,bb+1,0);
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%s%s",a,b);
            la = strlen(a), lb = strlen(b), ans = 0;
            f(0,0,0);
            printf("%d\n",ans);
        }
    }
    ```
    :::
    :::spoiler 13001 - Bouncing Ball
    ```c=
    ##include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int t,a[3],x[3],d[3],n,cnt,mi;
    main(){
        scanf("%d",&t);
        while(t--){
            REP(i,0,3) scanf("%d",&a[i]);
            REP(i,0,3) scanf("%d",&x[i]);
            REP(i,0,3) scanf("%d",&d[i]);
            scanf("%d",&n);
            REP(i,0,3){
                x[i] = x[i]+(long long)d[i]*n%(2*a[i]);     //走幾步(2a會循環)，小心溢位 
                while(x[i]<0 || x[i]>a[i]){
                    if(x[i]<0) x[i] = -x[i];
                    if(x[i]>0) x[i] = a[i]-(x[i]-a[i]);
                }
            }
            printf("%d %d %d\n",x[0],x[1],x[2]);
        }
    }
    ```
    :::
    
### [HW11](https://acm.cs.nthu.edu.tw/contest/2208/)
-
    :::spoiler 12507 - Searching Remark
    ```c=
    #include<stdio.h>
    #include<string.h>
    char pattern[25],strings[500],*ptr;
    char d[15] = {' ', '\n', '-', '/', ':', '(', ')', '[', ']', ',', '.'};
    int main(){
        int tim=0,i;
        fgets(pattern,25,stdin);
        while(fgets(strings,500,stdin)!=0){
            ptr=strtok(strings,d);
            while(ptr!=NULL){
                if(strlen(ptr)!=strlen(pattern)-1){
                    ptr=strtok(NULL,d);continue;
                }
                for(i=0;i<strlen(pattern)-1;i++) if((ptr[i]-32!=pattern[i])&&(pattern[i]!=ptr[i])&&(ptr[i]+32!=pattern[i])) break;
                if(i==strlen(pattern)-1) tim++;
                ptr=strtok(NULL,d);
            }
        }
        printf("%d\n",tim);
    }
    ```
    :::
    :::spoiler 12523 - Inventory   
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    struct K{
        char name[25];
        int hp, max_hp;
    }p[100];
    int n;
    main(){
        scanf("%d",&n);
        REP(i,0,n) scanf("%s%d%d",p[i].name,&p[i].hp,&p[i].max_hp);
        REP(i,0,n) REP(j,0,i)
            if(p[i].hp!=p[i].max_hp && (p[j].hp==p[j].max_hp || p[j].hp>p[i].hp ||
                p[j].hp==p[i].hp && p[j].max_hp>p[i].max_hp) ||
                p[j].hp==p[j].max_hp && p[j].hp>p[i].hp){ 
                    K c = p[i];
                    p[i] = p[j], p[j] = c;
                }
        REP(i,0,n) printf("%s %d %d\n",p[i].name,p[i].hp,p[i].max_hp);
    }
    ```
    :::
### [HW12](https://acm.cs.nthu.edu.tw/contest/2224/)
-
    :::spoiler 11269 - Text Editor   
    ```c=
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define hui_yuiui(i,j,k) for(int i=j-2;i<k;i++)
    char love[1314];
    int christmas;
    typedef struct node{
        char c;
        struct node *l, *r;
    }Node;                                          
    void add(Node *a, char c){                 	 //把b插入a與a後面的之間 
        Node *b = (Node*)malloc(sizeof(Node));
        b->r = NULL, b->c = c;
        if(a->r!=NULL) b->r = a->r, a->r->l = b;     //將a後面的與b的接起 
        b->l = a, a->r = b;		          //將a與b接起 
    }
    void erase(Node *a){ 
        a->l->r = a->r;                             //將a前面的跟a後面的接起
        if(a->r!=NULL) a->r->l = a->l; 
    }
    main(){
        Node *head = (Node*)malloc(sizeof(Node));    //head 為開頭 
        head->r = NULL, head->l = head;
        Node *lover = head;                          //lover 為游標位置
        fgets(love,1314,stdin), christmas = strlen(love);
        hui_yuiui(i,2,christmas){
            if(love[i]=='/'){                                 
                if(love[i+1]=='b') erase(lover), lover = lover->l, i+=9;
                else if(love[i+1]=='n') add(lover,'\n'), lover = lover->r, i+=7;
                else if(love[i+1]=='l'){ if(lover->l!=NULL) lover = lover->l; i+=4; }
                else if(love[i+1]=='r'){ if(lover->r!=NULL) lover = lover->r; i+=5; }
            }
            else add(lover,love[i]), lover = lover->r;
        }
        head = head->r;
        while(head!=NULL) printf("%c",head->c), head = head->r;
    }
    ```
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define frog_0219(i,j,k) for(int i=j;i<k;i++)
    char love[1314],merry[520];
    int lover,christmas,L[1314],R[520],P;                     //L,R,P 另一種link-list實作法 
    void add(int a, int b, char c){                           //把b插入a與a後面的之間 
        R[b] = R[a], L[R[a]] = b;                             //將a後面的與b的接起 
        L[b] = a, R[a] = b, merry[b] = c;		            //將a與b接起 
    }
    void erase(int a){ R[L[a]] = R[a], L[R[a]] = L[a]; }      //將a前面的跟a後面的接起，a就不見ㄌ 
    main(){
        fgets(love,1314,stdin), christmas = strlen(love);
        frog_0219(i,0,christmas){
            if(love[i]=='/'){                                 //lover 為游標位置 
                if(love[i+1]=='b') erase(lover), lover = L[lover], i+=9;
                else if(love[i+1]=='n') add(lover,++P,'\n'), lover = R[lover], i+=7;
                else if(love[i+1]=='l') lover = L[lover], i+=4;
                else if(love[i+1]=='r') lover = R[lover], i+=5;
            }
            else add(lover,++P,love[i]), lover = R[lover];
        }
        christmas = R[0];
        while(christmas) printf("%c",merry[christmas]), christmas = R[christmas];
    }
    ```
    :::
    :::spoiler 12577 - Bank Data   
    ```c=
    typedef struct _AccountData{
        char* name;
        int money;
    } AccountData;
    AccountData* createData(char* name, int money){
        AccountData* newdata=(AccountData*)malloc(sizeof(AccountData));
        newdata->name=(char*)malloc(strlen(name)*sizeof(char));
        strcpy(newdata->name,name);
        newdata->money=money;
        return newdata;
    }
    AccountData* userQuery(AccountData* data){ return createData(data->name,data->money); }
    ```
    :::
### [HW13](https://acm.cs.nthu.edu.tw/contest/2234/)
-
    :::spoiler 12568 - Reverse Linked List ver 2
    ```c=
    #include"function.h"
    void Push(Node** ptr_head,int x){
        Node *a = (Node*)malloc(sizeof(Node));
        a->data = x, a->next = *ptr_head, *ptr_head = a;
    }
    void Pop(Node** ptr_head){
        if(*ptr_head==NULL) return;
        Node *a = *ptr_head;
        *ptr_head = (*ptr_head)->next;
        free(a);
    }
    void Reverse_List(Node** ptr_head){
        Node *a = NULL;
        while(*ptr_head!=NULL) Push(&a,(*ptr_head)->data), Pop(ptr_head); 
        *ptr_head = a;
    }
    ```
    :::
    :::spoiler 13077 - Ranking System   
    ```c=
    #include"function.h"
    #include <stdlib.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    void Insert(Node** Table, int N, int score, char* name){
        Node *a = (Node*)malloc(sizeof(Node));
        a->name = (char*)malloc(sizeof(char)*101);
        a->score = score, strcpy(a->name,name), Table[N] = a;	
    }
    void Delete(Node** Table, int N, char* name){
        REP(i,0,N) if(strcmp(Table[i]->name,name)==0){
            free(Table[i]->name), free(Table[i]);
            Table[i] = Table[N-1], Table[N-1] = NULL;	     //把最後一個換來中間要刪掉的 
            break;
        }
    }
    int* Top(Node** Table, int N, int x){
        int *a = (int*)malloc(sizeof(int)*x);
        REP(i,0,x) a[i] = -1;
        REP(i,0,N) REP(j,0,x)                   //N個元素依序去找要插入a陣列(存Table的下標，會一直保持由大到小排好的狀態)的哪
          if(a[j]==-1 || Table[i]->score > Table[a[j]]->score ||
          Table[i]->score == Table[a[j]]->score && strcmp(Table[i]->name,Table[a[j]]->name)<0){
            for(int k=x-1;k>j;k--) a[k] = a[k-1];
            a[j] = i;
            break;
        }
        return a;
    }
    ```
    :::
### [final](https://acm.cs.nthu.edu.tw/contest/2235/)
-
    :::spoiler 11490 - The Cat Society
    ```c=
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    #define MX 10005
    int n,m,ans[MX],age[MX],num[MX];
    char name[MX][35],oc[MX][35],p[9] = "enkwamdl";
    int cmp(const void *a,const void *b){
        int i = *(int*)a, j = *(int*)b;
        if(num[i]!=num[j]) return num[i]<num[j]?-1:1;
        if(age[i]!=age[j]){
            if(num[i]==4) return age[i]<age[j]?-1:1;
            return age[i]>age[j]?-1:1;
        }
        return strcmp(name[i],name[j]);
    }
    main(){
        while(~scanf("%d%d",&n,&m)){
            REP(i,0,n){
                scanf("%s%s%d",name[i],oc[i],&age[i]), ans[i] = i;
                REP(j,0,8) if(oc[i][0]==p[j]) num[i] = j;	
            }
            qsort(ans,n,sizeof(int),cmp);
            if(m<n) n=m;                               //爛題敘 
            REP(i,0,n) printf("%s\n",name[ans[i]]);
        }
    }
    ```
    :::
    
    :::spoiler 11773 - Integer pointer array 
    ```c=
    #include"function.h"
    int** malloc_ptr(int array_size){
        int **ptr = (int**)malloc(sizeof(int*)*array_size);
        return ptr;
    }
    void malloc_array(int **array, int array_size){
        *array = (int*)malloc(sizeof(int)*array_size);
    }
    void pointer_ptr_to_array(int *array, int **ptr,int N){
        for(int i=0;i<N;i++) ptr[i] = &array[(i+1)*i/2];
    }
    ```
    :::
    :::spoiler 12568 - Reverse Linked List ver 2
    ```c=
    #include"function.h"
    void Push(Node** ptr_head,int x){
        Node *a = (Node*)malloc(sizeof(Node));
        a->data = x, a->next = *ptr_head, *ptr_head = a;
    }
    void Pop(Node** ptr_head){
        if(*ptr_head==NULL) return;
        Node *a = *ptr_head;
        *ptr_head = (*ptr_head)->next;
        free(a);
    }
    void Reverse_List(Node** ptr_head){
        Node *a = NULL;
        while(*ptr_head!=NULL) Push(&a,(*ptr_head)->data), Pop(ptr_head); 
        *ptr_head = a;
    }
    ```
    :::
    :::spoiler 12582 - Function Pointer Practice 
    ```c=
    #include"function.h"
    #define swap(a,b) a^=b^=a^=b
    void job1(void* argument){
        int l = ((Data*)argument)->lower, r = ((Data*)argument)->upper;
        while(l<r) swap(((Data*)argument)->arr[l],((Data*)argument)->arr[r]), l++, r--;
    }
    void job2(void* argument){
        int l = ((Data*)argument)->lower, r = ((Data*)argument)->upper;
        while(l<=r) ((Data*)argument)->arr[l] *= -1, l++;
    }
    void job3(void* argument){
        int l = ((Data*)argument)->lower, r = ((Data*)argument)->upper;
        while(l<=r) ((Data*)argument)->arr[l] *= 2, l++;
    }
    void initTask(Task* task, void(*func)(void*),void* argument){
        task->func = func, task->argument = argument;
    }
    void executeTasks(Task_List *task_list){
        for(int i=0;i<task_list->size;i++)
            task_list->tasks[i]->func(task_list->tasks[i]->argument);
    }
    ```
    :::
    :::spoiler 12584 - The Beauty of Distributing   
    ```c=
    #include<stdio.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int t,n,ans,a[15],ok,sum,b[15];
    void f(int level,int cnt){                          //一個一個元素取，分入cnt份 
        if(level==n){                                   //元素都取完 
            int f = 1;                                  //確認每份是不是一樣大 
            REP(i,1,cnt) if(b[i]!=b[0]) f = 0;
            if(f) ok = 1;
            return;
        }
        REP(i,0,cnt) if(b[i]+a[level]<=sum/cnt)         //枚舉此元素分入哪一份，一份大小最多sum/cnt
            b[i] += a[level], f(level+1,cnt), b[i] -= a[level];
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%d",&n), ok = sum = 0;
            REP(i,0,n) scanf("%d",&a[i]), sum += a[i];
            for(int i=n;i>=1 && !ok;i--) if(sum%i==0){
                f(0,i);
                if(ok) printf("%d\n",i);
            }
        }
    }
    ```
    :::
    :::spoiler 13077 - Ranking System   
    ```c=
    #include"function.h"
    #include <stdlib.h>
    #define REP(i,j,k) for(int i=j;i<k;i++)
    void Insert(Node** Table, int N, int score, char* name){
        Node *a = (Node*)malloc(sizeof(Node));
        a->name = (char*)malloc(sizeof(char)*101);
        a->score = score, strcpy(a->name,name), Table[N] = a;	
    }
    void Delete(Node** Table, int N, char* name){
        REP(i,0,N) if(strcmp(Table[i]->name,name)==0){
            free(Table[i]->name), free(Table[i]);
            Table[i] = Table[N-1], Table[N-1] = NULL;	     //把最後一個換來中間要刪掉的 
            break;
        }
    }
    int* Top(Node** Table, int N, int x){
        int *a = (int*)malloc(sizeof(int)*x);
        REP(i,0,x) a[i] = -1;
        REP(i,0,N) REP(j,0,x)                   //N個元素依序去找要插入a陣列(存Table的下標，會一直保持由大到小排好的狀態)的哪
          if(a[j]==-1 || Table[i]->score > Table[a[j]]->score ||
          Table[i]->score == Table[a[j]]->score && strcmp(Table[i]->name,Table[a[j]]->name)<0){
            for(int k=x-1;k>j;k--) a[k] = a[k-1];
            a[j] = i;
            break;
        }
        return a;
    }
    ```
    :::
    :::spoiler 13083 - Let's build a Vim editor 
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int len,mod,num,now,end;               
    char s[1314],ans[520];
    main(){
        while(~scanf("%s",&s)){
            len = strlen(s), mod = now = num = end = 0;
            REP(i,0,len-3){
                if(mod){                              //insert mode
                    if(s[i]=='E') mod = 0, now?now--:0, i += 2;
                    else{
                        for(int j=end;j>now;j--) ans[j] = ans[j-1];
                        ans[now++] = s[i], end++;
                    }
                }
                else{                                 //command mode
                    if('0'<=s[i] && s[i]<='9') num = num*10+s[i]-'0';
                    if(s[i]=='h') num?now-=num:now--, num = 0;
                    if(s[i]=='l') num?now+=num:now++, num = 0;
                    if(s[i]=='x'){
                        if(num==0) num = 1;
                        if(end-now<num) num = end-now;
                        REP(j,now,end-num) ans[j] = ans[j+num];
                        end -= num, num = 0;
                    }
                    if(end-1<now) now = end-1;
                    if(now<0) now = 0;
                    if(s[i]=='a') mod = 1, now += (end!=0);
                    if(s[i]=='i') mod = 1;
                    if(s[i]=='A') mod = 1, now = end;
                    if(s[i]=='I') mod = 1, now = 0;
                    //else printf("FKUUU");                 //在command mode也有可能輸入ESC，他整到我了QQ 
                }
            }
            ans[end] = '\0';
            printf("%s\n",ans);
        }
    }
    ```
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    int len,mod,num,L[1314],R[520],P,now,end;                     //L,R,P 另一種link-list實作法 
    char s[1314],ans[520];
    void add(int a, int b, char c){                               //把b插入a與a後面的之間 
        R[b] = R[a], L[R[a]] = b;                                 //將a後面的與b的接起 
        L[b] = a, R[a] = b, ans[b] = c;		                      //將a與b接起 
    }
    void erase(int a){ R[L[a]] = R[a], L[R[a]] = L[a]; } 
    main(){
        while(~scanf("%s",&s)){
            len = strlen(s), mod = num = now = end = P = 0;
            REP(i,0,len) L[i] = R[i] = 0;
            REP(i,0,len-3){
                if(mod){                                          //insert mode
                    if(s[i]=='E') mod = 0, now = (now?L[now]:now), i += 2;
                    else add(now,++P,s[i]), end = (now==end?R[now]:end), now = R[now];
                }
                else{                                             //command mode
                    if(s[i]=='a') mod = 1, now = R[now];
                    else if(s[i]=='i') mod = 1;
                    else if(s[i]=='A') mod = 1, now = end;
                    else if(s[i]=='I') mod = 1, now = 0;
                    else if(s[i]=='h'){
                        if(num==0) num = 1;
                        while(num-- && now) now = L[now];
                        num = 0;
                    }
                    else if(s[i]=='l'){
                        if(num==0) num = 1;
                        while(num-- && R[now]!=end) now = R[now];
                        num = 0;
                    }
                    else if(s[i]=='x'){
                        if(num==0) num = 1;
                        while(num-- && now!=end){
                            erase(R[now]);
                            if(R[now]==0){
                                end = now, now = L[now];
                                break;
                            }
                        }
                        num = 0;
                    }
                    else if('0'<=s[i] && s[i]<='9') num = num*10+s[i]-'0';
                }
            }
            now = R[0];
            while(now) printf("%c",ans[now]), now = R[now];
            printf("\n");
        }
    }
    ```
    :::
    :::spoiler 13086 - Golden Ratio Overheat 
    ```c=
    #include<stdio.h>
    #include<string.h>
    #define REP(i,j,k) for(int i=j;i<k;++i)
    long long t,f[60],n,k;
    char s[2][2005];
    void dfs(long long n,long long k){
        if(n<2) printf("%c\n",s[n][k]);
        else if(k<f[n-2]) dfs(n-2,k);
        else dfs(n-1,k-f[n-2]);
    }
    main(){
        scanf("%d",&t);
        while(t--){
            scanf("%s%s",s[0],s[1]), f[0] = strlen(s[0]), f[1] = strlen(s[1]);
            REP(i,2,60) f[i] = f[i-2]+f[i-1];
            scanf("%lld%lld",&n,&k);
            dfs(n,k);
        }
    }
    ```
    :::
# [Yang-109II](/@24K/Yang-109II)