Разбор задач Технокубок 2016 — Отборочный Раунд 1

Revision ru4, by fcspartakm, 2016-03-24 13:02:34

648A - Наибольший подъем

Для решения данной задачи насчитаем высоту каждой горы и сохраним ее в массиве h[], где h[j] равно высоте j-й горы. Для этого обойдем заданную матрицу, и если элемент, стоящий в строке i и в столбце j (строки и столбцы 0-индексированы), равен звездочке, обновим высоту j-й горы: h[j] = max(h[j], n - i). Осталось просто проитерироваться по столбцам от 0 до m — 2 включительно, и, если текущий столбец равен j, обновить величину максимального подъема или максимального спуска величиной |h[j + 1] - h[j]|.

Пример решения

648B - Собери стол

Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним ее в переменную len (len = sum / n, где sum — это суммарная длина всех частей, а n — количество ножек стола). Сохраним длины всех частей ножек в массив a[] и отсортируем его по возрастанию. Затем переберем части ножек переменной i от 0 до n - 1 включительно и будем выводить в ответ пары вида (a[i], len - a[i]).

Пример решения

648C - Путь Робота

Сначала найдем стартовую позицию Робота, сохраним ее и присвоим значение стартовой позиции звездоке. Так как по условию задана ломаная без самопересечений и самокасаний верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звездочка, перейдем в соседнюю клетку, значение которой равно звездочке, и присвоим ее значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звездочкой, значит мы обошли всю ломаную и нужно закончить работу программы.

Пример решения
Tags технокубок, отборочный, editorial, разбор

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru8 Russian fcspartakm 2016-03-24 13:23:35 40 (опубликовано)
ru7 Russian fcspartakm 2016-03-24 13:04:53 42 Мелкая правка: 'я часть:\n~~~~~\n ' -> 'я часть:\n\n~~~~~\n '
ru6 Russian fcspartakm 2016-03-24 13:04:24 6173
ru5 Russian fcspartakm 2016-03-24 13:03:24 69
ru4 Russian fcspartakm 2016-03-24 13:02:34 1702
ru3 Russian fcspartakm 2016-03-24 12:49:12 20 Мелкая правка: ' Сохраним все длины все' -> ' Сохраним длины все'
ru2 Russian fcspartakm 2016-03-24 12:48:48 822
ru1 Russian fcspartakm 2016-03-24 12:32:29 1130 Первая редакция (сохранено в черновиках)