[BCSP-X 2024 12 月小学高年级组] 质数补全

Luogu

IDLGB4158

Time1000ms

Memory512MB

DifficultyP2

2024北京枚举深度优先搜索 DFS筛法BCSP-X

Alice 在纸条上写了一个质数，第二天再看时发现有些地方污损看不清了。 - 在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数称为质数请你帮助 Alice 补全这个质数，若有多解输出数值最小的，若无解输出 $-1$。例如纸条上的数字为 $\tt{1*}$（$\tt{*}$ 代表看不清的地方），那么这个质数有可能为 $11, 13, 17, 19$，其中最小的为 $11$。 ## Input 第一行 $1$ 个整数 $t$，代表有 $t$ 组数据。接下来 $t$ 行，每行 $1$ 个字符串 $s$ 代表 Alice 的数字，仅包含数字或者 $\tt{*}$，并且保证首位不是 $\tt{*}$ 或者 $0$。 ## Output 输出 $t$ 行，每行 $1$ 个整数代表最小可能的质数，或者 $-1$ 代表无解。 [samples] ## Note ### 样例 3-6 参考附件中的样例。 ### 数据范围 $|s|$ 代表 $s$ 串的长度，对于所有数据，$1 \leq t \leq 10, 1 \leq |s| \leq 7$，$s$ 中仅包含数字或者 $\tt{*}$，并且保证首位不是 $\tt{*}$ 或者 $0$。本题采用捆绑测试，你必须通过子任务中的所有数据点以及其依赖的子任务，才能获得子任务对应的分数。 | 子任务编号 | 分值 | $\mid s\mid$ | 特殊性质 | 子任务依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $35$ | $\leq 7$ | $s$ 中没有 $\tt{*}$ | | | $2$ | $30$ | $\leq 4$ | | | | $3$ | $24$ | $\leq 7$ | $s$ 中至多包含 $1$ 个 $\tt{*}$ | $1$ | | $4$ | $11$ | $\leq 7$ | | $1,2,3$ |

Samples

Input #1

10
1*
3**
7**
83*7
2262
6**1
29*7
889*
777*
225*

Output #1

Input #2

10
4039***
2***5*5
4099961
25**757
7***0**
1***00*
41811*9
6***0*7
8***1**
6561*59

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[BCSP-X 2024 12 月小学高年级组] 质数补全",
    "description": {
      "content": "Alice 在纸条上写了一个质数，第二天再看时发现有些地方污损看不清了。 - 在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数称为质数 请你帮助 Alice 补全这个质数，若有多解输出数值最小的，若无解输出 $-1$。 例如纸条上的数字为 $\\tt{1*}$（$\\tt{*}$ 代表看不清的地方），那么这个质数有可能为 $11, 13, 17, 19$，其中最小的为",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4158"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice 在纸条上写了一个质数，第二天再看时发现有些地方污损看不清了。\n\n- 在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数称为质数\n\n请你帮助 Alice 补全这个质数，若有多解输出数值最小的，若无解输出 $-1$。\n\n例如纸条上的数字为 $\\tt{1*}$（$\\tt{*}$ 代表看不清的地方），那么这个质数有可能为 $11, 13, 17, 19$，其中最小的为...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments