// PascalABC.NET 3.0, сборка 1076 begin var n:=ReadInteger('Введите количество элементов массива: '); var a:=ArrRandom(n,1000,10000); Write('Исходный массив: ',a,#13#10); Write('Множество цифр из разряда сотен: '); a.Select(x->(x mod 1000) div 100).Sorted.Distinct.Println(',') end.
Тестовое решение: Введите количество элементов массива: 8 Исходный массив: [9374,4420,8856,8274,7555,2461,8302,6325] Множество цифр из разряда сотен: 2,3,4,5,8
2. "Школьный вариант"
// PascalABC.NET 3.0, сборка 1076 var i,n:integer; sd:set of 0..9; a:array[1..50] of integer; begin Write('Введите количество элементов массива: '); Read(n); Randomize; Write('Исходный массив: '); sd:=[]; for i:=1 to n do begin a[i]:=Random(9001)+1000; Write(a[i],' '); Include(sd,(a[i] mod 1000) div 100) end; Writeln; Write('Множество цифр из разряда сотен: '); for i:=0 to 9 do if i in sd then Write(i:2); Writeln end.
Тестовое решение: Введите количество элементов массива: 8 Исходный массив: 5332 4215 7231 3399 6989 8904 7804 3517 Множество цифр из разряда сотен: 2 3 5 8 9
Каждая из компонент связности должна быть кликой (иначе говоря, каждые две вершины в одной компоненте связности должны быть связаны ребром). Если в 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.0, сборка 1076
begin
var n:=ReadInteger('Введите количество элементов массива: ');
var a:=ArrRandom(n,1000,10000);
Write('Исходный массив: ',a,#13#10);
Write('Множество цифр из разряда сотен: ');
a.Select(x->(x mod 1000) div 100).Sorted.Distinct.Println(',')
end.
Тестовое решение:
Введите количество элементов массива: 8
Исходный массив: [9374,4420,8856,8274,7555,2461,8302,6325]
Множество цифр из разряда сотен: 2,3,4,5,8
2. "Школьный вариант"
// PascalABC.NET 3.0, сборка 1076
var
i,n:integer;
sd:set of 0..9;
a:array[1..50] of integer;
begin
Write('Введите количество элементов массива: '); Read(n);
Randomize;
Write('Исходный массив: ');
sd:=[];
for i:=1 to n do begin
a[i]:=Random(9001)+1000;
Write(a[i],' ');
Include(sd,(a[i] mod 1000) div 100)
end;
Writeln;
Write('Множество цифр из разряда сотен: ');
for i:=0 to 9 do
if i in sd then Write(i:2);
Writeln
end.
Тестовое решение:
Введите количество элементов массива: 8
Исходный массив: 5332 4215 7231 3399 6989 8904 7804 3517
Множество цифр из разряда сотен: 2 3 5 8 9