Решение задач блока ExamBegin 51-60

Решение задач из задачника по программированию М. Э. Абрамяна. Задачи из блока ExamBegin: «ЕГЭ по информатике: базовые алгоритмы».

Задача ExamBegin51

На вход в первой строке подается целое положительное число N, а во второй строке — массив из N целых чисел. Выполнив однократный просмотр массива, найти количество его минимальных элементов.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  n, i, min, k: integer;
 
begin
  Task('ExamBegin51');
  k := 0;
  Readln(n);
  min := maxint;
  for i := 1 to n do
  begin
    Read(m[i]);
    if min > m[i] then
    begin
      min := m[i];
      k := 0;
    end;
    if min = m[i] then k := k + 1;
  end;
  Write(k);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  n, i, min, k: integer;
 
begin
  Task('ExamBegin51');
  k := 0;
  Readln(n);
  min := maxint;
  for i := 1 to n do
  begin
    Read(m[i]);
    if min > m[i] then
    begin
      min := m[i];
      k := 0;
    end;
    if min = m[i] then k := k + 1;
  end;
  Write(k);
end.

Задача ExamBegin52

На вход в первой строке подается целое четное положительное число N, а во второй строке — массив из N целых чисел. Группируя элементы массива по парам (первый-второй, третий-четвертый и т. д.), найти за однократный просмотр массива количество пар с максимальной суммой и вывести в первой строке максимальную сумму, а во второй строке — количество пар с этой суммой.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  n, i, sum, max, k, l: integer;
 
begin
  Task('ExamBegin52');
  k := 0;
  Readln(n);
  for i := 1 to n do Read(m[i]);
  max := m[1] + m[2];
  for i := 1 to n div 2 do
  begin
    l := i * 2;
    sum := m[l] + m[l - 1];
    if max < sum then
    begin
      max := sum;
      k := 0;
    end;
    if sum = max then k := k + 1;
  end;
  Writeln(max);
  Writeln(k);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  n, i, sum, max, k, l: integer;
 
begin
  Task('ExamBegin52');
  k := 0;
  Readln(n);
  for i := 1 to n do Read(m[i]);
  max := m[1] + m[2];
  for i := 1 to n div 2 do
  begin
    l := i * 2;
    sum := m[l] + m[l - 1];
    if max < sum then
    begin
      max := sum;
      k := 0;
    end;
    if sum = max then k := k + 1;
  end;
  Writeln(max);
  Writeln(k);
end.

Задача ExamBegin53

На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N различных вещественных чисел. Выполнив однократный просмотр массива, найти два его наименьших элемента и вывести эти элементы в порядке возрастания их значений (каждый элемент выводить на новой строке).

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of real;
  n, i: integer;
  min1, min2: real;
 
begin
  Task('ExamBegin53');
  Readln(n);
  for i := 1 to n do Read(m[i]);
  min1 := m[1]; min2 := m[2];
  for i := 1 to n do
  begin
    if min1 > m[i] then begin
      min2 := min1;
      min1 := m[i];
    end;
    if (min2 > m[i]) and (min1 < m[i]) then
      min2 := m[i];
  end;
  Writeln(min1:2:2);
  Writeln(min2:2:2);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of real;
  n, i: integer;
  min1, min2: real;
 
begin
  Task('ExamBegin53');
  Readln(n);
  for i := 1 to n do Read(m[i]);
  min1 := m[1]; min2 := m[2];
  for i := 1 to n do
  begin
    if min1 > m[i] then begin
      min2 := min1;
      min1 := m[i];
    end;
    if (min2 > m[i]) and (min1 < m[i]) then
      min2 := m[i];
  end;
  Writeln(min1:2:2);
  Writeln(min2:2:2);
end.

Задача ExamBegin54

На вход в первой строке подается целое число N (> 2), а во второй строке — массив из N целых чисел, среди которых имеется не менее трех различных. Выполнив однократный просмотр массива, найти три его наибольших элемента с различными значениями и вывести эти элементы в порядке убывания их значений (каждый элемент выводить на новой строке).

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  min, max1, max2, max3, i, n: integer;
 
begin
  Task('ExamBegin54');
  Readln(n);
  min := maxint;
  for i := 1 to n do
  begin
    Read(m[i]);
    if min > m[i] then min := m[i];
  end;
  max1 := min; max2 := min; max3 := min;
  for i := 1 to n do
  begin
    if max1 < m[i] then begin
      max3 := max2;
      max2 := max1;
      max1 := m[i];
    end;
    if (max2 < m[i]) and (max1 > m[i]) then begin
      max3 := max2;
      max2 := m[i];
    end;
    if (max3 < m[i]) and (max2 > m[i]) then
      max3 := m[i];
  end;
  Writeln(max1);
  Writeln(max2);
  Writeln(max3);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  min, max1, max2, max3, i, n: integer;
 
begin
  Task('ExamBegin54');
  Readln(n);
  min := maxint;
  for i := 1 to n do
  begin
    Read(m[i]);
    if min > m[i] then min := m[i];
  end;
  max1 := min; max2 := min; max3 := min;
  for i := 1 to n do
  begin
    if max1 < m[i] then begin
      max3 := max2;
      max2 := max1;
      max1 := m[i];
    end;
    if (max2 < m[i]) and (max1 > m[i]) then begin
      max3 := max2;
      max2 := m[i];
    end;
    if (max3 < m[i]) and (max2 > m[i]) then
      max3 := m[i];
  end;
  Writeln(max1);
  Writeln(max2);
  Writeln(max3);
end.

Задача ExamBegin55

На вход в первой строке подается целое положительное число N, а во второй строке — массив из N вещественных чисел. Выполнив однократный просмотр массива, найти максимальное количество подряд идущих положительных элементов. Если положительных элементов нет, то вывести 0.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of real;
  i, n, k, max: integer;
 
begin
  Task('ExamBegin55');
  Readln(n);
  k := 0; max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if m[i] > 0 then k := k + 1
    else k := 0;
    if k > max then max := k;
  end;
  Write(max);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of real;
  i, n, k, max: integer;
 
begin
  Task('ExamBegin55');
  Readln(n);
  k := 0; max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if m[i] > 0 then k := k + 1
    else k := 0;
    if k > max then max := k;
  end;
  Write(max);
end.

Задача ExamBegin56

На вход в первой строке подается целое положительное число N, а во второй строке — массив из N целых чисел. Выполнив однократный просмотр массива, найти максимальное количество подряд идущих одинаковых элементов.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  i, n, k, max: integer;
 
begin
  Task('ExamBegin56');
  Readln(n);
  k := 1; max := 1;
  for i := 1 to n do
    Read(m[i]);
  for i := 1 to n - 1 do
  begin
    if m[i] = m[i + 1] then k := k + 1
    else k := 1;
    if k > max then max := k;
  end;
  Write(max);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  i, n, k, max: integer;
 
begin
  Task('ExamBegin56');
  Readln(n);
  k := 1; max := 1;
  for i := 1 to n do
    Read(m[i]);
  for i := 1 to n - 1 do
  begin
    if m[i] = m[i + 1] then k := k + 1
    else k := 1;
    if k > max then max := k;
  end;
  Write(max);
end.

Задача ExamBegin57

На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N целых чисел. Рассматривая всевозможные пары элементов массива, найти минимальное расстояние между элементами (расстояние между числами x и y равно модулю их разности: |x − y|).

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  i, j, n, k, max, min: integer;
 
begin
  Task('ExamBegin57');
  Readln(n);
  max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if max < m[i] then max := m[i];
  end;
  min := max; k := max;
  for i := 1 to n do
    for j := 1 to n do
      if i <> j then begin
        k := abs(m[i] - m[j]);
        if k < min then min := k;
      end;
  Write(min);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of integer;
  i, j, n, k, max, min: integer;
 
begin
  Task('ExamBegin57');
  Readln(n);
  max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if max < m[i] then max := m[i];
  end;
  min := max; k := max;
  for i := 1 to n do
    for j := 1 to n do
      if i <> j then begin
        k := abs(m[i] - m[j]);
        if k < min then min := k;
      end;
  Write(min);
end.

Выше приведенный листинг с примером решения задачи ExamBegin57 является довольно затратным алгоритмом, основанным на переборе всех возможных пар. Но этот алгоритм можно оптимизировать. Ниже приведен более легкий алгоритм нахождения минимальной разности двух чисел. Давайте рассмотрим его.
Чтобы определить максимальную сумму, надо среди всех чисел найти самое больше число и следующее за ним. Чтобы найти максимальную разность, надо определить максимальное и минимальное число в ряде. Для минимальной суммы нам надо искать самое минимальное число и следующий за ним минимум. Казалось бы, чтобы определить минимальную разность, надо взять минимумы ряда и из одного вычесть другой. Но это будет неверным решением, потому как минимальная разность — это минимальное значение между парой чисел. И обрабатывая числовой ряд мы это значение не найдем.
В любом случае нам нужен будем массив для хранения всех значений. После чего мы этот массив отсортируем используя для этого сортировку пузырьком. Так мы получим ряд друг за другом идущих по возрастанию чисел. Затем, перебирая соседние пары будем находить их разность и искать среди нее минимальную.
С 16 по 30 строку алгоритма мы сортируем массив пузырьком. Для этого используем два цикла. Один внешний, с условием, и второй внутренний со счетчиком. Внешний цикл отвечает за количество пробежек в нашей сортировке, по этому как только мы выстроим массив мы его прерываем меняя логическую переменную check на значение false. Во внутреннем цикле мы перебираем пары элементов, и если левый элемент оказывается больше правого, то меняем их местами. Так же у нас есть счетчик j, который мы увеличиваем при каждой итерации внешнего цикла, т.к. нам нет необходимости делать проверку с крайними правыми числами. Это особенность сортировки пузырьком, т.к. после первого же прогона нашего алгоритма в самую правую ячейку попадет самое больше значение из массива. И так будет происходить при каждой итерации. Поэтому мы и смещаем правую границу при итерации вложенным циклом. Это позволит не делать нам лишние итерации цикла когда они бесполезны.
С 31 по 33 строке мы пробегаемся по массиву и выбираем соседние пары, ищем среди них разность по модулю и среди этих разностей находим самую минимальную, которую запоминаем в переменную min.

uses PT4Exam;
 
const
  P = 100;
 
var
  a: array[1..P] of integer;
  n, i, j, t, min: integer;
  check: boolean;
 
begin
  Task('ExamBegin57');
  read(n);
  for i := 1 to n do
    read(a[i]);
  check := true;
  j := 1;
  while check do
  begin
    check := false;
    for i := 1 to n - j do
      if a[i] > a[i + 1] then
      begin
        t := a[i];
        a[i] := a[i + 1];
        a[i + 1] := t;
        check := true;
      end;
    j := j + 1;
  end;
  min := maxint;
  for i := 1 to n - 1 do
    if abs(a[i] - a[i + 1]) < min then min := abs(a[i] - a[i + 1]);
  write(min);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  a: array[1..P] of integer;
  n, i, j, t, min: integer;
  check: boolean;
 
begin
  Task('ExamBegin57');
  read(n);
  for i := 1 to n do
    read(a[i]);
  check := true;
  j := 1;
  while check do
  begin
    check := false;
    for i := 1 to n - j do
      if a[i] > a[i + 1] then
      begin
        t := a[i];
        a[i] := a[i + 1];
        a[i + 1] := t;
        check := true;
      end;
    j := j + 1;
  end;
  min := maxint;
  for i := 1 to n - 1 do
    if abs(a[i] - a[i + 1]) < min then min := abs(a[i] - a[i + 1]);
  write(min);
end.

Задача ExamBegin58

На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N вещественных чисел. Рассматривая всевозможные пары элементов массива, найти пару ближайших элементов, т. е. элементов, расстояние между которыми минимально (определение расстояния приводится в ExamBegin57). Вывести номера ближайших элементов (элементы нумеруются от 1). Каждый номер выводить на новой строке; первым выводится меньший номер. Предполагается, что в массиве имеется единственная пара ближайших элементов.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of real;
  i, j, n, a, b: integer;
  max, min: real;
 
begin
  Task('ExamBegin58');
  Readln(n);
  max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if max < m[i] then max := m[i];
  end;
  min := max; a := 0; b := 0;
  for i := 1 to n do
    for j := 1 to n do
      if i <> j then
        if abs(m[i] - m[j]) < min then
        begin
          a := i; b := j;
          min := abs(m[i] - m[j]);
        end;
  Writeln(a);
  Writeln(b);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  m: array[1..P] of real;
  i, j, n, a, b: integer;
  max, min: real;
 
begin
  Task('ExamBegin58');
  Readln(n);
  max := 0;
  for i := 1 to n do
  begin
    Read(m[i]);
    if max < m[i] then max := m[i];
  end;
  min := max; a := 0; b := 0;
  for i := 1 to n do
    for j := 1 to n do
      if i <> j then
        if abs(m[i] - m[j]) < min then
        begin
          a := i; b := j;
          min := abs(m[i] - m[j]);
        end;
  Writeln(a);
  Writeln(b);
end.

Задача ExamBegin59

На вход в первой строке подается целое число A, во второй строке — целые положительные числа M и N, а в последующих M строках — двумерный целочисленный массив размера M × N. Найти количество строк массива, содержащих элемент со значением A.

uses PT4Exam;
 
const
  P = 100;
 
var
  arr: array[1..P, 1..P] of integer;
  a, m, n, i, j, k: integer;
  count: boolean;
 
begin
  Task('ExamBegin59');
  Readln(a);
  Readln(m, n);
  k := 0; count := false;
  for i := 1 to m do
  begin
    for j := 1 to n do
    begin
      Read(arr[i, j]);
      if a = arr[i, j] then count := true;
    end;
    if count = true then k := k + 1;
    count := false;
  end;
  Write(k);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  arr: array[1..P, 1..P] of integer;
  a, m, n, i, j, k: integer;
  count: boolean;
 
begin
  Task('ExamBegin59');
  Readln(a);
  Readln(m, n);
  k := 0; count := false;
  for i := 1 to m do
  begin
    for j := 1 to n do
    begin
      Read(arr[i, j]);
      if a = arr[i, j] then count := true;
    end;
    if count = true then k := k + 1;
    count := false;
  end;
  Write(k);
end.

Задача ExamBegin60

На вход в первой строке подаются целые положительные числа M и N, а в последующих M строках — двумерный целочисленный массив размера M × N. Найти количество столбцов массива, содержащих хотя бы одно четное число.

uses PT4Exam;
 
const
  P = 100;
 
var
  arr: array[1..P, 1..P] of integer;
  m, n, i, j, k: integer;
  count: boolean;
 
begin
  Task('ExamBegin60');
  Readln(m, n);
  for i := 1 to m do
    for j := 1 to n do
      Read(arr[i, j]);
  k := 0; count := false;
  for i := 1 to n do
  begin
    for j := 1 to m do
      if arr[j, i] mod 2 = 0 then count := true;
    if count = true then k := k + 1;
    count := false;
  end;
  Write(k);
end.

uses PT4Exam;
 
const
  P = 100;
 
var
  arr: array[1..P, 1..P] of integer;
  m, n, i, j, k: integer;
  count: boolean;
 
begin
  Task('ExamBegin60');
  Readln(m, n);
  for i := 1 to m do
    for j := 1 to n do
      Read(arr[i, j]);
  k := 0; count := false;
  for i := 1 to n do
  begin
    for j := 1 to m do
      if arr[j, i] mod 2 = 0 then count := true;
    if count = true then k := k + 1;
    count := false;
  end;
  Write(k);
end.