eolymp
bolt
Try our new interface for solving problems
Məsələlər

Уравнение на шестиугольных плитках

Уравнение на шестиугольных плитках

Забавная головоломка состоит из набора шестиугольных плиток, с каждой из которых связана цифра, или '\textbf{=}', или арифметическая операция '\textbf{+}', '\textbf{-}', '\textbf{*}', или '\textbf{/}'. Рассмотрим непрерывные пути, проходящие через каждую плитку ровно один раз, в которых каждая следующая плитка является непосредственным соседом предыдущей. Задача состоит в нахождении такого пути, чтобы последовательность символов, изображенная на плитках, образовывала корректное уравнение согласно ограничений, приведенных ниже. Возможная последовательность представлена на рисунках вверху. На \textit{\textbf{Рисунке 1}} если следовать сверху вдоль серого пути, то получится последовательность символов "\textbf{6/3=9-7}". Аналогично на \textit{\textbf{Рисунке 2}} если начать с левой нижней \textbf{3}, то можно получить "\textbf{3*21+10=73}". Существует множество путей на наборе шестиугольных плиток даже небольшого количества. Игрок может разочароваться в решении головоломки и захотеть увидеть решение. Вам следует автоматизировать процесс нахождения решения. Расположение шестиугольных плиток и выбор символов для головоломки должны удовлетворять следующим правилам: 1. Шестиугольная доска содержит нечетное количество строк, большее \textbf{2}. Строки с нечетными номерами содержат одинаковое количество плиток. Строки с четными номерами содержат на одну плитку больше, нежели строки с нечетными номерами. И вот эти, более длинные строки, склеены сверху и снизу со строками с нечетными номерами. 2. На доске находится только одна плитка '\textbf{=}'. 3. На доске находится не более двух символов '\textbf{*}'. 4. На доске находится не более \textbf{14} плиток. 5. С учетом ограничений на символы, приведенных ниже, всегда существует единственное решение. Для получения допустимого решения из символов на некотором пути, выражения с каждой стороны от знака равенства должны иметь допустимый вид и иметь одно и то же числовое значение. Следующие правила определяют допустимый вид выражений с каждой из сторон от знака равенства и задают порядок вычисления выражения: 6. Операторы '\textbf{+}', '\textbf{-}', '\textbf{*}' и '\textbf{/}' могут быть только бинарными, то есть никакая последовательность с унарным '\textbf{+}' или '\textbf{-}' недопустима. Например "\textbf{-2*3=-6}" и "\textbf{1 =5+-4}" недопустимы. 7. Здесь не работает обычный приоритет операций. Все операции имеют одинаковый приоритет и выполняются слева направо. Например "\textbf{44-4/2=2+3*4}" допустимо, а "\textbf{14=2+3*4}" недопустимо. 8. Если выражение содержит операцию деления, то оно допустимо только если ее результатом будет целое число. Например "\textbf{10/5=12/6}" и "\textbf{7+3/5=3*4/6}" допустимы. А "\textbf{5/2*4=10}" недопустимо, так как промежуточный результат не является целочисленным. "\textbf{5/2*4=8}" недопустимо, так как равенство достигается только если при делении выполняется операция округления. 9. Каждое число должно состоять из не более чем двух цифр. Например, "\textbf{123+1 = 124}" не приемлемо. 10. Символьная последовательность из '\textbf{0}', за которым сразу следует другая цифра, недопустима. Например, "\textbf{3*05=15}" недопустимо. Удовлетворяя описанным ограничениям, никакой промежуточный или конечный результат вычисления выражения никогда не превосходит по модулю трех миллионов. \InputFile Входные данные содержат от одного до пятнадцати тестов, за которыми следует строка из единственного \textbf{0}. Первая строка каждого теста содержит два разделенных пробелом целых числа \textbf{r} \textbf{c}, где \textbf{r} - число строк шестиугольной сетки, а \textbf{c} - количество ячеек в строках с нечетными номерами. Следующие \textbf{r} строк содержат символы, записанные на шестиугольных плитках, каждая строка сетки задается в отдельной входной строке. Все символы в строке разделены пробелами. Строки, соответствующие нечетным строкам сетки, начинаются с пробела. Это сделано для лучшего восприятия того, как шестиугольники расположены между собою. Свойства \textbf{1-5} имеют место. \OutputFile Для каждого теста вывести одну строку. Она должна содержать единственное приемлемое уравнение согласно правил \textbf{6-10}. Строка не должна содержать пробелов.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
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
Çıxış verilənləri #1
6/3=9-7
3*21+10=73
8/4+3*9-2=43