Скорость передачи данных через absl сокдинение равна 1 бит/с. определите наибольший размер файла в байтах который может быть передан через данное соединение за 11 секунд​

Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в 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 вершина. Будем продолжать так делать, пока не останется одна вершина, тогда получится, что во всех компонентах связности кроме последней должно быть по одной вершине.

Итак, должно выполняться


Подставив в исходную формулу, получаем


Это и есть ответ.

// PascalABC.NET 3.1, сборка 1200 от 13.03.2016
begin
  var a:=MatrixRandom(7,7,0,9);
  var k:=0;
  for var i:=0 to 6 do begin
    for var j:=0 to 6 do begin
      Write(a[i,j]:3);
      if a[i,j] in [1..5] then Inc(k)
      end;
    Writeln
    end;
  Writeln('Кол-во элементов на [1,5]: ',k)
end.

Тестовое решение:
  2  1  7  3  3  2  7
  9  2  9  2  0  5  5
  4  2  6  9  4  6  0
  1  0  3  5  4  5  9
  6  3  6  0  2  0  8
  0  8  4  3  2  1  8
  6  0  4  4  5  4  0
Кол-во элементов на [1,5]: 27

Вариант "совсем для школы"

const
  n=7;
var
  a:array[1..n,1..n] of integer;
  i,j,k:integer;
begin
  Randomize;
  k:=0;
  for i:=1 to n do begin
    for j:=1 to n do begin
      a[i,j]:=Random(10);
      Write(a[i,j]:3);
      if a[i,j] in [1..5] then Inc(k)
      end;
    Writeln
    end;
  Writeln('Кол-во элементов на [1,5]: ',k)
end.