2 shunfurh shunfurh 于 2017.09.05 10:06 提问

Hex Tile Equations

Problem Description

An amusing puzzle consists of a collection of hexagonal tiles packed together with each tile showing a digit or '=' or an arithmetic operation '+', '-', '*', or '/'. Consider continuous paths going through each tile exactly once,
with each successive tile being an immediate neighbor of the previous tile. The object is to choose such a path so the sequence of characters on the tiles makes an acceptable equation, according to the restrictions listed below. A sequence is illustrated in each figure above. In Figure 1, if you follow the gray path from the top, the character sequence is"6/3=9-7". Similarly, in Figure 2, start from the bottom left 3 to get "3*21+10=73".
There are a lot of potential paths through a moderate sized hex tile pattern. A puzzle player may get frustrated and want to see the answer. Your task is to automate the solution. The arrangement of hex tiles and choices of characters in each puzzle satisfy these rules:

The hex pattern has an odd number of rows greater than 2. The odd numbered rows will all contain the same number of tiles. Even numbered rows will have one more hex tile than the odd numbered rows and these longer even numbered rows will stick out both to the left and the right of the odd numbered rows.

1.There is exactly one
2. '=' in the hex pattern.
3. There are no more than two '*' characters in the hex pattern.
4. There will be fewer than 14 total tiles in the hex pattern.
5.With the restrictions on allowed character sequences described below, there will be a unique acceptable solution in the hex pattern.

To have an acceptable solution from the characters in some path, the expressions on each side of the equal sign must be in acceptable form and evaluate to the same numeric value. The following rules define acceptable form of the expressions on each side of the equal sign and the method of expression evaluation:

6.The operators '+', '-', '*', and '/' are only considered as binary operators, so no character sequences where '+' or '-' would be a unary operator are acceptable. For example "-2*3=-6" and "1 =5+-4" are not acceptable.
7.The usual precedence of operations is not used. Instead all operations have equal precedence and operations are carried out from left to right. For example "44-4/2=2+3*4" is acceptable and "14=2+3*4" is not acceptable.
8.If a division operation is included, the equation can only be acceptable if the division operation works out to an exact integer result.
For example "10/5=12/6" and "7+3/5=3*4/6" are acceptable. "5/2*4=10"
is not acceptable because the sides would only be equal with exact mathematical calculation including an intermediate fractional result. "5/2*4=8" is not acceptable because the sides of the equation would
only be equal if division were done with truncation.
9.At most two digits together are acceptable. For example, " 9. 123+1 = 124" is not acceptable.
10.A character sequences with a '0' directly followed by another digit is not acceptable. For example,"3*05=15" is not acceptable.

With the assumptions above, an acceptable expression will never involve an intermediate or final arithmetic result with magnitude over three million.

Input
The input will consist of one to fifteen data sets, followed by a line containing only 0. The first line of a dataset contains blank separated integers r c, where r is the number of rows in the hex pattern and c is the number of entries in the odd numbered rows. The next r lines contain the characters on the hex tiles, one row per line. All hex tile characters for a row are blank separated. The lines for odd numbered rows also start with a blank, to better simulate the way the hexagons fit together. Properties 1-5 apply.

Output
There is one line of output for each data set. It is the unique acceptable equation according to rules 6-10 above. The line includes no spaces.

Sample Input
5 1
6
/ 3
=
9 -
7
3 3
1 + 1

  • 2 0 = 3 3 7 5 2 9 -
  • 2 = 3 4
  • 8 3 4 / 0

Sample Output
6/3=9-7
3*21+10=73
8/4+3*9-2=43

2个回答

caozhy
caozhy   Ds   Rxr 2017.09.07 23:47
已采纳
shen_wei
shen_wei   Ds   Rxr 2017.09.05 15:28
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
基于TILED的2D游戏绘制方法详解
1      Introduction1.1    Purpose and Scope游戏引擎作为游戏制作的基础是保证游戏质量的最重要部分,目前主要包括两方面:背景绘制和动画播放。为了使新员工对目前开发的手机游戏能够有深入的了解,此文档详细描述了目前使用的背景绘制的原理和具体实现方法。1.2    AbbreviationGD               Game Desi
Differential Equations and Linear Algebra(4th) 无水印原版pdf
Differential Equations and Linear Algebra(4th) 英文无水印原版pdf 第4版 pdf所有页面使用FoxitReader、PDF-XChangeViewer、SumatraPDF和Firefox测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 查看此书详细信息请在美国亚马逊官网搜索此书
杭电 HDU ACM 1496 Equations
Equations Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6065    Accepted Submission(s): 2455 Problem Description Consider equations h
Partial Differential Equations
Partial Differential Equations - An Introduction - W. Strauss (Wiley, 1992) WW.djvu
完整清晰的《Partial Differential Equations》第二版电子版+勘误表 (Lawrence C. Evans)
Lawrence C. Evanns 的《偏微分方程》第二版电子版+勘误表,非扫描版,不缺页,本人亲自完善的,页面文字除本人补充进去的17个缺页内容外可复制,网络上搜不到。
深度学习(5) Normal Equations 的由来
Normal Equations 的由来 假设我们有m个样本。特征向量的维度为n。因此,可知样本为{(x(1),y(1)), (x(2),y(2)),... ..., (x(m),y(m))},其中对于每一个样本中的x(i),都有x(i)={x1(i), xn(i),... ...,xn(i)}。令 H(θ)=θ0 + θ1x1 +θ2x2 +... + θnxn,则有
Partial Differential Equations with Fourier Series and Boundary Value Problem
关于偏微分方程的书,第二版 Nakhle H. Asmar著 813页
poj--1100 Dreisam Equations(dfs)
Problem Link题解在等式中重新放置 + - * 以便构造一个有效的等式。对于每个可以放置运算符的位置,都有三种选择,因此解空间是一棵完全三叉树,回溯搜索O(n3)O(n^3)。需要注意存在冗余括号的情况。#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cctype
CFD经典著作:numerical partial differential equation - finite difference method
"This important volume is the first part of a two-part textbook (the second part is entitled Conservation laws and elliptic equations). The text includes interesting homework problems that implement different aspects of most of the schemes discussed. The implementation aspect of this text includes a large amount of computing. Other useful aspects of computing included in this volume are symbolic computing and the use of graphics for analysis. Prerequisites suggested for using this book might include one semester of partial differential equations and some programming capability. This book will be a good reference text for students." -- MATHEMATICAL REVIEWS
POJ 1100 Dreisam Equations 笔记
在等式两边添加加、减、乘三种符号使两边相等。除括号外,三个符号的优先级相等。