Танцы на прямоугольной площадке
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Матрицы и сетки
- Стек, очередь, связные списки
На прямоугольной площадке в каждой клетке стоит танцор; дана матрица skills уровней мастерства (все не меньше 1). Соревнование идёт раундами. Компасный сосед танцора — ближайший ещё не выбывший танцор в той же строке или в том же столбце в одном из четырёх направлений (вверх, вниз, влево, вправо), так что соседей от 0 до 4.
После каждого раунда одновременно выбывают все танцоры, у которых есть хотя бы один компасный сосед и мастерство которых строго меньше среднего мастерства их соседей. Соседи считаются по составу этого раунда: выбывающий танцор ещё участвует в проверке остальных. Танцор без соседей не выбывает. Если после раунда никто не выбыл, соревнование заканчивается.
Интерес раунда — сумма мастерства всех танцоров, участвовавших в нём (включая тех, кто выбудет после него). Верните суммарный интерес всех раундов. Площадка может содержать до нескольких тысяч клеток, а раундов может быть много, поэтому пересчитывать всю площадку каждый раунд слишком долго.
Пример: [[1, 1, 1], [1, 2, 1], [1, 1, 1]] → 16 (10 в первом раунде, после него выбывают четыре единицы на сторонах, 6 во втором).
Источник: Coding Competitions Archive, codejam/2020/round_1a/square_dance · © Google LLC · Apache-2.0 · условие переведено и дополнено