Ctrl K

Самая длинная цепочка салюта

Средняя
На площади разложены пиротехнические заряды. Заряд charges[i] = [x, y, r] стоит в точке (x, y), а его вспышка поджигает всё в круге радиуса r с центром в этой точке (граница круга тоже считается). Когда заряд срабатывает, он поджигает все заряды в своём круге, те — заряды в своих кругах, и так далее. Обратите внимание: если A достаёт до B, это не значит, что B достаёт до A. Вы поджигаете ровно один заряд. Верните наибольшее число зарядов, которые могут сработать в итоге (включая первый).
Пример 1
charges=[[2, 2, 5], [6, 2, 3], [9, 2, 3]] → 3

Заряд 0 достаёт до заряда 1 (расстояние 4), а тот — до заряда 2 (расстояние 3): сработают все три. Если начать с заряда 2, он подожжёт только заряд 1, а до заряда 0 радиуса 1 не хватит.

Пример 2
charges=[[1, 1, 1], [10, 10, 1]] → 1

Заряды слишком далеко друг от друга, сработает только подожжённый.

Ограничения
  • 1 ≤ len(charges) ≤ 100
  • len(charges[i]) == 3
  • 0 ≤ x, y ≤ 10⁵
  • 1 ≤ r ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЧерез парк в обход прудов СложнаяЦепочки отношений СредняяКратчайший путь катящегося шарика СредняяОткрытые комнаты от холла СредняяГонка за сокровищами у ворот Средняя
загружаем Python…
Вход
charges=[[2, 2, 5], [6, 2, 3], [9, 2, 3]]
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 117 тестов на сервере, включая скрытые.