Coloring

题意翻译

Cirno_9baka 的纸条上有 $n$ 个格子，他觉得空白的纸条看着有点无趣，于是想在纸条的格子上涂上 $m$ 种颜色。同时，他认为第 $i$ 种颜色必须要用 $a_i$ 次，且每连续 $k$ 个格子里涂的颜色必须互不相同。 Cirno_9baka 想知道有没有这样的一种涂色方案能符合他的要求。 ### 输入格式 第一行，一个整数 $t$ ( $1 \leq t \leq 10\,000$ ) 表示测试用例的个数。 **对于每组测试用例：** 第一行，输入三个整数 $n$ , $m$ , $k$ ( $1 \leq k \leq n \leq 10^9$ , $1 \leq m \leq 10^5$ , $m \leq n$ )$\\$ 第二行，$m$ 个整数 $a_1,a_2,\cdots,a_m$ ( $1\leq a_i\leq n$ ) 并且保证 $ a_1 + a_2 + \ldots + a_m = n $ 保证每组测试用例中的 $m$ 的和不超过 $10^5$。 ### 输出格式 对于每组测试用例，如果有至少一种涂色的方案，输出"YES"；否则输出"NO"。 输出不区分大小写。 ### 样例提示 第一个测试用例中，没有任何涂色的方案满足所有要求。 第二个测试用例中，可以将纸条涂成$(1,2,1,2,3,4,3,4,5,6,5,6)$，对于每两个连续的格子，颜色都是互不相同的。

题目描述

Cirno\_9baka has a paper tape with $ n $ cells in a row on it. As he thinks that the blank paper tape is too dull, he wants to paint these cells with $ m $ kinds of colors. For some aesthetic reasons, he thinks that the $ i $ -th color must be used exactly $ a_i $ times, and for every $ k $ consecutive cells, their colors have to be distinct. Help Cirno\_9baka to figure out if there is such a way to paint the cells.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10\,000 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains three integers $ n $ , $ m $ , $ k $ ( $ 1 \leq k \leq n \leq 10^9 $ , $ 1 \leq m \leq 10^5 $ , $ m \leq n $ ). Here $ n $ denotes the number of cells, $ m $ denotes the number of colors, and $ k $ means that for every $ k $ consecutive cells, their colors have to be distinct. The second line of each test case contains $ m $ integers $ a_1, a_2, \cdots , a_m $ ( $ 1 \leq a_i \leq n $ ) — the numbers of times that colors have to be used. It's guaranteed that $ a_1 + a_2 + \ldots + a_m = n $ . It is guaranteed that the sum of $ m $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output "YES" if there is at least one possible coloring scheme; otherwise, output "NO". You may print each letter in any case (for example, "YES", "Yes", "yes", and "yEs" will all be recognized as positive answers).

输入输出样例

输入样例 #1

2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2

输出样例 #1

NO
YES

说明

In the first test case, there is no way to color the cells satisfying all the conditions. In the second test case, we can color the cells as follows: $ (1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6) $ . For any $ 2 $ consecutive cells, their colors are distinct.

**题意翻译**

Cirno_9baka有一排共$n$个格子的纸条，他想用$m$种颜色来涂这些格子。出于美学考虑，他认为第$i$种颜色必须恰好使用$a_i$次，且每连续$k$个格子涂的颜色必须互不相同。

请帮助Cirno_9baka判断是否存在这样的涂色方案。

**输入格式**

第一行，一个整数$t$ ($1 \leq t \leq 10,000$) 表示测试用例的个数。

**对于每组测试用例：**

第一行，输入三个整数$n$、$m$、$k$ ($1 \leq k \leq n \leq 10^9$，$1 \leq m \leq 10^5$，$m \leq n$)。

第二行，$m$个整数$a_1,a_2,\cdots,a_m$ ($1 \leq a_i \leq n$) 并且保证 $a_1 + a_2 + \ldots + a_m = n$。

保证每组测试用例中的$m$的和不超过$10^5$。

**输出格式**

对于每组测试用例，如果有至少一种涂色的方案，输出"YES"；否则输出"NO"。

输出不区分大小写。

**样例提示**

第一个测试用例中，没有任何涂色的方案满足所有要求。

第二个测试用例中，可以将纸条涂成$(1,2,1,2,3,4,3,4,5,6,5,6)$，对于每两个连续的格子，颜色都是互不相同的。

---

**题目描述**

Cirno\_9baka has a paper tape with $ n $ cells in a row on it. As he thinks that the blank paper tape is too dull, he wants to paint these cells with $ m $ kinds of colors. For some aesthetic reasons, he thinks that the $ i $ -th color must be used exactly $ a_i $ times, and for every $ k $ consecutive cells, their colors have to be distinct.

Help Cirno\_9baka to figure out if there is such a way to paint the cells.

**输入输出格式**

**输入格式**

第一行包含一个整数 $ t $ ($ 1 \leq t \leq 10,000 $) —— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $ n $、$ m $、$ k $ ($ 1 \leq k \leq n \leq 10^9 $，$ 1 \leq m \leq 10^5 $，$ m \leq n $)。其中 $ n $ 表示格子的数量，$ m $ 表示颜色的数量，$ k $ 表示每 $ k $ 个连续的格子颜色必须不同。

每个测试用例的第二行包含 $ m $ 个整数 $ a_1, a_2, \cdots , a_m $ ($ 1 \leq a_i \leq n $) —— 每种颜色必须使用的次数。保证 $ a_1 + a_2 + \ldots + a_m = n $。

保证所有测试用例中 $ m $ 的总和不超过 $ 10^5 $。

**输出格式**

对于每个测试用例，如果存在至少一种可能的涂色方案，则输出 "YES"；否则输出 "NO"。

您可以以任何大小写形式打印每个字母（例如，"YES"、"Yes"、"yes" 和 "yEs" 都将被识别为肯定答案）。

**输入输出样例**

**输入样例 #1**

```
2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2
```

**输出样例 #1**

```
NO
YES
```

**说明**

在第一个测试用例中，没有一种方法可以满足所有条件的涂色。

在第二个测试用例中，我们可以按以下方式涂色：$ (1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6) $。对于任意两个连续的格子，它们的颜色都是不同的。**题意翻译** Cirno_9baka有一排共$n$个格子的纸条，他想用$m$种颜色来涂这些格子。出于美学考虑，他认为第$i$种颜色必须恰好使用$a_i$次，且每连续$k$个格子涂的颜色必须互不相同。 请帮助Cirno_9baka判断是否存在这样的涂色方案。 **输入格式** 第一行，一个整数$t$ ($1 \leq t \leq 10,000$) 表示测试用例的个数。 **对于每组测试用例：** 第一行，输入三个整数$n$、$m$、$k$ ($1 \leq k \leq n \leq 10^9$，$1 \leq m \leq 10^5$，$m \leq n$)。 第二行，$m$个整数$a_1,a_2,\cdots,a_m$ ($1 \leq a_i \leq n$) 并且保证 $a_1 + a_2 + \ldots + a_m = n$。 保证每组测试用例中的$m$的和不超过$10^5$。 **输出格式** 对于每组测试用例，如果有至少一种涂色的方案，输出"YES"；否则输出"NO"。 输出不区分大小写。 **样例提示** 第一个测试用例中，没有任何涂色的方案满足所有要求。 第二个测试用例中，可以将纸条涂成$(1,2,1,2,3,4,3,4,5,6,5,6)$，对于每两个连续的格子，颜色都是互不相同的。 --- **题目描述** Cirno\_9baka has a paper tape with $ n $ cells in a row on it. As he thinks that the blank paper tape is too dull, he wants to paint these cells with $ m $ kinds of colors. For some aesthetic reasons, he thinks that the $ i $ -th color must be used exactly $ a_i $ times, and for every $ k $ consecutive cells, their colors have to be distinct. Help Cirno\_9baka to figure out if there is such a way to paint the cells. **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ($ 1 \leq t \leq 10,000 $) —— 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含三个整数 $ n $、$ m $、$ k $ ($ 1 \leq k \leq n \leq 10^9 $，$ 1 \leq m \leq 10^5 $，$ m \leq n $)。其中 $ n $ 表示格子的数量，$ m $ 表示颜色的数量，$ k $ 表示每 $ k $ 个连续的格子颜色必须不同。 每个测试用例的第二行包含 $ m $ 个整数 $ a_1, a_2, \cdots , a_m $ ($ 1 \leq a_i \leq n $) —— 每种颜色必须使用的次数。保证 $ a_1 + a_2 + \ldots + a_m = n $。 保证所有测试用例中 $ m $ 的总和不超过 $ 10^5 $。 **输出格式** 对于每个测试用例，如果存在至少一种可能的涂色方案，则输出 "YES"；否则输出 "NO"。 您可以以任何大小写形式打印每个字母（例如，"YES"、"Yes"、"yes" 和 "yEs" 都将被识别为肯定答案）。 **输入输出样例** **输入样例 #1** ``` 2 12 6 2 1 1 1 1 1 7 12 6 2 2 2 2 2 2 2 ``` **输出样例 #1** ``` NO YES ``` **说明** 在第一个测试用例中，没有一种方法可以满足所有条件的涂色。 在第二个测试用例中，我们可以按以下方式涂色：$ (1, 2, 1, 2, 3, 4, 3, 4, 5, 6, 5, 6) $。对于任意两个连续的格子，它们的颜色都是不同的。