Информатика ЕГЭ 27 задание разбор

✎ Программа эффективна по времени и по памяти (4 балла):

Язык Паскаль (версия PascalABC):

var N: integer; a: integer; n58, n29, n2: integer; k58: integer; i: integer; begin readln(N); n58 := 0; n29 := 0; n2 := 0; for i := 1 to N do begin readln(a); if a mod 58 = 0 then n58 := n58 + 1 else if a mod 29 = 0 then n29 := n29 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k58 := n58 * (n58 - 1) div 2 + n58 * (N - n58) + n2 * n29; writeln(k58) end.

n=int(input()) n58,n29,n2=0,0,0 for i in range(n): a=int(input()) if a % 28 == 0: n58+=1 elif a % 29 == 0: n29+=1 elif a % 2 == 0: n2+=1 k58=n58 * (n58-1) // 2 + n58 * (n-n58) + n2 * n29 print(k58)

1. n58 — количество чисел, кратных 58;
2. n29 —количество чисел, кратных 29, но не кратных 2 и 58;
3. n2 — количество чисел, кратных 2, но не кратных 29 и 58.

✎ Программа неэффективная (2 балла):

Язык Паскаль (версия PascalABC):

var i, j, k, n: integer; a: array[1..1000]of integer;//очередное значение begin readln(n); for i := 1 to n do begin readln(a[i]); end; k := 0; for i := 1 to n - 1 do for j := i + 1 to n do if a[i] * a[j] mod 58 = 0 then k := k + 1; writeln(k); end.

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.

Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

Из них на 26 делятся 4 произведения:

Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.

Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно). А. Оба сомножителя делятся на 26. Б. Один из сомножителей делится на 26, а другой не делится. В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой – на 13.

При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения: 1) n26 – количество чисел, кратных 26; 2) n13 – количество чисел, кратных 13, но не кратных 26; 3) n2 – количество чисел, кратных 2, но не кратных 26.

✎ Программа эффективна и по времени, и по памяти (4 балла): Программа на языке Паскаль (версия PascalABC):

var N: integer; a: integer; n26, n13, n2: integer; k26: integer; i: integer; begin readln(N); n26 := 0;n13 := 0;n2 := 0; for i := 1 to N do begin readln(a); if a mod 26 = 0 then n26 := n26 + 1 else if a mod 13 = 0 then n13 := n13 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k26 := n26 * (n26 - 1) div 2 + n26 * (N - n26) + n2 * n13; writeln(k26) end.

Программа на языке Python (версия Python 3):

n=int(input()) n26,n13,n2=0,0,0 for i in range(n): a=int(input()) if a % 26 == 0: n56+=1 elif a % 13 == 0: n13+=1 elif a % 2 == 0: n2+=1 k26=n26 * (n26-1) // 2 + n26 * (n-n26) + n2 * n13 print(k26)

Программа на языке Бейсик:

N26 = 0 N2 = 0 N13 = 0 NX = 0 INPUT N FOR I = 1 TO N INPUT A IF A MOD 26 = 0 THEN N26 = N26 + 1 ELSE IF A MOD 13 = 0 THEN N13 = N13 + 1 ELSE IF A MOD 2 = 0 THEN N2 = N2 + 1 ELSE NX = NX + 1 END IF END IF END IF NEXT I K26 = N26*(N26 - 1)\2 + N26*(N2 + N13 + NX) + N2*N13 PRINT K26

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 19. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000. Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

Напишите эффективную по времени и памяти программу для решения этой задачи.

Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.

• ✎ Программа эффективна по времени и памяти

const p = 19; var N: integer; a: integer; m0, m1: integer; mp0, mp1: integer; x, y: integer; i: integer; begin m0 := 0; m1 := 0; mp0 := 0; mp1 := 0; x := 0; y := 0; readln(N); for i := 1 to N do begin readln(a); // для четных if a mod 2 = 0 then begin // если кратное if (a mod p = 0) and (a >= mp0) then begin if mp0 > m0 then m0:= mp0; mp0:=a end else if a > m0 then m0 := a; end else begin // для нечетных if (a mod p = 0)and(a>=mp1) then begin if mp1>m1 then m1:=mp1; mp1 := a; end else if a>m1 then m1:=a; end; end; // writeln('mp0=', mp0, 'm0=', m0); if (mp0 > 0) and (m0 > 0) then begin x := mp0; y := m0; end; // writeln('mp1=', mp1, 'm1=', m1); if (mp1 > 0) and (m1 > 0) and (mp1 + m1 > x + y) then begin x := mp1; y := m1; end; writeln('=', x, ' ', y) end.

const p = 19; var n, i, x, k19n, k19chet, n19chet, n19n, m1, m2: integer; begin readln(n); readln(x); // обнуление всех переменных k19chet := 0; // четный кратный n19chet := 0; // четный некратный k19n := 0; // нечетный кратный n19n := 0; // нечетный некратный m1 := 0; m2 := 0; // максимальные // цикл до n - 1, т.к. первое число уже считали for i := 1 to n - 1 do begin // проверка, если четный и кратный if (x mod p = 0) and (x mod 2 = 0) and (x > k19chet) then begin k19chet := x; end; // проверка, если четный и некратный if (x mod p <> 0) and (x mod 2 = 0) and (x > n19chet) then begin n19chet := x; end; // проверка, если нечетный и кратный if (x mod p = 0) and (x mod 2 = 1) and (x > k19n) then begin k19n := x; end; // проверка, если нечетный и некратный if (x mod p <> 0) and (x mod 2 = 1) and (x > n19n) then begin n19n := x; end; readln(x); // считываем очередное число // если x кратно и есть такое некратное n19chet, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19chet) mod 2 = 0) and (x + n19chet > m1 + m2) and (n19chet > 0) then begin m1 := x; m2 := n19chet; end; // если x кратно и есть такое некратное n19n, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19n) mod 2 = 0) and (x + n19n > m1 + m2) and (n19n > 0) then begin m1 := x; m2 := n19n; end; // если есть такое кратное k19n, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19n) mod 2 = 0) and (x + k19n > m1 + m2) and (k19n > 0) then begin m1 := x; m2 := k19n; end; // если есть такое кратное k19chet, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19chet) mod 2 = 0) and (x + k19chet > m1 + m2) and (k19chet > 0) then begin m1 := x; m2 := k19chet; end; end; writeln(m1, ' ', m2) end.

p = 19 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 балла.

Язык Pascal (версия PascalABC):

const p = 19; var N: integer; a: array [1..10000] of integer; x, y: integer; i, j: integer; begin readln(N); for i := 1 to N do readln(a[i]); x := 0; y := 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] > x + y) then begin x := a[i]; y := a[j] end end end; writeln(x, ' ', y) end.

Задание А (более легкое, чем Б) Имеется набор данных, состоящий из 5 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеет значения.

Задание Б (более сложное, чем А) Имеется набор данных, состоящих из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Напишите программу для решения этой задачи. Постарайтесь сделать программу эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться на более чем в k раз.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

✎ Задание Б (алгоритм), более сложное, 4 балла:

поскольку в задании указано, что «имеется набор данных, состоящих из пар…», то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:

for i:=1 to n do begin readln(x,y); .

Допустим имеем пары:

if x>y then begin max:=x; min:=y end else begin max:=y;min:=x end;

if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then min_kvadr:=sqr(max) - sqr(min)

if sum mod 2 = 0 then begin if min_kvadr = 1073676289 then sum := 0 else sum:=sum - min_kvadr end;

Эффективная программа на языке Паскаль (версия Pascal ABC):

var n:longint; x,y: integer; max: integer; min: integer; sum:longint; min_kvadr:longint; i:integer; begin sum:=0; readln(n); min_kvadr:=1073676289; for i:=1 to n do begin readln(x,y); if x>y then begin max:=x; min:=y end else begin max:=y;min:=x end; sum:=sum+sqr(max); if((max-min) mod 2 > 0) and (sqr(max)-sqr(min) < min_kvadr) then min_kvadr:=sqr(max) - sqr(min) end; if sum mod 2 = 0 then begin if min_kvadr = 1073676289 then sum := 0 else sum:=sum - min_kvadr end; writeln('sum=',sum) end.

Пример работы программы:

✎ Задание А (более легкое, 2 балла максимум):

так как в задании указано, что пар чисел ровно 5, то введем в программу константу n=5

Решение на языке Паскаль (версия PascalABC):

const n = 5; var x,y: longint; max_sum: longint; sum:array [1..15]of longint; i,k:longint; begin readln(x,y); sum[1]:=sqr(x); sum[2]:=sqr(y); k:=3; for i:=2 to n do begin readln(x,y); sum[k]:=sum[k-2]+sqr(x); sum[k+1]:=sum[k-2]+sqr(y); sum[k+2]:=sum[k-1]+sqr(x); sum[k+3]:=sum[k-1]+sqr(y); k:=k+4; end; max_sum:=sum[1]; for i:=1 to n*n do if (sum[i]>max_sum) and (sum[i] mod 2 <>0) then max_sum:=sum[i]; if (max_sum=sum[1]) and (max_sum mod 2 = 0) then max_sum:=0; writeln(max_sum) end.

А. Имеется набор данных, состоящий из 5 троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

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

Б. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

Постарайтесь сделать программу эффективной по времени и по используемой памяти. Программа считается эффективной по времени, если время работы программы пропорционально количеству чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.

Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.

Как в варианте А, так и в варианте Б программа должна напечатать одно число — минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя). Напоминаем! не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию.

Входные данные Для варианта А на вход программе подается 5 строк, каждая из которых содержит три натуральных числа, не превышающих 10000.

Пример входных данных для варианта А:

Для варианта Б на вход программе в первой строке подается количество троек чисел N (1 Показать решение:

✎ Задание Б (4 балла)

Пример правильной и эффективной программы для задания Б на языке Паскаль (версия PascalABC):

const aMax = 10000; var N: longint; a, b, c, tmp: longint; s: longint; D_min: longint; i: longint; begin s := 0; D_min := aMax + 1; readln(N); for i := 1 to N do begin readln(a, b, c); if (a > b) then begin tmp := a;a := b;b := tmp end; if(b > c) then begin tmp := b;b := c;c := tmp; if (a > b) then begin tmp := a;a := b;b := tmp end end; s := s + a; if((b - a) mod 5 > 0 ) and ((b - a) < D_min) then D_min := b - a; if((c - a) mod 5 > 0 ) and ((c - a) < D_min) then D_min := c - a end; if s mod 5 = 0 then begin if D_min > aMax then s := 0 else s := s + D_min end; writeln(s) end.

✎ Задание А (2 балла)

На языке Паскаль (версия PascalABC):

var a: array[1..5, 1..3] of longint; i1, i2, i3, i4, i5: longint; s, sMin: longint; begin for i1 := 1 to 5 do readln(a[i1, 1], a[i1, 2], a[i1, 3]); sMin := 100000; for i1 := 1 to 3 do for i2 := 1 to 3 do for i3 := 1 to 3 do for i4 := 1 to 3 do for i5 := 1 to 3 do begin s := a[1, i1] + a[2, i2] + a[3, i3] + a[4, i4] + a[5, i5]; if (s mod 5 = 0) and (s < sMin) then sMin := s end; if (sMin = 100000) then sMin := 0; writeln(sMin) end.

На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 29.

Описание входных и выходных данных: В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных данных:

Из них на 29 делятся 5 произведений.

Требуется написать эффективную по времени и памяти программу для решения описанной задачи.

✎ Программа на языке Паскаль (версия PascalABC). Программа неэффективна ни по времени, ни по памяти (2 балла):

Перебор всех вариантов произведений:

const s = 4;//требуемое расстояние var n, i, j, cnt: integer; a: array[1..1000] of integer; begin readln(n); cnt := 0; for i := 1 to n do readln(a[i]); for i := 1 to n - s do for j := i + s to n do if a[i] * a[j] mod 29 = 0 then cnt := cnt + 1; writeln(cnt) end.

✎ Программа на языке Паскаль (версия PascalABC). Программа эффективна и по времени, и по памяти (4 балла):

• Если один из сомножителей делится без остатка на 29, то произведение с любым другим сомножителем тоже будет делится на 29.
• Последние рассматриваемые 4 элемента можно хранить как 4 счётчика: количество делящихся на 29 среди всех считанных чисел, всех считанных чисел без последнего, всех считанных чисел без 2 последних, всех считанных чисел без 3 последних, – и также сдвигать их после очередного шага.

const s = 4;//требуемое расстояние var n,i: integer; n1, n2, n3, n4: integer; //хранение последних s счетчиков a_: integer; //очередное значение cnt: integer;//количество искомых пар begin readln(n); n1 := 0;n2 := 0;n3 := 0;n4 := 0; cnt := 0; for i := 1 to n do begin readln(a_); // очередное значение if i > s then if a_ mod 29 = 0 then cnt := cnt + (i - s) else cnt := cnt + n4; // сдвигаем элементы счетчика n4 := n3; n3 := n2; n2 := n1; // обновляем счетчик кратных 29 if a_ mod 29 = 0 then n1 := n1 + 1; end; writeln(cnt) end.

Видео на RuTube здесь

Датчик передаёт каждую секунду по каналу связи неотрицательное целое число, не превосходящее 1000, — текущий результат измерений. Временем, в течение которого происходит передача, можно пренебречь. Необходимо найти в заданной серии показаний датчика минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 8 секунд. Если получить такое произведение не удаётся, ответ считается равным -1. Общее количество показаний датчика в серии не превышает 10 000.

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.

Пример входных данных:

Программа должна вывести одно число — описанное в условии произведение, либо -1, если получить такое произведение не удаётся. Пример выходных данных для приведённого выше примера входных данных:

✎ Задание А (решение на языке Паскаль, версия pascalABC):Ниже приводится пример переборного решения на Паскале, неэффективного ни по памяти, ни по времени, но являющегося правильным ответом на задание А.

const s = 8; var N: integer; a: array[1..10000] of integer; mp: integer; i, j: integer; begin readln(N); for i := 1 to N do readln(a[i]); mp := 1000 * 1000 + 1; for i := 1 to N - s do begin for j := i + s to N do begin if (a[i] * a[j] mod 2 = 0) and (a[i] * a[j] < mp) then mp := a[i] * a[j] end; end; if mp = 1000 * 1000 + 1 then mp := -1; writeln(mp) end.

✎Задание Б (решение на языке Паскаль, версия pascalABC):

Для каждого показания с номером k, начиная с k = 9, рассмотрим все допустимые по условиям задачи пары, в которых данное показание получено вторым. Минимальное произведение из всех этих пар будет получено, если первым в паре будет взято минимальное подходящее показание среди всех, полученных от начала приёма и до показания с номером k — 8. Если очередное показание чётное, минимальное среди предыдущих может быть любым, если нечётное — только чётным.

Для получения эффективного по времени решения нужно по мере ввода данных помнить абсолютное минимальное и минимальное чётное показание на каждый момент времени, каждое вновь полученное показание умножать на соответствующий ему минимум, имевшийся на 8 элементов ранее, и выбрать минимальное из всех таких произведений. Ниже приводится пример такой программы на Паскале, эффективной по памяти и по времени.

const s = 8; amax = 1001; var N: integer; a: array[1..s] of integer; a_: integer; ma: integer; me: integer; mp: integer; p: integer; i, j: integer; begin readln(N); for i := 1 to s do readln(a[i]); ma := amax;me := amax;mp := amax * amax; for i := s + 1 to N do begin readln(a_); if a[1] < ma then ma := a[1]; if (a[1] mod 2 = 0) and (a[1] < me) then me := a[1]; if a_ mod 2 = 0 then p := a_ * ma else if me < amax then p := a_ * me else p := amax * amax; if (p < mp) then mp := p; for j := 1 to s - 1 do a[j] := a[j + 1]; a[s] := a_ end; if mp = amax * amax then mp := -1; writeln(mp) end.