Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных В первой строке входных данных задаётся количество чисел
N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
5
34
12
51
52
51
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение:
Разность двух чисел чётна, если эти числа имеют одинаковую чётность.
Будем вводить элементы последовательности по одному и хранить четыре элемента: максимальные чётный m0 и нечётный m1 элементы всей последовательности и максимальные чётный и нечётный элементы, кратные p = 17 (mp0 и mp1 соответственно). При этом у чисел, кратных p, будет «приоритет»: если вновь найденный общий максимум последовательности (с учётом чётности) кратен p, это число будет записано в качестве максимума среди кратных p (mp0 или mp1). В общий максимум (m0 или m1) оно сможет
перейти, только если среди кратных p (mp0 или mp1) появится большее или такое же значение.
После ввода всех элементов нужно найти значения mp0 + m0, mp1 + m1 и выбрать пару с большей суммой. При этом необходимо убедиться, что эти максимумы действительно выбраны из последовательности, а не записаны при инициализации нулевыми или отрицательными значениями.
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
const p = 17; var N: integer; {количество чисел} a: integer; {очередное число} d: integer; {чётность очередного числа} m: array [0..1] of integer; {чётный и нечётный максимумы} mp: array [0..1] of integer; {чётный и нечётный максимумы, кратные p} x, y: integer; {ответ – пара чисел} i: integer; begin m[0] := 0; m[1] := 0; mp[0] := 0; mp[1] := 0; x := 0; y := 0; readln(N); for i := 1 to N do begin readln(a); d := a mod 2; if (a mod p = 0)and(a >= mp[d]) then {нестрогое сравнение!} begin if mp[d] > m[d] then {допустимо нестрогое сравнение} m[d] := mp[d]; mp[d] := a end else if a > m[d] then {допустимо нестрогое сравнение} m[d] := a end; if (mp[0] > 0) and (m[0] > 0) then x := mp[0]; y := m[0]; if (mp[1] > 0) and (m[1] > 0) and (mp[1] + m[1] > x + y) then x := mp[1]; y := m[1]; writeln(x, ' ', y) end. |
Пример 1a. Программа на Алгоритмическом языке. Программа эффективна по времени и памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
алг задача нач цел p = 17| делитель из условия задачи цел N | количество чисел цел a | очередное число цел d | чётность очередного числа целтаб m[0:1] |чётный и нечётный максимумы целтаб mp[0:1] | чётный и нечётный максимумы, кратные p цел x,y | пара чисел для ответа m[0] := 0; m[1] := 0 mp[0] := 0; mp[1] := 0 ввод N нц N раз ввод a d := mod(a,2) если mod(a,p) = 0 и a >= mp[d] | нужно нестрогое сравнение! то если mp[d] > m[d] | допустимо нестрогое сравнение то m[d] := mp[d] все mp[d] := a иначе если a > m[d] | допустимо нестрогое сравнение то m[d] := a все все кц x := 0; y := 0 если mp[0] > 0 и m[0] > 0 то x := mp[0]; y := m[0] все если mp[1] > 0 и m[1] > 0 и mp[1] + m[1] > x + y то x := mp[1]; y := m[1] все вывод x, ' ', y кон |
В приведённом решении вместо массивов m и mp можно использовать две пары простых переменных. В этом случае программа получится более громоздкой (придётся отдельно разбирать случаи чётного и нечётного
чисел в последовательности и дублировать аналогичные фрагменты программы), но останется эффективной. Ниже приводится реализующая такой алгоритм программа на языке Python 3
Пример 2. Программа на языке Python 3. Программа эффективна по времени и памяти
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
p = 17 m0 = m1 = mp0 = mp1 = 0 N = int(input()) for i in range(N): a = int(input()) if a % 2 == 0: if a % p == 0 and a >= mp0: if mp0 > m0: m0 = mp0 mp0 = a elif a > m0: m0 = a else: if a % p == 0 and a >= mp1: if mp1 > m1: m1 = mp1 mp1 = a elif a > m1: m1 = a x = y = 0 if mp0 > 0 and m0 > 0: x = mp0; y = m0 if mp1 > 0 and m1 > 0 and mp1 + m1 > x + y: x = mp1; y = m1 print(x,y) |
Ещё один путь решения – записать всю последовательность в массив и анализировать её в несколько проходов. Ниже приводится реализующая такой алгоритм программа на языке C++. В этой программе массив с исходными данными обрабатывается два раза: на первом проходе находятся индексы максимального чётного и нечётного элементов, кратных p, на втором проходе – общие чётный и нечётный максимумы. При этом элементы, выделенные как кратные при первом проходе, во время второго прохода из
сравнения исключаются. Такая программа эффективна по времени (несмотря на повторную обработку массива, общее время работы пропорционально N), но неэффективна по памяти. Максимальная оценка за такую программу при отсутствии в ней синтаксических и содержательных ошибок – 3 балла
Пример 3. Правильная программа на языке C++, эффективная только по времени
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> using namespace std; int main() { const int p = 17; // делитель int N; cin >> N; // количество элементов int a[N]; // элементы последовательности for (int i = 0; i < N; ++i) cin >> a[i]; int imp0 = -1, imp1 = -1; //индексы максимумов, кратных p for (int i = 0; i < N; ++i) { if (a[i] % p == 0) { if (a[i] % 2 == 0) { if (imp0 == -1 || a[i] > a[imp0]) imp0 = i; } else { if (imp1 == -1 || a[i] > a[imp1]) imp1 = i; } } } int im0 = -1, im1 = -1; // индексы общих максимумов for (int i = 0; i < N; ++i) { if (i != imp0 && i != imp1) { if (a[i] % 2 == 0) { if (im0 == -1 || a[i] > a[im0]) im0 = i; } else { if (im1 == -1 || a[i] > a[im1]) im1 = i; } } } int x = 0, y = 0; // пара чисел для ответа if (imp0 != -1 && im0 != -1) { x = a[imp0]; y = a[im0]; } if (imp1 != -1 && im1 != -1 && a[imp1] + a[im1] > x + y) { x = a[imp1]; y = a[im1]; } cout << x << ' ' << y << endl; return 0; } |
Возможно также «лобовое» решение: запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растут квадратично). Подобная программа оценивается не выше 2 баллов. Ниже приведена реализующая описанный выше алгоритм программа на языке Паскаль (использована версия PascalABC)
Пример 4. Правильная, но неэффективная программа на языке Паскаль
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
const p = 17; var N: integer; {количество чисел} a: array [1..10000] of integer; {исходные данные} x1, x2: integer; {ответ – пара чисел} i,j: integer; begin readln(N); for i := 1 to N do readln(a[i]); x1 := 0; x2 := 0; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i] - a[j]) mod 2 = 0) and ((a[i] mod p = 0) or (a[j] mod p = 0)) and (a[i] + a[j] > x1 + x2) then begin x1 := a[i]; x[2] := a[j] end end end; writeln(x1, ' ', x2) end. |