#P9782. DQY 的回家路

    ID: 6405 传统题 10000ms 1024MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划区间 DP记忆化搜索有限候选集缩减枚举与搜索固定一个变量消去另一维枚举较小维度排序与序列处理二分查找数据结构哈希表状态去重路径恢复CF2500

DQY 的回家路

DQY 的回家路

题目描述

车票编号由六个数字组成,每个数字为 00 到 99。请按原顺序使用全部六个数字,在它们之间加入运算符、负号和括号,构造值恰为 100100 的表达式;相邻数字可以拼成一个多位整数。

要求:

  • 数字不含前导零,单独的 0 合法;
  • 只能使用加法 +、减法 -、乘法 *、除法 /、一元负号 - 和括号;
  • 不能除以 00,每一步除法都必须整除;
  • 一元负号的优先级仅低于括号,可连续使用。

表达式的语法如下,其中数字是连续的十进制数字串:

表达式 := 式子 | 表达式 + 式子 | 表达式 - 式子
式子   := 式   | 式子 * 式     | 式子 / 式
式     := 数字 | -式           | (表达式)

例如 2*(3+4)、0+0、--239--179、(17+13)/6、0/10、-(21+12)、(((8))*(9)) 均为合法表达式。2(3+4)、2**2、-239-179-、17+13/6(不能整除)、10/0、0/0、1+() 不合法。

输入格式

从标准输入读入若干行,每行连续六个数字,表示一张车票编号。读到文件结束为止。

输出格式

对每行输入,输出一个符合要求、值为 100100 的表达式;不存在时输出 No solution。

样例 输入

123456
987654
111111
000000
001000

样例 输出

1+(2+3+4)*(5+6)
9+87+(6-5)*4
(111-11)/1
No solution
0+0+100+0

评分说明

本题只有一个测试点,按升序列出所有车票编号。所有输出均须符合格式。分值按原评测程序取整,按找到正确表达式的数量评分:设找到 xx 张可构造车票的正确表达式,所有存在解的车票数量为 TT,分数为下表所示。

xx 的范围 score(x)\mathrm{score}(x)
0≤x<50\le x<5 xx
5≤x<555\le x<55 5+(x−5)/105+(x-5)/10
55≤x<55555\le x<555 10+(x−55)/10010+(x-55)/100
555≤x<5555555\le x<5555 15+(x−555)/100015+(x-555)/1000
5555≤x<555555555\le x<55555 20+(x−5555)/1000020+(x-5555)/10000
55555≤x<T−5555555555\le x<T-55555 25+50(x−55555)/(T−2⋅55555)25+50(x-55555)/(T-2\cdot55555)
T−55555≤x<T−5555T-55555\le x<T-5555 75+(x−(T−55555))/1000075+(x-(T-55555))/10000
T−5555≤x<T−555T-5555\le x<T-555 80+(x−(T−5555))/100080+(x-(T-5555))/1000
T−555≤x<T−55T-555\le x<T-55 85+(x−(T−555))/10085+(x-(T-555))/100
T−55≤x<T−5T-55\le x<T-5 90+(x−(T−55))/1090+(x-(T-55))/10
T−5≤x≤TT-5\le x\le T 95+x−(T−5)95+x-(T-5)