eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рівняння на шестикутних плитках

Рівняння на шестикутних плитках

Забавна ломиголовка складається з набору шестикутних плиток, з кожною з яких пов'язана цифра, або '\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}. Рядок не повинен містити пропусків.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #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
Вихідні дані #1
6/3=9-7
3*21+10=73
8/4+3*9-2=43