Задача Задача №3530853
А
А
В Тридесятом царстве города и ещё один город — столица. Один город впал в немилость царя. Какое наибольшее количество дорог может оставить царь между городами так, чтобы в…
Запрос пользователя
В Тридесятом царстве города и ещё один город — столица. Один город впал в немилость царя. Какое наибольшее количество дорог может оставить царь между городами так, чтобы в опальный город нельзя было проехать ни из одного другого города? (Между двумя городами может быть только одна дорога, на которой нет других городов.) Напиши в ответ число — наибольшее количество дорог.
Разберёмся пошагово.
- Всего городов: 30 обычных городов + 1 столица = 31 город.
- Один город стал непопулярным и должен оказаться недоступным из других городов. Это значит, что у этого города должно быть нулевое звено (никакой дороги к нему), иначе из другого города можно попасть в опальный город.
- Следовательно, все дороги могут идти только между оставшимися 30 городами.
- Чтобы получить максимальное количество дорог, между этими 30 городами нужно построить все возможные дороги: это полный граф K30.
- Количество дорог в K30 равно числу пар городов: C(30, 2) = 30·29/2 = 435.
Ответ: 435
