shunfurh 于 2017.09.02 09:52 提问

Firefighters

A mathematician kept all his documents in a file cabinet near his desk. One day a fire set out in his office and most of his works were badly damaged. Luckily, some of the equations he had solved so many years during his long career were partially preserved. Each equation contained an expression in left side and result in the right. The preserved expressions consisted of all the numbers and brackets, but unfortunately, some of the operators between them were lost in the fire. Another problem was that the results of the equations were scattered and the mathematician was not sure if a certain answer is the result of a certain expression. Your task is to help the mathematician determine if the expressions and the results he was able to save from the fire match one another.
In order to do this, you are given an expression, containing the integer numbers between 1 and 999, simple mathematical operators (+, -, *, /), brackets, and question marks (?), representing the lost mathematical operators. For every expression given, your only task is to state if an expression can or cannot give the required result. In order to help you, the mathematician has chosen only expressions that have the following restrictions:

1.The expressions contain no more than 100 symbols;

2.The brackets enclose no more than 1 operator with his two operands. However, every one of these operands can be an expression in brackets;

3.The constants in the expressions have no sign, i.e. there are no negative numbers in expressions;

4.The maximum number of question marks in the expressions (the lost operators) is less or equal to 10.

The calculation should be performed using the following rules:

1. The operators * and / are of higher priority than the operators + and -. Parentheses may change the priorities as usually;

2. The operators +, -, *, and / are left associative, meaning that they group from left to right. If a, b and c are numbers:
a*b*c = (a*b)*c, a/b/c = (a/b)/c, a/b*c = (a/b)*c, a+b+c = (a+b)+c, a-b+c = (a-b)+c, etc.

3. When dividing two integers, you should ignore the decimal fraction, for example consider the following equations: 2/5=0, 9/5=1, 100/6=16.

Input: The first line of the input file contains an integer N - determining the number of equations. Next 2*N lines contain the equations. One equation is defined in two lines. The first line is the expression, defining the left side of the equation; second line is an integer result, defining the right side of the equation. The input lines do not have blanks. The strings representing expressions are guaranteed to have no syntax errors.

Output: For every equation in the input file, write yes or no on separate lines on the standard output. If the expression can give the result, write yes. Otherwise, if the result cannot be achieved, write no.

Sample Input

3
1?((2*(3*4))+(5+6))
35
1?2*3+4-14
0
1?3*4/5*6+12
11

Sample Output

yes
no
no

1个回答

caozhy      2017.09.17 00:25

How we decide
Product Description 　　The first book to use the unexpected discoveries of neuroscience to help us make the best decisions. 　　Since Plato, philosophers have described the decision-making process as either rational or emotional: we carefully deliberate, or we blink and go with our gut. But as scientists break open the mind's black box with the latest tools of neuroscience, they re discovering that this is not how the mind works. Our best decisions are a finely tuned blend of both feeling and reason and the precise mix depends on the situation. When buying a house, for example, it s best to let our unconscious mull over the many variables. But when we re picking a stock, intuition often leads us astray. The trick is to determine when to use the different parts of the brain, and to do this, we need to think harder (and smarter) about how we think. 　　Jonah Lehrer arms us with the tools we need, drawing on cutting-edge research as well as the real-world experiences of a wide range of deciders from airplane pilots and hedge fund investors to serial killers and poker players. 　　Lehrer shows how people are taking advantage of the new science to make better television shows, win more football games, and improve military intelligence. His goal is to answer two questions that are of interest to just about anyone, from CEOs to firefighters: How does the human mind make decisions? And how can we make those decisions better?

ACM Fighting! 2 1.计算几何 5 1.1 注意 5 1.2几何公式 6 1.3 多边形 8 1.4多边形切割 11 1.5 浮点函数 12 1.6 面积 18 1.7球面 18 1.8三角形 19 1.9三维几何 22 1.10 凸包 30 1.11 网格 32 1.12 圆 33 1.13 矢量运算求几何模板 35 1.14结构体表示几何图形 47 1.15四城部分几何模板 52 1.16 一些代码 54 1.16.1 最小圆覆盖_zju1450 54 1.16.2 直线旋转_两凸包的最短距离(poj3608) 58 1.16.3 扇形的重心 62 1.16.4 根据经度纬度求球面距离 62 1.16.5 多边形的重心 64 1.16.6 存不存在一个平面把两堆点分开(poj3643) 66 1.16.7 pku_3335_判断多边形的核是否存在 67 1.16.8 pku_2600_二分+圆的参数方程 74 1.16.9 pku_1151_矩形相交的面积 76 1.16.10 pku_1118_共线最多的点的个数 78 1.16.11 pku2826_线段围成的区域可储水量 80 1.16.12 Pick公式 84 1.16.13 N点中三个点组成三角形面积最大 86 1.16.14 直线关于圆的反射 89 1.16.15 pku2002_3432_N个点最多组成多少个正方形(hao) 94 1.16.16 pku1981_单位圆覆盖最多点(poj1981)CircleandPoints 97 1.16.17 pku3668_GameofLine_N个点最多确定多少互不平行的直线(poj3668) 99 1.16.18 求凸多边形直径 100 2.组合 102 2.1 组合公式 102 2.2 排列组合生成 102 2.3 生成gray码 104 2.4 置换(polya) 104 2.5 字典序全排列 105 2.6 字典序组合 105 2.7 一些原理及其例子 106 3.数论 108 3.1 阶乘最后非0位 108 3.2 模线性方程组 108 3.3 素数 110 3.4 欧拉函数 114 3.6高精度 116 3.6.1平方根 116 3.6.2 高精度乘幂 117 3.7 高斯消元回代法 122 3.8 数值计算 124 3.8.1 定积分计算 124 3.8.2 多项式求根(牛顿法) 125 3.8.3 周期性方程(追赶法) 127 4.排序 128 4.1快速选择算法 128 4.2归并排序+逆序数的求取 128 5.字符串 130 5.1 KMP应用 130 5.2 后缀数组 131 5.3 中缀表达式转后缀表达式 134 5.4 Firefighters 表达式求值 135 6.博弈 139 6.1 博弈的AB剪枝 139 6.1.1 取石子 139 6.2 博弈 SG函数 局势分割 141 7.数据结构 142 7.1 TRIE 142 7.2 线段树 147 7.3 并查集 151 7.4 树状数组 152 7.5 点树 154 7.6 STL 156 7.7 离散化 157 8.图论 158 8.0 2-SAT 158 8.2 寻找Euler回路 163 8.3 拓扑排序 163 8.4 差分约束系统 164 8.5 笛卡尔树 165 8.6 LCA和RMQ 167 8.7 割和桥 171 8.8 最小生成树(kruskal) 172 8.9 最短路径 173 8.10 最大网络流 175 8.11 最小费用流 180 8.12 最大团问题 182 8.13 二分图匹配 184 8.14 带权的最优二分图匹配 184 9.搜索算法概略 187 9.1 迭代深搜+IDA* 187 9.2 分之界限法（深搜） 189 9.3 A* 8数码问题( pascal ) 192 9.4 优先队列广搜 194 10.应用 197 10.1 Joseph问题 197 10.2 N皇后构造解 197 10.3 布尔母函数 198 10.4 第k元素 199 10.5 幻方构造 199 10.6 模式匹配(kmp) 201 10.7 逆序对数 201 10.8 字符串最小表示 202 10.9 最长公共单调子序列 202 10.10 最长子序列 204 10.11 最大子串匹配 204 10.12 最大子段和 205 10.13 最大子阵和 206 11.其它 207 11.1 大数(只能处理正数) 207 11.2 分数 212 11.3 矩阵 214 11.4 线性方程组 216 11. 5 线性相关 218 11.6 日期 219 11.7 读入 220 11.8 函数 220