309818: CF1740D. Knowledge Cards
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Knowledge Cards
题意翻译
### 题目大意 对于一个 $n \times m$ 的棋盘，左上角为 $(1,\;1)$，右下角为 $(n,\;m)$。$(1,\;1)$ 和 $(n,\;m)$ 上分别有一个栈。最开始的时候$(1,\;1)$ 格子上的栈里有 $k$ 张牌，**从栈顶到栈底**的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。你需要对这些牌做若干次操作将所有牌移到 $(n,\;m)$ 格子的栈中，使得最后 $(n,\;m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$，每次给你棋盘长宽 $n \times m$ 和初始的 $a$ 数组，请问是否有解。 我们定义一次操作的规则如下： 1. 一次只能操作一张牌； 2. 一张牌只能向相邻的**四联通**格子（有共边）里移动； 3. **除了** $(1,\;1)$ 和 $(n,\;m)$ 以外的格子内不能拥有超过一张牌； 4. 如果你当前**操作**的格子是 $(1,\;1)$，那么你只能从他的**栈顶**取走一张牌，且你**不能**将一张牌移到他上面； 5. 如果你当前操作的**目标**格子是 $(n,\;m)$，那么你只能将一张牌移动到他的**栈顶**，且你不能从他上面移走任何一张牌。 ### 输入格式 第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。 对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。 接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$ ，意义见题目大意。 数据保证 $\sum n \cdot m \leqslant 10^6,\sum k \leqslant 10^5$。 ### 输出格式 对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。（数据不区分大小写） $Translated \; by \; Zigh$题目描述
Pak Chanek, a renowned scholar, invented a card puzzle using his knowledge. In the puzzle, you are given a board with $ n $ rows and $ m $ columns. Let $ (r, c) $ represent the cell in the $ r $ -th row and the $ c $ -th column. Initially, there are $ k $ cards stacked in cell $ (1, 1) $ . Each card has an integer from $ 1 $ to $ k $ written on it. More specifically, the $ i $ -th card from the top of the stack in cell $ (1, 1) $ has the number $ a_i $ written on it. It is known that no two cards have the same number written on them. In other words, the numbers written on the cards are a permutation of integers from $ 1 $ to $ k $ . All other cells are empty. You need to move the $ k $ cards to cell $ (n, m) $ to create another stack of cards. Let $ b_i $ be the number written on the $ i $ -th card from the top of the stack in cell $ (n, m) $ . You should create the stack in cell $ (n, m) $ in such a way so that $ b_i = i $ for all $ 1 \leq i \leq k $ . In one move, you can remove the top card from a cell and place it onto an adjacent cell (a cell that shares a common side). If the target cell already contains one or more cards, you place your card on the top of the stack. You must do each operation while satisfying the following restrictions: - Each cell other than $ (1,1) $ and $ (n,m) $ must not have more than one card on it. - You cannot move a card onto cell $ (1,1) $ . - You cannot move a card from cell $ (n,m) $ . Given the values of $ n $ , $ m $ , $ k $ and the array $ a $ , determine if the puzzle is solvable.输入输出格式
输入格式
Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 2 \cdot 10^4 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains three integers $ n $ , $ m $ , and $ k $ ( $ 3 \leq n, m \leq 10^6 $ , $ nm \leq 10^6 $ , $ 1 \leq k \leq 10^5 $ ) — the size of the board and the number of cards. The second line of the test case contains $ k $ integers $ a_1, a_2, \ldots, a_k $ — the array $ a $ , representing the numbers written on the cards. The values of $ a $ are a permutation of integers from $ 1 $ to $ k $ . It is guaranteed that the sum of $ nm $ and $ k $ over all test cases do not exceed $ 10^6 $ and $ 10^5 $ respectively.
输出格式
For each test case, output "YA" (without quotes) if it is possible and "TIDAK" (without quotes) otherwise, which mean yes and no in Indonesian respectively. You can output "YA" and "TIDAK" in any case (for example, strings "tiDAk", "tidak", and "Tidak" will be recognised as a negative response).
输入输出样例
输入样例 #1
4
3 3 6
3 6 4 1 2 5
3 3 10
1 2 3 4 5 6 7 8 9 10
5 4 4
2 1 3 4
3 4 10
10 4 9 3 5 6 8 2 7 1输出样例 #1
YA
TIDAK
YA
YA说明
In the first test case, the following is one way the puzzle can be done: - Move the card with $ 3 $ written on it from cell $ (1, 1) $ to cell $ (1, 2) $ , then cell $ (1, 3) $ . - Move the card with $ 6 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (3, 1) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ . - Move the card with $ 4 $ written on it from cell $ (1, 1) $ to cell $ (1, 2) $ . - Move the card with $ 1 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (2, 2) $ , then cell $ (2, 3) $ . - Move the card with $ 2 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (2, 2) $ . - Move the card with $ 5 $ written on it from cell $ (1, 1) $ to cell $ (2, 1) $ , then cell $ (3, 1) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ . - Move the card with $ 2 $ written on it from cell $ (2, 2) $ to cell $ (2, 1) $ . - Move the card with $ 4 $ written on it from cell $ (1, 2) $ to cell $ (2, 2) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ . - Move the card with $ 3 $ written on it from cell $ (1, 3) $ to cell $ (1, 2) $ , then cell $ (2, 2) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ . - Move the card with $ 2 $ written on it from cell $ (2, 1) $ to cell $ (3, 1) $ , then cell $ (3, 2) $ , then cell $ (3, 3) $ . - Move the card with $ 1 $ written on it from cell $ (2, 3) $ to cell $ (3, 3) $ . An animated illustration regarding the process mentioned above is as follows: Input
题意翻译
### 题目大意 对于一个 $n \times m$ 的棋盘，左上角为 $(1,\;1)$，右下角为 $(n,\;m)$。$(1,\;1)$ 和 $(n,\;m)$ 上分别有一个栈。最开始的时候$(1,\;1)$ 格子上的栈里有 $k$ 张牌，**从栈顶到栈底**的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。你需要对这些牌做若干次操作将所有牌移到 $(n,\;m)$ 格子的栈中，使得最后 $(n,\;m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$，每次给你棋盘长宽 $n \times m$ 和初始的 $a$ 数组，请问是否有解。 我们定义一次操作的规则如下： 1. 一次只能操作一张牌； 2. 一张牌只能向相邻的**四联通**格子（有共边）里移动； 3. **除了** $(1,\;1)$ 和 $(n,\;m)$ 以外的格子内不能拥有超过一张牌； 4. 如果你当前**操作**的格子是 $(1,\;1)$，那么你只能从他的**栈顶**取走一张牌，且你**不能**将一张牌移到他上面； 5. 如果你当前操作的**目标**格子是 $(n,\;m)$，那么你只能将一张牌移动到他的**栈顶**，且你不能从他上面移走任何一张牌。 ### 输入格式 第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。 对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。 接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$ ，意义见题目大意。 数据保证 $\sum n \cdot m \leqslant 10^6,\sum k \leqslant 10^5$。 ### 输出格式 对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。（数据不区分大小写） $Translated \; by \; Zigh$Output
**题目大意**
有一个 $n \times m$ 的棋盘，左上角为 $(1,1)$，右下角为 $(n,m)$。$(1,1)$ 和 $(n,m)$ 上分别有一个栈。最开始的时候 $(1,1)$ 格子上的栈里有 $k$ 张牌，从栈顶到栈底的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。需要做若干次操作将所有牌移到 $(n,m)$ 格子的栈中，使得最后 $(n,m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$。每次给定的棋盘长宽 $n \times m$ 和初始的 $a$ 数组，要求判断是否有解。
操作规则如下：
1. 一次只能操作一张牌；
2. 一张牌只能向相邻的四联通格子（有共边）里移动；
3. 除了 $(1,1)$ 和 $(n,m)$ 以外的格子内不能拥有超过一张牌；
4. 如果当前操作的格子是 $(1,1)$，只能从栈顶取走一张牌，不能将牌移到它上面；
5. 如果当前操作的目标格子是 $(n,m)$，只能将牌移动到栈顶，不能从它上面移走牌。
**输入格式**
第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。
对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。
接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$，意义见题目大意。
数据保证 $\sum n \cdot m \leqslant 10^6,\;\sum k \leqslant 10^5$。
**输出格式**
对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。**题目大意** 有一个 $n \times m$ 的棋盘，左上角为 $(1,1)$，右下角为 $(n,m)$。$(1,1)$ 和 $(n,m)$ 上分别有一个栈。最开始的时候 $(1,1)$ 格子上的栈里有 $k$ 张牌，从栈顶到栈底的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。需要做若干次操作将所有牌移到 $(n,m)$ 格子的栈中，使得最后 $(n,m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$。每次给定的棋盘长宽 $n \times m$ 和初始的 $a$ 数组，要求判断是否有解。 操作规则如下： 1. 一次只能操作一张牌； 2. 一张牌只能向相邻的四联通格子（有共边）里移动； 3. 除了 $(1,1)$ 和 $(n,m)$ 以外的格子内不能拥有超过一张牌； 4. 如果当前操作的格子是 $(1,1)$，只能从栈顶取走一张牌，不能将牌移到它上面； 5. 如果当前操作的目标格子是 $(n,m)$，只能将牌移动到栈顶，不能从它上面移走牌。 **输入格式** 第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。 对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。 接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$，意义见题目大意。 数据保证 $\sum n \cdot m \leqslant 10^6,\;\sum k \leqslant 10^5$。 **输出格式** 对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。
有一个 $n \times m$ 的棋盘，左上角为 $(1,1)$，右下角为 $(n,m)$。$(1,1)$ 和 $(n,m)$ 上分别有一个栈。最开始的时候 $(1,1)$ 格子上的栈里有 $k$ 张牌，从栈顶到栈底的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。需要做若干次操作将所有牌移到 $(n,m)$ 格子的栈中，使得最后 $(n,m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$。每次给定的棋盘长宽 $n \times m$ 和初始的 $a$ 数组，要求判断是否有解。
操作规则如下：
1. 一次只能操作一张牌；
2. 一张牌只能向相邻的四联通格子（有共边）里移动；
3. 除了 $(1,1)$ 和 $(n,m)$ 以外的格子内不能拥有超过一张牌；
4. 如果当前操作的格子是 $(1,1)$，只能从栈顶取走一张牌，不能将牌移到它上面；
5. 如果当前操作的目标格子是 $(n,m)$，只能将牌移动到栈顶，不能从它上面移走牌。
**输入格式**
第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。
对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。
接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$，意义见题目大意。
数据保证 $\sum n \cdot m \leqslant 10^6,\;\sum k \leqslant 10^5$。
**输出格式**
对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。**题目大意** 有一个 $n \times m$ 的棋盘，左上角为 $(1,1)$，右下角为 $(n,m)$。$(1,1)$ 和 $(n,m)$ 上分别有一个栈。最开始的时候 $(1,1)$ 格子上的栈里有 $k$ 张牌，从栈顶到栈底的第 $i$ 张牌上有一个数 $a_i$，保证 $a$ 数组是一个 $k$ 的全排列。需要做若干次操作将所有牌移到 $(n,m)$ 格子的栈中，使得最后 $(n,m)$ 格子的栈中从上到下牌上的序号依次为 $1 \sim k$。每次给定的棋盘长宽 $n \times m$ 和初始的 $a$ 数组，要求判断是否有解。 操作规则如下： 1. 一次只能操作一张牌； 2. 一张牌只能向相邻的四联通格子（有共边）里移动； 3. 除了 $(1,1)$ 和 $(n,m)$ 以外的格子内不能拥有超过一张牌； 4. 如果当前操作的格子是 $(1,1)$，只能从栈顶取走一张牌，不能将牌移到它上面； 5. 如果当前操作的目标格子是 $(n,m)$，只能将牌移动到栈顶，不能从它上面移走牌。 **输入格式** 第一行一个整数 $T\;(1 \leqslant T \leqslant 2\cdot10^4)$ 表示测试样例数。 对于每一组测试样例，第一行三个整数 $n,\;m,\;k\;(3 \leqslant n,m \leqslant 10^6,\;n \cdot m \leqslant 10^6,\;1 \leqslant k \leqslant 10^5)$，分别表示棋盘大小和初始牌数。 接下来的一行 $k$ 个整数，表示 $a_1 \sim a_k$，意义见题目大意。 数据保证 $\sum n \cdot m \leqslant 10^6,\;\sum k \leqslant 10^5$。 **输出格式** 对于每一组输出样例输出包含一行，如果有解则输出 "YA"（不包含引号），否则输出 "TIDAK"（不包含引号）。