Чтобы квадрат вписался в круг, его диагональ должна быть равна диаметру круга. Если трактовать "уместиться" как "пролезть", то диагональ должна быть меньше диаметра.. Формулы площадей квадрата S₁ и круга S₂ известны, что легко позволяет нам найти нужное условие. Если нужно, чтобы случай, когда квадрат вписан в круг тоже учитывался, строгое неравенство следует заменить нестрогим.
// PascalABC.NET 3.0, сборка 1160 от 05.02.2016 begin var s1:=ReadReal('Площадь квадрата'); var s2:=ReadReal('Площадь круга'); if pi*s1<2*s2 then Writeln('Квадрат умещается в круге') else Writeln('Квадрат не умещается в круге') end.
Тестовое решение: Площадь квадрата 24.6 Площадь круга 28.4 Квадрат не умещается в круге
Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в i-ой компоненте связности вершин, то общее число рёбер будет суммой по всем компонентам связности:
Требуется найти максимум этого выражения (т.е. на самом деле - максимум суммы квадратов) при условии, что сумма всех ni равна N и ni - натуральные числа.
Если K = 1, то всё очевидно - ответ N(N - 1)/2. Пусть K > 1.
Предположим, n1 <= n2 <= ... <= nK - набор чисел, для которых достигается максимум, и n1 > 1. Уменьшим число вершин в первой компоненте связности до 1, а оставшиеся вершины "перекинем" в K-ую компоненту связности. Вычислим, как изменится сумма квадратов: Поскольку по предположению n1 > 1 (тогда и nK > 1), то сумма квадратов увеличится, что противоречит предположению о том, что на выбранном изначально наборе достигается максимум. Значит, максимум достигается, если наименьшая по размеру компонента связности - изолированная вершина. Выкинем эту компоненту связности, останутся K - 1 компонента связности и N - 1 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.
вершин, то общее число рёбер будет суммой по всем компонентам связности:
Формулы площадей квадрата S₁ и круга S₂ известны, что легко позволяет нам найти нужное условие.
Если нужно, чтобы случай, когда квадрат вписан в круг тоже учитывался, строгое неравенство следует заменить нестрогим.
// PascalABC.NET 3.0, сборка 1160 от 05.02.2016
begin
var s1:=ReadReal('Площадь квадрата');
var s2:=ReadReal('Площадь круга');
if pi*s1<2*s2 then Writeln('Квадрат умещается в круге')
else Writeln('Квадрат не умещается в круге')
end.
Тестовое решение:
Площадь квадрата 24.6
Площадь круга 28.4
Квадрат не умещается в круге