Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2475. Миссия невозможна
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 01/11/2019 | Муниципальный этап 10-11 классы (4) |
| 09/12/2023 | Марафон 80 задач, 8 этап (C) |
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вор по кличке «Призрак» собирается похитить известный алмаз «Розовая пантера».
Алмаз находится в углу комнаты размером `M\ times\ N` метров в точке с координатами `(M,N)`.
Вход в комнату находится в другом углу комнаты в точке с координатами `(0,0)`. Инспектор Клузо
установил в комнате `K` сенсорных датчика, `i`-й датчик находится в точке с координами `(X_i,\ Y_i)` может засечь движение на расстоянии не более `D_i` метров.
Напишите программу, которая определяет, сможет ли «Призрак» похитить алмаз.
Первая строка ввода содержит три целых числа – размеры комнаты `M` и `N` (`10\ ≤\ M,\ N\ ≤\ 10^4`) и количество сенсоров `K` (`1\ ≤\ K\ ≤\ 1000`).
Следующие `K` строк содержат по три целых числа – координаты сенсора `X_i`, `Y_i` (`0\ <\ X_i\ <\ M`, `0\ <\ Y_i\ <\ N`) и его чувствительность `D_i` (`1\ ≤\ D_i\ ≤\ 10^4`).
Вывести сообщение «YES», если алмаз можно похитить, обойдя все сенсоры, иначе вывести сообщение «NO».
Пример ввода 1
10 22 2 6 16 5 4 6 5
Пример вывода 1
YES
Пример ввода 2
10 10 2 5 4 4 3 7 4
Пример вывода 2
NO
Описание подзадач и системы оценивания
Подзадача 1 (20 баллов)
`K\ =\ 1`
В этой подзадаче 8 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Программа должна проходить тесты из условия задачи, несмотря на то, что они не соответствуют ограничениям на подзадачу.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1\ <\ K\ ≤\ 50`
В этой подзадаче 16 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 3 (30 баллов)
Необходимые подзадачи: 1,2.
`50\ <\ K\ ≤\ 1000`
В этой подзадаче 16 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).
