Yang-109 - HackMD

{%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)