В Тридесятом царстве города и ещё один город — столица. Один город впал в немилость царя. Какое наибольшее количество дорог может оставить царь между городами так, чтобы в опальный город нельзя было проехать ни из одного другого города? (Между двумя городами может быть только одна дорога, на которой нет других городов.) Напиши в ответ число — наибольшее количество дорог.

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