В ювелирных магазинах продаются изделия четырёх категорий: A, B, С и D. В городе N был проведён мониторинг цен ювелирных изделий в различных магазинах. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять для каждой категории ювелирных изделий, сколько магазинов продают его дороже всего.
Описание входных и выходных данных.
На вход программе в первой строке подаётся число данных N о стоимости ювелирных изделий. В каждой из последующих N строк находится информация в следующем формате: , где — строка, состоящая не более чем из 20 символов без пробелов, —строка, состоящая не более чем из 20 символов без пробелов, —одна из букв—A, B, C или D, —целое число в диапазоне от 2000 до 700 000, обозначающее стоимость одного изделия в рублях.
Пример входных данных:
Кристалл Адамас С 30000
Кристалл Блеск С 30000
Красота Элегант A 5000
Красота Бриллиант А 5000
Шик Классика А 4000
Кристалл Адамас В 10000
Безграничная память. Как запоминать информацию
Программа должна выводить через пробел 4 числа— количество магазинов, продающих дороже всего изделия категории A, B, C и D соответственно. Если ювелирное изделие какой-либо категории нигде не продаётся, то следует вывести 0.
Пример выходных данных:
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N изделиях.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла.
Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Показать ответ
Программа читает все входные данные один раз, сразу подсчитывая в массиве с индексами от A до D количество камней, принадлежащих определённой ценовой категории. Во время чтения данных определяются максимальная цена ювелирных изделий для каждой категории и количество магазинов, продающих изделия по этой цене. Для этого используются 8 переменных или соответствующие массивы.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой категории ювелирных изделий максимальная цена отмечена ровно в одном магазине).
Как Учиться В 2 Раза Быстрее С Техникой Фейнмана (Пример)
Пример правильной и эффективной программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var max, kcenkat: array[’A’..’D’] of integer;
c, i, k: char; j, N, b: integer;
Источник: ege-today.ru
Е27.21 Решение задания №27 Досрочный вариант №1 ЕГЭ по информатике 2020
Решение задания №27 Досрочный вариант №1 ЕГЭ по информатике 2020 от ФИПИ. Информатика ЕГЭ 27 задание разбор. Как решать задание №27 ЕГЭ по информатике 2020 г.
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов.
Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных В первой строке входных данных задаётся количество чисел
N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
5
34
12
51
52
51
Пример выходных данных для приведённого выше примера входных данных:
51 51
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (34, 12), (34, 52), (51, 51). Наибольшая сумма получается в паре (51, 51). Эта пара допустима, так как число 51 встречается в исходной последовательности дважды.
Напишите эффективную по времени и памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение:
Разность двух чисел чётна, если эти числа имеют одинаковую чётность.
Будем вводить элементы последовательности по одному и хранить четыре элемента: максимальные чётный m0 и нечётный m1 элементы всей последовательности и максимальные чётный и нечётный элементы, кратные p = 17 (mp0 и mp1 соответственно). При этом у чисел, кратных p, будет «приоритет»: если вновь найденный общий максимум последовательности (с учётом чётности) кратен p, это число будет записано в качестве максимума среди кратных p (mp0 или mp1). В общий максимум (m0 или m1) оно сможет
перейти, только если среди кратных p (mp0 или mp1) появится большее или такое же значение.
После ввода всех элементов нужно найти значения mp0 + m0, mp1 + m1 и выбрать пару с большей суммой. При этом необходимо убедиться, что эти максимумы действительно выбраны из последовательности, а не записаны при инициализации нулевыми или отрицательными значениями.
Пример 1. Программа на языке Паскаль. Программа эффективна по времени и памяти
Источник: informatikaexpert.ru
ЕГЭ по информатике. Задание 27
Задание 27 — «Обработка строк или последовательности чисел». Это задание характеризуется высоким уровнем сложности , время выполнения – 50 минут, максимальный балл — 4.
Конечно, это как-то нечестно, писать сложную программу без возможности ее проверить на компьютере.
Перед написанием программы надо хорошо представлять, что собственно нужно запрограммировать. Причем продумать алгоритм нужно до мелочей, учесть все возможные варианты поведения программы. Обязательно подробно и понятно записать алгоритм на простом языке, в виде блок-схемы, например.
Рассмотрим пример:
На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a[i] и a[j] такие что i < j и a[i] >a[j] (первый элемент пары больше второго; i и j – порядковые номера чисел в последовательности входных данных). Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m = 120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел n (2<=n<=12000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10000. В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
Пример входных данных
6
60
140
61
100
300
59
Пример выходных данных для приведённого выше примера входных данных: 300 60.
Пояснение. Из шести заданных чисел можно составить три пары, сумма элементов которых делится на m = 120: 60+300, 140+100 и 61+59. Во второй и третьей из этих пар первый элемент больше второго, но во второй паре сумма больше.
Решение.(привожу на Паскале)
Сумма a[i] и a[j] делится на m, если сумма остатков этих чисел от деления на m равна 0 или m. Для каждого из остатков от деления на m среди уже просмотренных элементов будем хранить максимальное число, имеющее соответствующий остаток от деления на m. Для этого будем использовать массив s длиной m изначально с элементами, равными 0. Все считанные значения при этом можно не хранить.
Очередное считанное число a будем рассматривать как возможный правый элемент искомой пары. Пусть остаток от деления a на m равен p. Тогда если s[m — p] > 0 то сумма a и s[m — p] делится на m и при условии s[m — p]>a эта пара – вариант для ответа. Если их сумма больше предыдущего ответа, то заменим его. При этом если остаток от деления a на m равен 0, то рассматривать надо пару a и s[0].
По окончании обработки элемента a необходимо обновить элемент s[p] значением a, если a > s[p].
const m = 120;
var
s: array[0..m-1] of integer;
n, a, i, p, left, right: integer;
begin
readln(n);
for i := 0 to m — 1 do
s[i] := 0; массива>
left := 0; right := 0; переменных для записи ответа>
for i := 1 to n do
begin
readln(a);
p := a mod m;
if p = 0 then
begin
if (s[0] > a) and (s[0] + a > left + right) then
begin
left := s[0]; right := a
end
end
else
begin
if (s[m — p] > a) and (s[m — p] + a > left + right) then
begin
left := s[m — p]; right := a
end;
end;
if a > s[p] then s[p] := a элемента для остатка>
end;
writeln(left, ‘ ‘,right)
end.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, 4 балла.
Максимальная оценка за правильную программу, возможно, неэффективную по памяти или время выполнения которой существенно зависит от величины m, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Описание алгоритма решения без программы оценивается в 0 баллов.
Если остались вопросы, пишите в комментариях. Обязательно отвечу. Если нужно разобрать конкретный пример, также — в комментарии.
Еще больше интересного материала в группе в ВК и на сайте . Кроме этого, можете воспользоваться услугами репетитора .
Источник: dzen.ru