2014 Asia - Jakarta Regional Contest

문제 링크

A. Cluster Analysis

$N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다.

$N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include <stdio.h> #include <stdlib.h>   int T, N, K; int A[101], par[101];   int find(int n){ return par[n]==n ? n : (par[n] = find(par[n])); }   int main() {     int ts = 0, i, j;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d", &N, &K);         for (i=1;i<=N;i++) scanf("%d", A+i), par[i] = i;         for (i=1;i<N;i++) for (j=i+1;j<=N;j++) if (abs(A[i]-A[j]) <= K){             int a = find(i), b = find(j);             if (a != b) par[b] = a;         }         int ans = 0;         for (i=1;i<=N;i++) if (find(i) == i) ans++;         printf("%d\n", ans);     } }

B. Body Building

$N$개의 정점과 $M$개의 간선으로 이루어진 무방향성 그래프가 주어진다. 이 그래프에서 하나의 연결 요소를 덤벨로 구분할 수 있다. 덤벨이란, 하나의 손잡이 간선과 간선 양 쪽에 같은 수의 정점으로 구성된 완전 그래프가 있어야한다. 덤벨로 구분할 수 있는 연결 요소의 개수를 구하는 문제다.

편의상 입력으로 주어지는 그래프를 연결 그래프라고 하자. 우선 정점의 수 $N$은 짝수여야한다. $N = 2K$라고 할 때, $N-2$개의 정점의 차수는 $K-1$이어야 하고, 두 정점의 차수는 $K$이어야한다. 이를 통하여 손잡이 간선에 포함된 두 정점을 구할 수 있다. 이를 통해 그래프가 덤벨 모양인지 쉽게 확인할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include <stdio.h> #include <vector> using namespace std;   #define sz(v) ((int)(v).size())   int T, N, M; int w[101][101], deg[101]; bool V[101]; vector <int> list;   void dfs(int n) {     if (V[n]) return;     V[n] = 1; list.push_back(n);     for (int i=1;i<=N;i++) if (w[n][i] && !V[i]) dfs(i); }   int main() {     int ts = 0, i, j, k;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d", &N, &M);         for (i=1;i<=N;i++) V[i] = deg[i] = 0;         for (i=1;i<=N;i++) for (j=1;j<=N;j++) w[i][j] = 0;         for (i=1;i<=M;i++) scanf("%d%d", &j, &k), w[j][k] = w[k][j] = 1, deg[j]++, deg[k]++;         int ans = 0;         for (i=1;i<=N;i++) if (!V[i]){             list.clear(); dfs(i);             int n = sz(list);             if (n&1) continue;             int cnt = 0, a = 0, b = 0, m = (n >> 1);             for (int t: list){                 if (deg[t] == m){                     cnt++;                     b = a, a = t;                 }else if (deg[t] != m-1) cnt = 3;             }             if (cnt != 2) continue;             w[a][b] = 0;             for (int t: list) V[t] = 0;             list.clear(); dfs(a);             if (sz(list) != m){ dfs(b); continue; }             list.clear(); dfs(b);             if (sz(list) != m) continue;             ans++;         }         printf("%d\n", ans);     } }

C. Electric Bike

$N$개의 구간으로 이루어진 자전거 코스가 있다. 전기 자전거를 통해 이 구간 차례대로 모두 지나야한다. 전기 자전거의 동력에 따라 쓰이는 연료량과 얻는 힘이 다르다. $E$ 만큼의 연료가 있고 자전거 동력을 $K$번 바꿀 수 있을 때, $N$개의 구간을 지나기 위한 최소 추가 힘을 구하는 문제다.

D[i][j][k][l] = i번 구간까지 지났고 마지막 동력이 j이고 동력을 k번 바꿨고 사용한 총 연료량이 l일 때, 최소 추가 힘

위와 같이 DP 배열을 잡고 해결하면 된다. 시간복잡도는 $O(NKE)$이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <stdio.h> #include <algorithm> using namespace std;   int T, N, K, E; int A[1001], B[4] = {0, 4, 8, 11}, D[1001][4][11][51];   int main() {     int ts = 0, i, j, k, l;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d%d", &N, &K, &E);         for (i=1;i<=N;i++) scanf("%d", A+i);         for (i=0;i<=N;i++) for (j=0;j<4;j++) for (k=0;k<=K;k++) for (l=0;l<=E;l++) D[i][j][k][l] = 2e9;         D[0][0][0][0] = 0;         for (i=0;i<N;i++) for (j=0;j<4;j++) for (k=0;k<=K;k++) for (l=0;l<=E;l++) if (D[i][j][k][l] < 2e9){             for (int t=0;t<4;t++){                 int nk = k+(j!=t), nl = l+t;                 if (nk > K || nl > E) continue;                 if (D[i+1][t][nk][nl] > D[i][j][k][l]+max(0, A[i+1]-B[t]))                     D[i+1][t][nk][nl] = D[i][j][k][l]+max(0, A[i+1]-B[t]);             }         }         int ans = 2e9;         for (i=0;i<4;i++) for (j=0;j<=K;j++) for (k=0;k<=E;k++)             if (ans > D[N][i][j][k])                 ans = D[N][i][j][k];         printf("%d\n", ans);     } }

D. Kevin's Problem

1부터 $N$까지의 수 $N$개로 이루어진 순열들이 있다. 하나의 순열이 있을 때, 특정 규칙을 통해 수 하나를 선택한다. 이 때 수 $P$가 선택되는 순열의 개수를 구하는 문제다.

D[i][j] = 수열의 마지막 수가 i고, 길이가 j인 증가 수열의 개수 (단, 수열에 $P$는 들어가지 않는다)

위와 같이 DP 배열을 정의하여 문제를 해결할 수 있다.

기본적인 아이디어는 수 $P$가 들어갈 위치를 정하고, $P$ 바로 앞에 오는 수를 정했을 때 경우의 수를 계산하면 된다.

아래와 같이 예외로 생각해주어야하는 경우가 존재한다.

1. $P = N$ 인 경우
2. $K = N-1$ 인 경우
3. $P$가 순열의 마지막에 있는 경우

시간복잡도는 $O(N^2)$이다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <stdio.h>   typedef long long lld;   const int MOD = 1e9 + 7; int T, N, K, P; int D[501][501], F[501];   inline void add(int &t, int v){ t = (t+v)%MOD; }   int main() {     int ts = 0, i, j;     F[0] = 1;     for (i=1;i<501;i++) F[i] = (lld)F[i-1] * i % MOD;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d%d", &N, &K, &P);         D[0][0] = 1;         for (j=1;j<N;j++){             int sum = 0;             for (i=1;i<=N;i++){                 add(sum, D[i-1][j-1]);                 D[i][j] = i == P ? 0 : sum;             }         }         int ans = 0;         if (P == N){             for (i=1;i<N;i++) add(ans, (lld)D[i][N-K] * F[K-1] % MOD);         }else if (K == N-1){             ans = F[K];         }else{             for (i=K+1;i<=N;i++){                 for (j=P+1;j<=N;j++){                     add(ans, (lld)D[j][i-K] * F[N-(i-K+1)] % MOD);                 }             }             for (i=1;i<P;i++){                 add(ans, (lld)D[i][N-K] * F[K-1] % MOD);             }         }         printf("%d\n", ans);     } }

E. Cutting Tree

포레스트(1개 이상의 트리들로 이루어진 그래프)가 주어진다. 그리고 특정 간선을 지우는 질의와 두 정점이 연결되어 있는지 묻는 질의가 주어진다. 질의를 입력으로 주어진 순서대로 처리하는 문제다.

질의가 주어진 역순으로 문제를 뒤집으면, 질의는 간선을 지우는 것이 아니라 간선이 추가되는 질의로 바뀌게 된다. 이제 union-find를 통해 두 정점이 연결되어 있는지 확인할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

#include <stdio.h> #include <vector> using namespace std;   #define MAXN 20004 #define MAXM 5003   int T, N, M; int par[MAXN], P[MAXN], X[MAXN], ord[MAXN];   struct Z{     char c; int a, b; } Q[MAXM];   bool cmp(const int &a, const int &b){ return X[a] > X[b]; }   int find(int n){ return par[n] == n ? n : (par[n] = find(par[n])); }   inline void con(int a, int b) {     if (!a || !b) return;     a = find(a), b = find(b);     if (a == b) return;     par[b] = a; }   int main() {     int ts = 0, i, j, k;     for (scanf("%d", &T);T--;){         printf("Case #%d:\n", ++ts);         scanf("%d%d", &N, &M);         for (i=1;i<=N;i++) scanf("%d", P+i), X[i] = 2e9, ord[i] = par[i] = i;         for (i=1;i<=M;i++){             scanf(" %c%d", &Q[i].c, &Q[i].a);             if (Q[i].c == 'Q') scanf("%d", &Q[i].b);             else if (X[Q[i].a] > i) X[Q[i].a] = i;         }         sort(ord+1, ord+N+1, cmp);         vector <int> ans;         for (i=M,j=1;i;i--){             while (j <= N && X[ord[j]] >= i){                 con(P[ord[j]], ord[j]);                 j++;             }             if (Q[i].c != 'Q') continue;             ans.push_back(find(Q[i].a) == find(Q[i].b));         }         for (i=(int)ans.size();i--;) puts(ans[i] ? "YES" : "NO");     } }

F. Double Swords

$N$ 마리의 용이 있다. 용을 잡으려면 양손에 검을 하나씩 총 두 개의 검이 필요하다. 용 별로 필요한 검 하나는 크기가 정해지고, 나머지 검 하나는 특정 범위를 만족하면 된다. 이 때 모든 용을 잡기 위해 필요한 검의 최소 개수를 구하는 문제다.

편의상 왼손에 쥘 검을 크기가 정해진 검, 오른손에 쥘 검이 범위로 주어진 검이라 하자. 왼손으로 쥘 검의 크기들의 검은 반드시 필요한 검의 크기들이다. 이제 문제는 최소 개수의 검으로 오른손에 쥘 검들을 만들면 된다. 이는 여러 개의 구간들이 있고 모든 구간을 찍기 위해 필요한 점의 최소 개수와 같다. 이는 욕심쟁이기법으로 쉽게 구할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

#include <stdio.h> #include <set> #include <algorithm> using namespace std;   #define MAXN 100005   int T, N, M; int A[MAXN], B[MAXN], C[MAXN];   struct Z{     int s, e;     bool operator < (const Z &ot)const{         return s < ot.s;     } } V[MAXN];   int main() {     int ts = 0, i;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d", &N);         set <int> S;         for (i=1;i<=N;i++) scanf("%d%d%d", A+i, B+i, C+i), S.insert(A[i]);         M = 0;         for (i=1;i<=N;i++){             auto it = S.lower_bound(B[i]);             if (it != S.end()){                 if (*it == A[i]){                     ++it;                     if (it != S.end() && *it <= C[i]) continue;                 }                 else if (*it <= C[i]) continue;             }             V[++M].s = B[i], V[M].e = C[i];         }         sort(V+1, V+M+1);         int mn = 2e9, ans = 0;         for (i=1;i<=M;i++){             if (mn < V[i].s){                 mn = 2e9;                 ans++;             }             if (mn > V[i].e) mn = V[i].e;         }         if (mn < 2e9) ans++;         printf("%d\n", ans+(int)S.size());     } }

G. Prime Switch

$N$개의 전구가 있고, $K$개의 스위치가 있다. 전구는 1번부터 $N$번까지 번호가 매겨져 있다. 스위치에도 번호가 적혀있다. 이 번호들은 서로 다르며 소수(prime number)이다. 이 스위치를 누르면 스위치 번호의 배수가 적힌 전구들의 상태가 뒤집힌다. 이 때, 스위치를 적절히 눌러 켜져있는 전구의 개수를 최대화 하는 문제다.

$\sqrt{N}$보다 같거나 작은 번호를 가진 스위치는 많아야 11개다. 이 들에 대해 $2^{11}$가지의 경우에 대해 모두 처리하고 각 경우마다 $\sqrt{N}$보다 번호가 큰 스위치들에 대해서는 서로 독립이므로 욕심쟁이기법을 통해 전구의 개수를 최대화 할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include <stdio.h> #include <algorithm> using namespace std;   #define MAXN 1004 #define bit(n) (1<<((n)-1))   int T, N, M, K, R; int A[MAXN]; bool V[MAXN];   int main() {     int ts = 0, i, j;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d", &N, &K);         for (i=1;i<=K;i++) scanf("%d", A+i);         sort(A+1, A+K+1);         for (R=1;R*R<=N;R++); R--;         for (i=1;i<=K;i++) if (A[i] <= R) M = i;         int ans = 0;         for (int msk=0;msk<(1<<M);msk++){             for (i=1;i<=N;i++) V[i] = 0;             for (i=1;i<=M;i++) if (msk&bit(i)){                 for (j=A[i];j<=N;j+=A[i]) V[j] ^= 1;             }             for (i=M+1;i<=K;i++){                 int cnt = 0;                 for (j=A[i];j<=N;j+=A[i]){                     if (V[j]) cnt--;                     else cnt++;                 }                 if (cnt > 0){                     for (j=A[i];j<=N;j+=A[i]) V[j] ^= 1;                 }             }             int cnt = 0;             for (i=1;i<=N;i++) if (V[i]) cnt++;             if (ans < cnt) ans = cnt;         }         printf("%d\n", ans);     } }

H. I Want That Cake

A팀과 B팀에 각각 $N$명씩 사람이 있다. $M$개의 팬케잌이 있고, 한 사람이 한 개에서 $K$개의 팬케잌을 먹을 수 있다. 마지막 펜케잌을 먹는 사람이 속한 팀이 이기는 게임을 한다. 다만 두 팀이 번갈아가면서 진행하지 않고 미리 순서를 정해둔다. 두 팀에 속한 각 선수들이 최선을 다할 때 어느 팀이 이기는지 구하는 문제다.

D[i][j] = i번째 사람의 차례고, 남은 팬케잌의 개수가 j일 때 i번째 사람이 이기면 1, 지면 0

위와 같이 DP 배열을 정의한다.

i번째 사람과 i+1번째 사람이 같은 팀에 속한 경우와 그렇지 않은 경우에 따라 점화식이 달라지게 된다.

쉽게 생각하면 $O(NMK)$의 시간복잡도를 보이는데, 점화식의 특성을 잘 이용하면 $O(NM)$에 해결할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include <stdio.h>   #define MAXN 2004   int T, N, M, K, L; int D[MAXN][MAXN]; char S[MAXN];   int main() {     int ts = 0, i, j;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d%d%s", &N, &M, &K, S+1); L = (N << 1);         for (i=1;i<=L;i++){             D[i][0] = 0;             for (j=1;j<=M;j++) D[i][j] = j <= K ? 1 : -1;         }         for (i=L;--i;){             int p = 0, q = 0, zero = 0, one = 0;             for (j=K+1;j<=M-i+1;j++){                 while (q <= j-1){                     if (D[i+1][q]) one++;                     else zero++;                     q++;                 }                 while (p < j-K){                     if (D[i+1][p]) one--;                     else zero--;                     p++;                 }                 D[i][j] = 0;                 if (S[i] == S[i+1]){                     if (one) D[i][j] = 1;                 }else{                     if (zero) D[i][j] = 1;                 }             }         }         printf("%c\n", D[1][M] ? S[1] : ('A'+'B'-S[1]));     } }

I. Maze Mayhem

$N \times M$ 크기의 미로가 있다. 이 미로에서는 오른쪽과 아래 방향으로만 이동할 수 있다. 미로의 시작점은 왼쪽-위 점이고, 도착점은 오른쪽-아래 점이다. 이제 $K$개 이하의 장애물을 설치해서 시작점에서 도착점으로 가지 못하게 해야 한다. 가능한 경우의 수를 구하는 문제다.

D[i][j][k][l] = i번 이동했고, 도달가능한 상황이 j이고, 설치한 장애물의 개수가 k이고, l번까지 장애물을 설치했을 때 경우의 수

위와 같이 DP 배열을 정의한다.

도달 가능한 상황이라 함은 i번 이동했을 때 도달 가능한 위치가 최대 $N$가지이다. 그러므로 가능한 상황의 수는 $2^N$가지이므로 길이가 $N$인 이진수로 나타낼 수 있다.

장애물을 l번 줄까지 놓았다는 것은 가능한 $N$개의 상황 중 l번까지 장애물을 설치했음을 의미한다. 중복으로 경우를 세는 경우에 대비하기 위해 필요하다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <stdio.h>   #define bit(n) (1<<(n))   const int MOD = 1e9 + 7; int T, N, M, K; int D[16][1<<8][65][9];   inline void add(int &t, int v){ t = (t+v)%MOD; }   int main() {     int ts = 0, i, j, k, l;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d%d", &N, &M, &K);         for (i=0;i<N+M-1;i++) for (j=0;j<bit(N);j++) for (k=0;k<=K;k++) for (l=0;l<=N;l++) D[i][j][k][l] = 0;         D[0][1][0][0] = 1;         for (i=0;i<N+M-1;i++) for (l=0;l<=N;l++) for (j=0;j<bit(N);j++) for (k=0;k<=K;k++) if (D[i][j][k][l]){             if (k < K && l < N && i-l >= 0 && i-l < M){                 int t = j & bit(l) ? j ^ bit(l) : j;                 add(D[i][t][k+1][l+1] , D[i][j][k][l]);             }             if (l < N) add(D[i][j][k][l+1], D[i][j][k][l]);             if (i == N+M-2 || l < N) continue;             int nxt = 0;             for (int y=0;y<N;y++) if (j & bit(y)){                 int x = i-y;                 if (x+1 < M) nxt |= bit(y);                 if (y+1 < N) nxt |= bit(y+1);             }             add(D[i+1][nxt][k][0], D[i][j][k][l]);         }         int ans = 0;         for (k=0;k<=K;k++) add(ans, D[N+M-2][0][k][N]);         printf("%d\n", ans);     } }

J. Leveling Ground

길이가 $N$인 산 모양이 주어진다. 길이가 $M$인 구간을 공사해야한다. 공사는 구간에 속한 가장 낮은 높이에 맞춰 구간안에 있는 모든 땅을 판다. 이 때 비용은 파는 땅의 단면의 면적과 같다. 문제에 있는 그림에서 점('.') 하나는 비용이 1이며, 경사 ('/')는 비용이 0.5다. 이 때 공사 가능한 여러 구간들 중 최소 비용으로 공사할 수 있는 구간의 비용을 구하는 문제다.

길이가 $M$인 각 구간에 대해서 구간 내의 높이(점의 개수)의 합과 경사의 개수, 그리고 최소 높이를 알면 그 구간에 대한 공사 비용을 구할 수 있다. 이는 deque(Double-Ended Queue)와 같은 자료구조를 통해 구현할 수 있다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

#include <stdio.h> #include <deque> using namespace std;   #define MAXN 1000006 typedef long long lld;   int T, N, M; int H[MAXN]; char A[MAXN];   int main() {     int ts = 0, i, j;     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d%s", &N, &M, A+1);         int h = 0;         for (i=1;i<=N;i++){             if (A[i] == '/') H[i] = h++;             else if (A[i] == '_') H[i] = h;             else H[i] = --h;         }         lld sum = 0; int slope = 0;         deque <int> dq;         lld ans = 1e18;         for (i=j=1;i<=N;i++){             while (j <= i-M){                 sum -= H[j];                 if (A[j] != '_') slope--;                 j++;             }             sum += H[i]; if (A[i] != '_') slope++;             while (!dq.empty() && H[dq.back()] >= H[i]) dq.pop_back();             dq.push_back(i);             while (dq.front() <= i-M) dq.pop_front();             if (i < M) continue;             lld p = sum - (lld)H[dq.front()] * M, v = p + p + slope;             if (ans > v) ans = v;         }         printf("%lld.%d\n", ans>>1, (int)(ans&1)*5);     } }

K. Punching Robot

$N \times M$ 크기의 미로가 있다. 이 미로에서는 오른쪽과 아래 방향으로만 이동할 수 있다. 미로의 시작점은 왼쪽-위 점이고, 도착점은 오른쪽-아래 점이다. 미로 위에 $K$개의 장애물이 있는데 장애물들은 $1 \times 1$ 크기가 아닌 $3 \times 3$ 크기다. 장애물을 지나지 않고 시작점에서 도착점으로 가는 경로의 개수를 구하는 문제다.

$3 \times 3$ 크기의 장애물 하나를 $1 \times 1$ 크기의 장애물 9개로 바꾸고 문제를 생각한다. 그러면 총 90개의 장애물이 있을 수 있다. 이제 DP 배열을 아래와 같이 정의한다.

D[i] = 시작점에서 출발하여 장애물 i까지 장애물을 하나도 거치지 않고 가는 경우의 수

자세한 점화식은 생략한다.

문제에서 제일 중요한 것은 ${n}\choose{k}$를 $\mod 997$안에서 빠르게 구해야한다. 이는 뤼카의 정리를 이용하여 $\log {n+k}$ 시간안에 구할 수 있다. 일반적으로 생각할 수 있는 방법으로 구하면 $997!$이 997의 배수가 되어버려서 Modulo Inverse를 제대로 구할 수 없다.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

#include <stdio.h> #include <vector> #include <algorithm> using namespace std;   #define all(v) (v).begin(), (v).end()   const int MOD = 997; int T, N, M, K; int C[MOD][MOD], D[99];   struct Z{     Z(int y=0, int x=0): y(y), x(x) {}     int y, x;     bool operator < (const Z &ot)const{         return y != ot.y ? y < ot.y : x < ot.x;     }     bool operator == (const Z &ot)const{         return y == ot.y && x == ot.x;     } };   int choose(int n, int k) {     int ret = 1;     for (;n;n/=MOD, k/=MOD){         int p = n % MOD, q = k % MOD;         ret = ret * C[p][q] % MOD;     }     return ret; }   inline int count(int y, int x){ return choose(y+x, x); }   int main() {     int ts = 0, i, j, k;     C[0][0] = 1;     for (i=1;i<MOD;i++){         C[i][0] = 1;         for (j=1;j<=i;j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;     }     for (scanf("%d", &T);T--;){         printf("Case #%d: ", ++ts);         scanf("%d%d%d", &N, &M, &K);         vector <Z> A;         for (i=1;i<=K;i++){             scanf("%d%d", &j, &k);             for (int y=j-1;y<j+2;y++)                 for (int x=k-1;x<k+2;x++)                     A.emplace_back(y, x);         }         A.emplace_back(N, M);         sort(all(A));         A.erase(unique(all(A)), A.end());         K = (int)A.size();         for (i=0;i<K;i++){             D[i] = count(A[i].y-1, A[i].x-1);             for (j=0;j<i;j++) if (A[j].x <= A[i].x){                 D[i] -= D[j] * count(A[i].y-A[j].y, A[i].x-A[j].x) % MOD;                 if (D[i] < 0) D[i] += MOD;             }         }         printf("%d\n", D[K-1]);     } }