C. иннокентий и одна известная страна
иннокентий работает в одной большой корпорации. сейчас его является открытие филиала в новой стране. в стране n городов соединенных n − 1 дорогой так, что из любого
города можно добраться до любого другого.
открытие филиала — дело ответственное. филиал должен располагаться в городе, стоимость
транспортировки из которого минимальна. для этого иннокентий придумал следующую форму
расчета: пусть u — выбранный город, а vi — соседние города, то есть такие, в которые можно
попасть из
p
u, проехав ровно по одной дороге. тогда стоимость транспортировки определяется как
(dvi + 1)2
, где dvi — длина наибольшего пути, начинающегося в городе vi
, который не проходит
дважды через какой-либо город и не проходит через u. иннокентию выбрать город, в
котором нужно разместить склад, чтобы стоимость была минимальной.
формат входных данных
в первой строке входного файла записано число n — количество городов (1 6 n 6 5 · 105
).
в следующих n − 1 строках дано описание дорог. каждая строка содержит по два целых числа
u и v — номера городов, которые соответствующая дорога соединяет (1 6 u, v 6 n, u 6= v).
формат выходных данных
в выходной файл необходимо вывести два числа: наименьшую стоимость размещения филиала
и город, при выборе которого она достигается. если подходящих ответов несколько, выведите любой
из них.
Объяснение:
1.
Определяем количество символов в сообщении, для этого количество символов умножаем на количество страниц:
128 х 4 = 512 символов.
Находим сколько информации отводится на кодирование 1 символа:
0,125 Кбайт х 1024 = 128 байт или 128 х 8= 1024 бита всего в сообщении
1024 бита : 512 символов = 2 бита на 1 символ
Находим количество символов в алфавите по формуле N = 2^i:
N=2²=4
Мощность алфавита составляет 4 символа.
2.
Количество пирожков с вишней К1=2
Всего пирожков в корзине N=4+10+2+4=20
Вероятность выбора пирожка с вишней составляет
р1=К1/N=2/20=0,1
Теперь вычислим количество информации, содержащееся в сообщении, что Маша выбрала пирожок с вишней:
I1=log₂ (1/р1)=log₂(1/0,1)=log₂ 10=3,322 бита ≈4 бита (поскольку бит- минимальная единица информации и число бит не может быть дробным)
3.
2^i=N, где N - объём информации, а i - кол-во бит, которым кодируется единица информации. N=15*5=75
2^i=75
i=log₂ 75=6,23 бита ≈ 7 бит