309918: CF1759F. All Possible Digits
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
All Possible Digits
题意翻译
多组数据： 给你一个 $n$ 位的 $p$ 进制数，第 $i$ 位为 $a_i$。 每次操作可以让该数加 $1$，请问最少要操作多少次，可以让数码 $0,...,p-1$ 都出现过（包含在中间过程出现）。题目描述
A positive number $ x $ of length $ n $ in base $ p $ ( $ 2 \le p \le 10^9 $ ) is written on the blackboard. The number $ x $ is given as a sequence $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i < p $ ) — the digits of $ x $ in order from left to right (most significant to least significant). Dmitry is very fond of all the digits of this number system, so he wants to see each of them at least once. In one operation, he can: - take any number $ x $ written on the board, increase it by $ 1 $ , and write the new value $ x + 1 $ on the board. For example, $ p=5 $ and $ x=234_5 $ . - Initially, the board contains the digits $ 2 $ , $ 3 $ and $ 4 $ ; - Dmitry increases the number $ 234_5 $ by $ 1 $ and writes down the number $ 240_5 $ . On the board there are digits $ 0, 2, 3, 4 $ ; - Dmitry increases the number $ 240_5 $ by $ 1 $ and writes down the number $ 241_5 $ . Now the board contains all the digits from $ 0 $ to $ 4 $ . Your task is to determine the minimum number of operations required to make all the digits from $ 0 $ to $ p-1 $ appear on the board at least once.输入输出格式
输入格式
The first line of the input contains a single integer $ t $ ( $ 1 \le t \le 2 \cdot 10^3 $ ) — the number of test cases. The descriptions of the input test cases follow. The first line of description of each test case contains two integers $ n $ ( $ 1 \le n \le 100 $ ) and $ p $ ( $ 2 \le p \le 10^9 $ ) — the length of the number and the base of the number system. The second line of the description of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i < p $ ) — digits of $ x $ in number system with base $ p $ It is guaranteed that the number $ x $ does not contain leading zeros (that is, $ a_1>0 $ ).
输出格式
For each test case print a single integer — the minimum number of operations required for Dmitry to get all the digits on the board from $ 0 $ to $ p-1 $ . It can be shown that this always requires a finite number of operations.
输入输出样例
输入样例 #1
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1输出样例 #1
1
1
0
0
7
995
2
1
1
1
2Input
题意翻译
多组数据： 给你一个 $n$ 位的 $p$ 进制数，第 $i$ 位为 $a_i$。 每次操作可以让该数加 $1$，请问最少要操作多少次，可以让数码 $0,...,p-1$ 都出现过（包含在中间过程出现）。Output
**题意翻译**
- 题目：所有可能的数码
- 数据组数：多组
- 描述：给定一个 $n$ 位的 $p$ 进制数，第 $i$ 位为 $a_i$。
- 操作：每次操作可以将这个数加 $1$。
- 目标：求最少操作多少次，使得数码 $0, ..., p-1$ 都至少出现过一次（包含在中间过程中出现）。
**题目描述**
- 题目：所有可能的数码
- 描述：黑板上写着一个正数 $x$，它是一个 $n$ 位的 $p$ 进制数（$2 \le p \le 10^9$），表示为序列 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）—— $x$ 的数码从左到右（从最高位到最低位）排列。
- 目标：Dmitry 非常喜欢这个数制的所有数码，他想要看到每一个数码至少出现一次。
- 操作：每次操作可以将黑板上的数 $x$ 增加 $1$。
- 任务：确定要使所有数码从 $0$ 到 $p-1$ 至少在黑板上出现一次所需的最少操作次数。
**输入输出格式**
- 输入格式：
- 第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^3$）——测试用例的数量。接下来是每个测试用例的描述。
- 每个测试用例的描述第一行包含两个整数 $n$（$1 \le n \le 100$）和 $p$（$2 \le p \le 10^9$）——数字的长度和数制的基础。
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）——基于 $p$ 进制的 $x$ 的数码。
- 保证数字 $x$ 不包含前导零（即 $a_1 > 0$）。
- 输出格式：
- 对于每个测试用例，打印一个整数——Dmitry 获得所有数码从 $0$ 到 $p-1$ 所需的最少操作次数。
- 可以证明，这总是需要有限次的操作。
**输入输出样例**
- 输入样例 #1：
```
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
```
- 输出样例 #1：
```
1
1
0
0
7
995
2
1
1
1
2
```**题意翻译** - 题目：所有可能的数码 - 数据组数：多组 - 描述：给定一个 $n$ 位的 $p$ 进制数，第 $i$ 位为 $a_i$。 - 操作：每次操作可以将这个数加 $1$。 - 目标：求最少操作多少次，使得数码 $0, ..., p-1$ 都至少出现过一次（包含在中间过程中出现）。 **题目描述** - 题目：所有可能的数码 - 描述：黑板上写着一个正数 $x$，它是一个 $n$ 位的 $p$ 进制数（$2 \le p \le 10^9$），表示为序列 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）—— $x$ 的数码从左到右（从最高位到最低位）排列。 - 目标：Dmitry 非常喜欢这个数制的所有数码，他想要看到每一个数码至少出现一次。 - 操作：每次操作可以将黑板上的数 $x$ 增加 $1$。 - 任务：确定要使所有数码从 $0$ 到 $p-1$ 至少在黑板上出现一次所需的最少操作次数。 **输入输出格式** - 输入格式： - 第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^3$）——测试用例的数量。接下来是每个测试用例的描述。 - 每个测试用例的描述第一行包含两个整数 $n$（$1 \le n \le 100$）和 $p$（$2 \le p \le 10^9$）——数字的长度和数制的基础。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）——基于 $p$ 进制的 $x$ 的数码。 - 保证数字 $x$ 不包含前导零（即 $a_1 > 0$）。 - 输出格式： - 对于每个测试用例，打印一个整数——Dmitry 获得所有数码从 $0$ 到 $p-1$ 所需的最少操作次数。 - 可以证明，这总是需要有限次的操作。 **输入输出样例** - 输入样例 #1： ``` 11 2 3 1 2 4 2 1 1 1 1 6 6 1 2 3 4 5 0 5 2 1 0 1 0 1 3 10 1 2 3 5 1000 4 1 3 2 5 3 5 2 3 4 4 4 3 2 3 0 1 3 2 5 5 1 2 2 2 4 3 4 1 0 1 ``` - 输出样例 #1： ``` 1 1 0 0 7 995 2 1 1 1 2 ```
- 题目：所有可能的数码
- 数据组数：多组
- 描述：给定一个 $n$ 位的 $p$ 进制数，第 $i$ 位为 $a_i$。
- 操作：每次操作可以将这个数加 $1$。
- 目标：求最少操作多少次，使得数码 $0, ..., p-1$ 都至少出现过一次（包含在中间过程中出现）。
**题目描述**
- 题目：所有可能的数码
- 描述：黑板上写着一个正数 $x$，它是一个 $n$ 位的 $p$ 进制数（$2 \le p \le 10^9$），表示为序列 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）—— $x$ 的数码从左到右（从最高位到最低位）排列。
- 目标：Dmitry 非常喜欢这个数制的所有数码，他想要看到每一个数码至少出现一次。
- 操作：每次操作可以将黑板上的数 $x$ 增加 $1$。
- 任务：确定要使所有数码从 $0$ 到 $p-1$ 至少在黑板上出现一次所需的最少操作次数。
**输入输出格式**
- 输入格式：
- 第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^3$）——测试用例的数量。接下来是每个测试用例的描述。
- 每个测试用例的描述第一行包含两个整数 $n$（$1 \le n \le 100$）和 $p$（$2 \le p \le 10^9$）——数字的长度和数制的基础。
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）——基于 $p$ 进制的 $x$ 的数码。
- 保证数字 $x$ 不包含前导零（即 $a_1 > 0$）。
- 输出格式：
- 对于每个测试用例，打印一个整数——Dmitry 获得所有数码从 $0$ 到 $p-1$ 所需的最少操作次数。
- 可以证明，这总是需要有限次的操作。
**输入输出样例**
- 输入样例 #1：
```
11
2 3
1 2
4 2
1 1 1 1
6 6
1 2 3 4 5 0
5 2
1 0 1 0 1
3 10
1 2 3
5 1000
4 1 3 2 5
3 5
2 3 4
4 4
3 2 3 0
1 3
2
5 5
1 2 2 2 4
3 4
1 0 1
```
- 输出样例 #1：
```
1
1
0
0
7
995
2
1
1
1
2
```**题意翻译** - 题目：所有可能的数码 - 数据组数：多组 - 描述：给定一个 $n$ 位的 $p$ 进制数，第 $i$ 位为 $a_i$。 - 操作：每次操作可以将这个数加 $1$。 - 目标：求最少操作多少次，使得数码 $0, ..., p-1$ 都至少出现过一次（包含在中间过程中出现）。 **题目描述** - 题目：所有可能的数码 - 描述：黑板上写着一个正数 $x$，它是一个 $n$ 位的 $p$ 进制数（$2 \le p \le 10^9$），表示为序列 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）—— $x$ 的数码从左到右（从最高位到最低位）排列。 - 目标：Dmitry 非常喜欢这个数制的所有数码，他想要看到每一个数码至少出现一次。 - 操作：每次操作可以将黑板上的数 $x$ 增加 $1$。 - 任务：确定要使所有数码从 $0$ 到 $p-1$ 至少在黑板上出现一次所需的最少操作次数。 **输入输出格式** - 输入格式： - 第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^3$）——测试用例的数量。接下来是每个测试用例的描述。 - 每个测试用例的描述第一行包含两个整数 $n$（$1 \le n \le 100$）和 $p$（$2 \le p \le 10^9$）——数字的长度和数制的基础。 - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i < p$）——基于 $p$ 进制的 $x$ 的数码。 - 保证数字 $x$ 不包含前导零（即 $a_1 > 0$）。 - 输出格式： - 对于每个测试用例，打印一个整数——Dmitry 获得所有数码从 $0$ 到 $p-1$ 所需的最少操作次数。 - 可以证明，这总是需要有限次的操作。 **输入输出样例** - 输入样例 #1： ``` 11 2 3 1 2 4 2 1 1 1 1 6 6 1 2 3 4 5 0 5 2 1 0 1 0 1 3 10 1 2 3 5 1000 4 1 3 2 5 3 5 2 3 4 4 4 3 2 3 0 1 3 2 5 5 1 2 2 2 4 3 4 1 0 1 ``` - 输出样例 #1： ``` 1 1 0 0 7 995 2 1 1 1 2 ```