Легенда

Учёные разрабатывают систему, позволяющую определить оптимальный маршрут спуска с любой горы. Для этого несколько дронов-квадрокоптеров отправляются от вершины к подножью выбранной горы, просматривают все пути, по которым может пройти человек, и запоминают их. После чего программа анализирует полученные данные и выбирает наиболее короткий путь до основания горы.

Ваша задача: написать программу, которая будет обрабатывать данные с дронов и выбирать наиболее короткий путь для человека. Данные записываются в виде карты-пирамиды, первая строка которой соответствует вершине горы, а последняя — её подножью. Перемещение по карте производится вниз по соседним ячейкам. В каждой ячейке карты записано время, которое необходимо затратить дрону на преодоление данного пути. Однако, дроны также анализируют местность на проходимость её человеком и помечают сложнопроходимые места символом «*» рядом со временем. Это значит, что данный путь у человека займёт в 2 раза больше времени, чем у дрона. Эти данные представлены в виде карты-пирамиды. Программа же должна вывести времена для участков такого маршрута, прохождение которого занимает наименьшее время от вершины до основания горы для человека.

Учтите, что в ответе нужно указать цифры времени для дрона, в пути, занимающим наименьшее время у человека, без символов «*».

Входной формат: в первой строке число N — число строк в карте-пирамиде. Далее идёт N строк, состоящих из целых чисел, в каждой строке на одно число больше, чем в предыдущей. Каждое число соответствует времени пролёта дроном соответствующего участка. Символ сложного пути в виде «*» ставится справа от числа. Все числа разделены пробелами. Пример входных данных:

5
9
5 7
3 12 8*
3 2 4 1*
6 1* 5 4* 7*

Выходной формат: несколько чисел в строку через пробел, звенья наиболее короткого пути. Например,

7 3 12 4 1 8
Time Limit: 1 секунда
Memory Limit: 256 MB


Видео-разбор

Последнее изменение: Monday, 19 September 2022, 12:10