AT_abc403_f.[ABC403F] Shortest One Formula

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个正整数 $N$ 。

请找出由字符 1、+、*、(、) 组成的数学表达式中，满足以下所有条件的最短表达式 $S$ ：

$S$ 符合以下 BNF 语法中 <expr> 符号的定义
$S$ 表示的数学表达式计算结果等于 $N$

BNF 语法定义如下：

<expr>   ::= <term> | <expr> "+" <term>
<term>   ::= <factor> | <term> "*" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= "1" | "1" <number>

符合 <expr> 定义的表达式示例：

1111+111：表示 $1111+111$
(1+1)*(1+1)：表示 $(1+1)\times (1+1)$
(11+(1+1)*(1+1))+1：表示 $(11+(1+1)\times (1+1))+1$

不符合 <expr> 定义的表达式示例：

(1+1)(1+1)
1+2
1-1
1/1
)1(
1++1
+1
(+1)
1*+1

输入格式

输入通过标准输入给出，格式如下：

$N$

输出格式

输出满足条件的最短表达式。

输入输出样例

输入#1
```
9
```
输出#1
```
(1+1+1)*(1+1+1)
```
输入#2
```
11
```
输出#2
```
11
```
输入#3
```
403
```
输出#3
```
1+(1+1+1)*(1+11+11+111)
```

说明/提示

约束条件

$1 \leq N \leq 2000$
输入均为整数

样例解释 #1

值为 $9$ 的表达式可能有多种形式，例如：

(1+1+1)*(1+1+1)
1+1+1+1+1+1+1+1+1
(1+1)*(1+1)*(1+1)+1

其中 (1+1+1)*(1+1+1) 是最短的表达式。

翻译由 DeepSeek V3 完成

输入解题思路，AI测评打分。不知道怎么写?

首页