309455: CF1681D. Required Length

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Required Length

题意翻译

给定两个正整数n,x,对于每个x,在其中截取一位10进制数字y,与x相乘得到x’, 按上述操作,求出当x的位数与n相等时的最少操作次数

题目描述

You are given two integer numbers, $ n $ and $ x $ . You may perform several operations with the integer $ x $ . Each operation you perform is the following one: choose any digit $ y $ that occurs in the decimal representation of $ x $ at least once, and replace $ x $ by $ x \cdot y $ . You want to make the length of decimal representation of $ x $ (without leading zeroes) equal to $ n $ . What is the minimum number of operations required to do that?

输入输出格式

输入格式


The only line of the input contains two integers $ n $ and $ x $ ( $ 2 \le n \le 19 $ ; $ 1 \le x < 10^{n-1} $ ).

输出格式


Print one integer — the minimum number of operations required to make the length of decimal representation of $ x $ (without leading zeroes) equal to $ n $ , or $ -1 $ if it is impossible.

输入输出样例

输入样例 #1

2 1

输出样例 #1

-1

输入样例 #2

3 2

输出样例 #2

4

输入样例 #3

13 42

输出样例 #3

12

说明

In the second example, the following sequence of operations achieves the goal: 1. multiply $ x $ by $ 2 $ , so $ x = 2 \cdot 2 = 4 $ ; 2. multiply $ x $ by $ 4 $ , so $ x = 4 \cdot 4 = 16 $ ; 3. multiply $ x $ by $ 6 $ , so $ x = 16 \cdot 6 = 96 $ ; 4. multiply $ x $ by $ 9 $ , so $ x = 96 \cdot 9 = 864 $ .

Input

题意翻译

给定两个正整数n,x,对于每个x,在其中截取一位10进制数字y,与x相乘得到x’, 按上述操作,求出当x的位数与n相等时的最少操作次数

Output

**题意翻译**

给定两个正整数n和x,可以执行以下操作:从x的十进制表示中选择一个数字y(y至少在x中出现一次),然后用y乘以x。目标是使x的十进制表示的长度(不包含前导零)等于n。求达到这个目标所需的最少操作次数。

**题目描述**

给定两个整数n和x。你可以对整数x执行多种操作。

每次操作如下:从x的十进制表示中选择一个数字y(y至少在x中出现一次),然后用y乘以x。

你的目标是使x的十进制表示的长度(不包含前导零)等于n。求达到这个目标所需的最少操作次数。

**输入输出格式**

**输入格式**

输入包含一行,有两个整数n和x($2 \le n \le 19$;$1 \le x < 10^{n-1}$)。

**输出格式**

输出一个整数,表示使x的十进制表示的长度(不包含前导零)等于n所需的最少操作次数,或者如果无法达到目标,则输出-1。

**输入输出样例**

**输入样例 #1**

```
2 1
```

**输出样例 #1**

```
-1
```

**输入样例 #2**

```
3 2
```

**输出样例 #2**

```
4
```

**输入样例 #3**

```
13 42
```

**输出样例 #3**

```
12
```

**说明**

在第二个样例中,可以通过以下操作达到目标:

1. 将x乘以2,得到x=2*2=4;
2. 将x乘以4,得到x=4*4=16;
3. 将x乘以6,得到x=16*6=96;
4. 将x乘以9,得到x=96*9=864。**题意翻译** 给定两个正整数n和x,可以执行以下操作:从x的十进制表示中选择一个数字y(y至少在x中出现一次),然后用y乘以x。目标是使x的十进制表示的长度(不包含前导零)等于n。求达到这个目标所需的最少操作次数。 **题目描述** 给定两个整数n和x。你可以对整数x执行多种操作。 每次操作如下:从x的十进制表示中选择一个数字y(y至少在x中出现一次),然后用y乘以x。 你的目标是使x的十进制表示的长度(不包含前导零)等于n。求达到这个目标所需的最少操作次数。 **输入输出格式** **输入格式** 输入包含一行,有两个整数n和x($2 \le n \le 19$;$1 \le x < 10^{n-1}$)。 **输出格式** 输出一个整数,表示使x的十进制表示的长度(不包含前导零)等于n所需的最少操作次数,或者如果无法达到目标,则输出-1。 **输入输出样例** **输入样例 #1** ``` 2 1 ``` **输出样例 #1** ``` -1 ``` **输入样例 #2** ``` 3 2 ``` **输出样例 #2** ``` 4 ``` **输入样例 #3** ``` 13 42 ``` **输出样例 #3** ``` 12 ``` **说明** 在第二个样例中,可以通过以下操作达到目标: 1. 将x乘以2,得到x=2*2=4; 2. 将x乘以4,得到x=4*4=16; 3. 将x乘以6,得到x=16*6=96; 4. 将x乘以9,得到x=96*9=864。

加入题单

上一题 下一题 算法标签: