Дан связный граф на 2016 вершин. За одну операцию можно выбрать две вершины на максимальном (по количеству ребер) расстоянии и соединить ребром. Может ли после N операций максимальное расстояние оказаться больше S при: а) N = 1, S = 1100; б) N = 2, S = 2000; в) N = 3, S = 805; г) N = 1, S = 1700?
а) Да, так как при одной операции максимальное расстояние увеличивается на 1, то после одной операции максимальное расстояние может быть максимум 2016-1=2015, что больше 1100.
б) Нет, так как после двух операций максимальное расстояние увеличивается на 2, то после двух операций максимальное расстояние может быть максимум 2016-2=2014, что меньше 2000.
в) Нет, так как после трех операций максимальное расстояние увеличивается на 3, то после трех операций максимальное расстояние может быть максимум 2016-3=2013, что меньше 805.
г) Да, так как при одной операции максимальное расстояние увеличивается на 1, то после одной операции максимальное расстояние может быть максимум 2016-1=2015, что больше 1700.
а) Да, так как при одной операции максимальное расстояние увеличивается на 1, то после одной операции максимальное расстояние может быть максимум 2016-1=2015, что больше 1100.
б) Нет, так как после двух операций максимальное расстояние увеличивается на 2, то после двух операций максимальное расстояние может быть максимум 2016-2=2014, что меньше 2000.
в) Нет, так как после трех операций максимальное расстояние увеличивается на 3, то после трех операций максимальное расстояние может быть максимум 2016-3=2013, что меньше 805.
г) Да, так как при одной операции максимальное расстояние увеличивается на 1, то после одной операции максимальное расстояние может быть максимум 2016-1=2015, что больше 1700.