Задание 27. Программирование. Оптимизация по времени и памяти. ЕГЭ 2020 по информатике
Средний процент выполнения: 14.3%
Ответом к заданию 27 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).
Задачи для практики
Задача 1
Метод кодирования шифром Ришелье заключается в следующем: пусть имеется сообщение, записанное с помощью букв латинского алфавита, и набор перестановок различной длины, тогда к сообщению применяют эти перестановки, разбивая сообщение на части и переставляя в них буквы определённым образом, в результате получают зашифрованное сообщение.
Напишите программу, которая на вход получает сообщение и набор перестановок, и результатом её работы является зашифрованное методом Ришелье сообщение.
Замечание:
1) При шифровании сообщения в нём игнорируются пробелы и знаки препинания, а также все буквы переводятся в прописные.
2) Перестановка длины n — это набор чисел от 1 до n, записанный в определённом порядке. Элементы перестановки вводятся через пробел, а сами перестановки разделены «;».
3) Суммарная длина перестановок совпадает с количеством букв в сообщении и не превышает 250.
Пример: Сообщение "I am happy!" и 2 перестановки "2 3 1; 4 2 1 3 5", тогда сообщение преобразуем к виду "IAMHAPPY", применяя первую перестановку к первым трём буквам, получим "AMI", вторую перестановку к следующим пяти буквам—"PAHPY". В итоге получим "AMIPAHPY".
Решение
Программа на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var n, i, k, l, er:integer; c:char;
mes, chmes, cipher:string;
begin
writeln(’Введите сообщение >’);
readln(mes);
chmes:=’’; l:=Length(mes);
for i := 1 to l do
begin
c:=mes[i];
if((c>=’a’) and (c<=’z’)) or ((c>=’A’)
and (c<=’Z’)) then
chmes:=chmes+UpCase(c)
end;
l:=Length(chmes); i:=0;
writeln(’Введите набор перестановок >’);
mes:=’’; k:=0;
while i
read(c);
if (c<>’;’) and (c<>’ ’) then mes:=mes+c
else
begin
val(mes, n, er);
cipher:=cipher+chmes[k+n];
mes:=’’; i:=i+1;
if c=’;’ then k:=i
end;
end;
read(n);
cipher:=cipher+chmes[k+n];
writeln(cipher);
end.
Задача 2
Метод шифрования гаммированием заключается в следующем: пусть имеется сообщение, записанное с помощью букв латинского алфавита, и задана строка-ключ (строка без пробелов и знаков препинания, записанная прописными буквами), в дальнейшем будем называть её гаммой. Сопоставим буквам латинского алфавита числа A→ 0, B→ 1, . . .Z→ 25.
Шифрование сообщения осуществляется посимвольно путём сложения букв (имеется в виду соответствующих им чисел) сообщения и гаммы, затем берётся остаток от этой суммы по модулю 26 и осуществляется обратное преобразование числа в букву.
Причём, если гамма меньшей длины, чем сообщение, то она продолжается периодически до нужной длины; если гамма имеет большую длину, чем сообщение, то берётся последовательность необходимой длины из её первых букв.
Требуется написать программу, которая читает сообщение из файла message.txt, шифрует его, используя введённую с клавиатуры гамму, и сохраняет результат в файле cipher.txt.
Замечания:
1) При шифровании сообщения в нём игнорируются пробелы и знаки препинания, а также все буквы переводятся в прописные.
2) Можно считать, что сообщение и гамма кодируются в формате ASCII. 3) Длина гаммы не превышает 50 символов.
Пример: Сообщение "I am happy!", гамма "NOT", тогда сообщение преобразуем к виду "IAMHAPPY", продолжим гамму "NOTNOTNO" и после шифрования получим "VOFUOICM".
Решение
Программа на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var i, k, l, n, o, p:integer; c:char;
cipher, gamma:string;
fin, fout:text;
begin
assign(fin, ’c:\message.txt’);
assign(fout, ’c:\cipher.txt’);
reset(fin);
writeln(’Vvedite kluch:’);
readln(gamma);
l:=length(gamma);
for i:= 1 to l do
gamma[i]:=upcase(gamma[i]);
i:=1;
cipher:=’’;
repeat
read(fin, c);
if (c>=’a’) and (c<=’z’) or (c>=’A’)
and (c<=’Z’) then
begin
c:=upcase(c);
k:=ord(c)- ord(’A’);
n:=ord(gamma[i])-ord(’A’);
o:=(k+n) mod 26;
p:= o+ord(’A’);
cipher:=cipher+chr(p);
if i=l then i:=1 else i:=i+1;
end;
until eof(fin);
close(fin);
rewrite(fout);
writeln(fout, cipher);
close(fout);
writeln(cipher);
end.
Задача 3
В ювелирных магазинах продаются изделия четырёх категорий: A, B, С и D. В городе N был проведён мониторинг цен ювелирных изделий в различных магазинах. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять для каждой категории ювелирных изделий, сколько магазинов продают его дешевле всего.
Описание входных и выходных данных.
На вход программе в первой строке подаётся число данных N о стоимости ювелирных изделий. В каждой из последующих N строк находится информация в следующем формате: <Компания> <Магазин> <Категория> <Цена>, где <Компания> — строка, состоящая не более чем из 20 символов без пробелов, <Магазин>—строка, состоящая не более чем из 20 символов без пробелов, <Категория>—одна из букв—A, B, C или D, <Цена>—целое число в диапазоне от 1000 до 500 000, обозначающее стоимость одного изделия в рублях. <Компания> и <Магазин>, <Магазин> и <Категория>, а также <Категория> и <Цена> разделены ровно одним пробелом.
Пример входных данных:
5
Кристалл Адамас С 30000
Кристалл Блеск С 28000
Красота Элегант С 28000
Красота Бриллиант А 5000
Шик Классика А 4000
Кристалл Адамас В 10000
Программа должна выводить через пробел 4 числа— количество магазинов, продающих дешевле всего изделия категории A, B, C и D соответственно. Если ювелирное изделие какой-то категории нигде не продаётся, то следует вывести 0.
Пример выходных данных:
1 1 2 0
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N изделиях.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Во время чтения данных определяются минимальная цена ювелирных изделий каждой категории и количество магазинов, продающих изделия по этой цене. Для этого используются 8 переменных или соответствующие массивы.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой категории ювелирных изделий минимальная цена отмечена ровно в одном магазине).
Пример правильной и эффективной программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var min, kcenkat: array[’A’..’D’] of longint;
c, i, k: char;
j, N, b: integer;
begin
for i:=’A’ to ’D’ do begin
min[i]:=500000;
kcenkat [i]:=0; end;
readln(N);
for j:=1 to N do
begin
repeat
read(c);
until c=’ ’; {считана компания}
repeat
read(c);
until c=’ ’; {считана категория}
readln(k,b);
if min[k]>b then
begin
min[k]:=b; kcenkat[k]:=1
end else
if min[k] = b then kcenkat[k]:= kcenkat[k]+1;
end;
{если ювелирных изделий какой-то категории не было, kcenkat[k] осталось равным 0}
for i:=’A’ to ’D’ do write(kcenkat[i],’ ’)
end.
Задача 4
В ювелирных магазинах продаются изделия четырёх категорий: A, B, С и D. В городе N был проведён мониторинг цен ювелирных изделий в различных магазинах. Напишите эффективную по времени работы и по используемой памяти программу, которая будет определять для каждой категории ювелирных изделий, сколько магазинов продают его дороже всего.
Описание входных и выходных данных.
На вход программе в первой строке подаётся число данных N о стоимости ювелирных изделий. В каждой из последующих N строк находится информация в следующем формате: <Компания> <Магазин> <Категория> <Цена>, где <Компания> — строка, состоящая не более чем из 20 символов без пробелов, <Магазин>—строка, состоящая не более чем из 20 символов без пробелов, <Категория>—одна из букв—A, B, C или D, <Цена>—целое число в диапазоне от 2000 до 700 000, обозначающее стоимость одного изделия в рублях.
<Компания> и <Магазин>, <Магазин> и <Категория>, а также <Категория> и <Цена> разделены ровно одним пробелом.
Пример входных данных:
5
Кристалл Адамас С 30000
Кристалл Блеск С 30000
Красота Элегант A 5000
Красота Бриллиант А 5000
Шик Классика А 4000
Кристалл Адамас В 10000
Программа должна выводить через пробел 4 числа— количество магазинов, продающих дороже всего изделия категории A, B, C и D соответственно. Если ювелирное изделие какой-либо категории нигде не продаётся, то следует вывести 0.
Пример выходных данных:
2 1 2 0.
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N изделиях.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла.
Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Программа читает все входные данные один раз, сразу подсчитывая в массиве с индексами от A до D количество камней, принадлежащих определённой ценовой категории. Во время чтения данных определяются максимальная цена ювелирных изделий для каждой категории и количество магазинов, продающих изделия по этой цене. Для этого используются 8 переменных или соответствующие массивы.
Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, когда для каждой категории ювелирных изделий максимальная цена отмечена ровно в одном магазине).
Пример правильной и эффективной программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var max, kcenkat: array[’A’..’D’] of integer;
c, i, k: char; j, N, b: integer;
begin
for i:=’A’ to ’D’ do
begin
max[i]:=2000;
kcenkat [i]:=0;
end;
readln(N);
for j:=1 to N do
begin
repeat
read(c);
until c=’ ’; {считана компания}
repeat
read(c);
until c=’ ’; {считана категория}
readln(k,b);
if max[k] begin
max[k]:=b;
kcenkat[k]:=1
end
else
if max[k] = b then
kcenkat[k]:= kcenkat[k]+1;
end;
{если ювелирных изделий какой-то категории не было, kcenkat[k] осталось равным 0 }
for i:=’A’ to ’D’
write(kcenkat[i],’ ’)
end.
Задача 5
В 82-квартирном доме проводится проверка долгов жильцов по оплате коммунальных услуг. Для формирования сообщений о накопившемся долге выбираются номера квартир, долг которых больше среднего по всему дому. Если долг квартиры равен среднему по дому, то номер квартиры включается в результирующий набор в том случае, когда средний долг больше минимального долга на 60%. Если долги у всех одинаковые, то выбирается первая половина (начиная с 1-й) квартир-должников и округляется в большую сторону (например, при пяти должниках будут выбраны первые 3 квартиры).
Программа должна выводить номера квартир-должников, подходящих по условию. Гарантируется, что максимальный долг не превышает 3000 рублей и каждая квартира во входных данных присутствует только один раз.
Описание входных и выходных данных.
На вход программы сначала вводится число квартир-должников N. В каждой из следующих N строк находятся сведения о долге одной из квартир в формате:
<Фамилия> <Имя> <квартира> <долг>,
где <Фамилия> — строка, состоящая не более чем из 20 символов, <Имя> — строка, состоящая не более чем из 15 символов, <квартира> — целое положительное число от 1 до 82, <долг> — положительное вещественное число. <Фамилия> и <Имя>, <Имя> и <квартира>, <квартира> и <долг> разделены одним пробелом.
Пример входных данных:
6
Иванов Иван 1 100.00
Петров Николай 2 800.00
Ветров Алексей 3 400.00
Садовой Руслан 4 300.00
Горин Иван 5 0.00
Лебедев Алексей 6 1000.00
Пример выходных данных для приведённого выше примера входных данных:
2
3
6
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N квартирах.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Программа на языке PascalABC 1.8. Программа эффек- тивна по времени и по памяти.
const F=82;
var cnt: array[1..F] of real; c: char;
z, min, midl: real; i, flt, N: integer;
begin
for i := 1 to F do cnt[i] := 0;
readln(N);
midl := 0; min := 3000;
for i := 1 to N do
begin
repeat read(c);
until c = ’ ’; {конец фамилии}
repeat read(c);
until c = ’ ’; {конец имени}
readln(flt, z); {номер квартиры, задолженность}
if z < min then min := z;
midl := midl + z; cnt[flt] := z
end;
midl := midl/N;
flt := 0; i := 1;
if min = midl then
while flt < ((N div 2) + (N mod 2)) do
begin
if cnt[i] > 0 then
begin
write (i, ’ ’); flt := flt + 1
end;
i := i + 1
end
else
for i := 1 to F do
begin
if cnt[i] > midl then write (i, ’ ’);
if (cnt[i]=midl) and (cnt[i]>min*0.6) then
write (i, ’ ’)
end
end.
Задача 6
В 64-квартирном доме проводится проверка долгов жильцов по оплате коммунальных услуг. Для формирования сообщений о накопившемся долге выбираются номера квартир, долг за которые превышает 80% от максимального долга по всем квартирам. Если долги у всех одинаковые, то выбираются первые 60% квартир-должников, начиная с минимального номера (округлять следует в меньшую сторону, например, при шести должниках будут выбраны первые 3 квартиры-должника).
Программа должна выводить номера квартир-должников, подходящих по условию. Гарантируется, что максимальный долг не превышает 3000 рублей и каждая квартира во вводимых данных присутствует только один раз.
Описание входных и выходных данных.
На вход программы сначала подаётся число квартир-должников N. В каждой из следующих N строк находятся сведения о долге одной из квартир в формате: <Фамилия> <Имя> <квартира> <долг>, где <Фамилия>—строка, состоящая не более чем из 20 символов, <Имя>—строка, состоящая не более чем из 15 символов, <квартира>—целое положительное число от 1 до 64, <долг>—положительное вещественное число.
<Фамилия> и <Имя>, <Имя> и <квартира>, <квартира> и <долг> разделены одним пробелом.
Пример входных данных:
6
Иванов Иван 1 120.50
Петров Николай 2 850.00
Ветров Алексей 3 200.00
Садовой Руслан 4 300.00
Горин Иван 5 0.00
Лебедев Алексей 6 1000.00
Пример выходных данных для приведённого выше примера входных данных:
2
6.
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N квартирах.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла.
Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
const F = 64;
var cnt: array[1..F] of real; c : char;
z, max, sum: real; i, flt, N: integer;
begin
for i := 1 to F do cnt[i] := 0;
readln(N);
max:=0; sum:=0;
for i := 1 to N do begin
repeat
read(c);
until c = ’ ’; {конец фамилии}
repeat
read(c);
until c = ’ ’; {конец имени}
readln(flt, z); {номер кв-ры, задолженность}
if z > max then max := z;
sum := sum+z; cnt[flt] := z
end;
flt := 0; i := 1;
if max = sum/N then
while flt <= (N*0.6) do begin
if cnt[i] > 0 then begin
write (i, ’ ’);
flt := flt + 1
end;
i := i + 1
end
else
for i := 1 to F do
if cnt[i] > max*0.8 then
write (i, ’ ’);
end.
Задача 7
На сортировочной станции данные по каждому товару содержат следующую информацию: код страны-отправителя (строка без пробелов, длиной не более 10 символов, начинающаяся с латинских символов, соответствующих стране), код страны-адресата (строка без пробелов, длиной не более 10 символов, начинающаяся с латинских символов, соответствующих стране), код товара (строка без пробелов, длиной не более 10 символов, начинающаяся с латинских символов, соответствующих наименованию товара), семизначный регистрационный номер. Аббревиатурой товара является трёхсимвольный код, состоящий из трёх заглавных латинских букв—первых букв кода страны отправителя, кода страны адресата и кода товара.
Требуется написать программу, которая определит информацию по тем товарам, которые имеют заданную аббревиатуру. Информацию о товаре следует выдать в порядке убывания частоты его встречаемости в списке. Описание входных и выходных данных.
На вход программе в первой строке подается аббревиатура товара.
Количество товара в списке с такой аббревиатурой не больше 20. Во второй строке находится число N — количество товаров, полученных в результате анализа списка, не все из них подходят под указанную аббревиатуру. Значение N может быть очень велико. В каждой из следующих N строк записано три слова: код страны-отправителя, код страныадресата и код соответствующего товара. Слова разделяются одним пробелом. В конце и в начале строки пробелов нет. Все символы в списке записаны заглавными латинскими буквами. Гарантируется, что в списке хотя бы один товар с нужной аббревиатурой есть.
Пример входных данных:
FBT
5
FR742 BEL1254 TR4587 1236547
RU1254 FR4567 GT12454 1236548
FR654 GER4526 LK1245 1236549
FR742 BEL1254 TR4587 1236550
FIN1254 BUL252 TW1247 1236551
Пример выходных данных для приведённого выше примера входных данных:
FR742 BEL1254 TR4587 2
FIN1254 BUL252 TW1247 1
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N товарах.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var N, k, k1, i, j, L : integer;
{Массив для хранения информации о товаре }
Tov: array[1..20] of string;
{Массив для хранения информации о количестве одинакового товара }
Kol : array [1..20] of integer;
abr:string[3]; s1,s:string[40];
begin
writeln(’Введите аббревиатуру’);
readln(abr);
writeln(’Введите количество элементов списка’);
readln(N);
L := 0; i:=1;
{Считываем очередную информацию о товаре и проверяем совпадение первой буквы с первой буквой аббревиатуры.Если нет совпадения, считываем следующие данные списка.}
while i<=N do
begin
readln(s);
if s[1]<>abr[1] then i:=i+1 else
begin
s1:=s;
k:=pos(’ ’,S);
delete(s1,1,k);
k1:=pos(’ ’,S1);
{Проверяем на совпадение с заданной аббревиатурой.}
if (s[k+1]=abr[2]) and (s[k+k1+1]=abr[3]) then
begin
S:=copy(s,1,length(s)-8);
{Осуществляем поиск данных о товаре среди введённых ранее и подсчитываем количество совпадающей информации.}
j := 1;
while (j<=L) and (s<>Tov[j]) do j:=j+1;
if j<=L then
Kol[j]:=Kol[j]+1
else begin
Tov[j]:=s; Kol[j]:=1; L:=L+1
end
end;
i:=i+1
end
end;
{Выводим на экран значения массивов Tov и Kol в порядке убывания значений массива Kol. Для этого, начиная с первого элемента, находим наибольший элемент массива Kol и выводим на экран этот элемент и соответствующий ему элемент массива Tov.На место найденного элемента ставим первый. Далее находим наибольший, начиная со второго элемента массива Kol, и т. д.}
for i:=1 to L-1 do
begin
n:=kol[i]; k:=i;
for j:=i+1 to L do
begin
if n
n:=kol[j]; k:=j;
end;
end;
writeln(’Tov=’,Tov[k], ’ k=’,Kol[k]);
Kol[k]:=Kol[i];
Tov[k]:=Tov[i];
end;
writeln(’Tov=’,Tov[L], ’ k=’,Kol[L]);
end.
Задача 8
Требуется написать программу, которая будет осуществлять стратегию покупки всех возможных акций, стоимость которых не превышает приемлемой цены 240, и выводить на экран информацию о количестве и средней стоимости всех приобретённых акций. Гарантируется, что будет куплена хотя бы 1 акция.
Описание входных и выходных данных.
На вход программе подаются сведения об акциях, которыми торгуют на фондовой бирже NASDAQ. В первой строке сообщается количество акций N (N > 100 000), каждая из следующих N строк имеет формат <Название Акции> <Тип Операции> <Цена>, где <Название Акции> — строка, состоящая не более чем из 4 символов, <Тип Операции> — строка, состоящая из символа «s» или «b», причём символ «s» означает, что данную акцию можно продать по указанной цене, а символ «b»—то, что данную акцию можно купить по указанной цене,<Цена>— не более чем трёхзначное целое число. <Название Акции> и <Тип Операции>, а также <Тип Операции> и <Цена> разделены одним пробелом.
Пример входных данных:
4
MSFT b 26
QQQ s 56
APP b 389
HP s 59
Пример выходных данных:
совершена 1 операция по покупке акций
средняя стоимость 1 приобретённой акции 26 долл.
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N акциях.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Программа читает все входные данные один раз, не запоминая их в массиве, а запоминая только тип операции над акцией и цену, соответствующую данной акции.Программа производит покупку акции, если тип операции с ней соответствует покупке и если цена покупки не превышает приемлемой цены 240. При покупке акции увеличивается количество и общая стоимость всех приобретённых акций. В конце выводится число всех приобретённых акций, а также средняя стоимость одной проибретённой акции.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var i, k, N, p: integer;
s: real; c: char;
begin
readln(N); {считано количество акций}
s := 0; {общая стоимость приобретённых акций}
k := 0; {количество приобретённых акций}
for i := 1 to N do
begin
repeat
read(c);
until c = ’ ’; {считано название акции}
read(c); {считан тип операции}
if c = ’b’ then begin
read(c); readln(p);
{сравниваем текущую цену с приемлемой ценой 240}
if p <= 240 then begin
s := s + p; {покупаем акцию}
k := k + 1; {увеличиваем число имеющихся акций}
end;
end;
end;
writeln(’совершено ’,k,’операций по покупке акций’);
writeln(’средняя стоимость 1 приобр. акции - ’,s/k);
end.
Задача 9
У Димы есть много книг, которые он ещё не прочитал. Дима обожает толстые старые книги. Кроме того, он не любит произведения с длинными названиями. В очередной раз, когда ему надо было выбрать себе книгу, он решил воспользоваться помощью компьютера. Мальчик составил список непрочитанных книг и определил критерии, по которым необходимо выбрать книгу: год издания должен быть ранее 1980-го, количество страниц—не менее 400, а название должно быть по возможности самым коротким из названий книг, удовлетворяющих первым двум условиям. Гарантируется, что хотя бы одна книга удовлетворяет перечисленным критериям.
Программа должна выводить количество книг в списке, изданных ранее 1980 г. и содержащих не менее 400 страниц, а также наименование книги с самым коротким названием.
Описание входных и выходных данных.
На вход программе сначала подаётся число имеющихся у Димы книг N. В каждой из следующих N строк находится описание какой-либо книги в следующем формате:
<Фамилия автора> <Год издания> <Кол-во страниц> <Название>, где <Год издания>, <Кол-во страниц>—целые числа;
<Фамилия автора> — строка без пробелов, состоящая не более чем из 20 символов;
<Название>—строка, состоящая не более чем из 40 символов. <Фамилия автора>, <Год издания>, <Кол-во страниц>, <Название> разделены между собой одним пробелом.
Пример входных данных:
5
Теккерей 1986 736 Ярмарка тщеславия
Булычев 1976 484 Великий Гусляр
Днепров 1974 798 Глиняный бог
Брэдбери 1964 368 Марсианские хроники
Казанцев 1988 637 Клокочущая пустота
Пример выходных данных для приведённого выше примера входных данных:
2
Глиняный бог
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N книгах.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Программа читает все входные данные один раз. При прочтении данных очередной книги сразу проверяются условия: издана ли эта книга ранее 1980 года и содержит ли она не менее 400 страниц. Если оба условия одновременно выполняются, то значение счётчика увеличивается на единицу и проверяется условие: является ли название такой книги меньше уже просмотренных. В результате прочтения данных обо всех книгах становятся известны количество искомых книг и самое короткое название.
Пример программы на языке PascalABC 1.8.Программа эффективна по времени и по памяти.
var c: Char;
s, ms: string;
i, y, p, N, k, ml: Integer;
begin
Readln(N);
ml := 41; k := 0;
for i:=1 to N do
begin
repeat
Read(c);
until c=’ ’; {считана фамилия}
Read(y); Read(p);
Readln(s);
if (y < 1980) and (p >= 400) then
begin
Inc(k);
if Length(s) < ml then
begin
ml := Length(s);
ms := s;
end;
end;
end;
Writeln(k);
Writeln(ms)
end.
Задача 10
Для автоматизированной системы управления движением городских пассажирских автобусов требуется написать программу, которая решает следующую задачу.
На некоторой остановке в течение одного часа для каждого пассажирского автобуса фиксируется время прибытия в минутах (целое число от 0 до 60), номер маршрута (целое число), название предприятия (текстовая строка в 20 символов). Все автобусы одного маршрута принадлежат одному предприятию; одно предприятие может обслуживать несколько маршрутов. Для каждого маршрута задан плановый интервал движения в минутах (целое число от 5 до 15) — промежуток времени между моментами прихода автобусов данного маршрута. Если автобусы некоторого маршрута допускают интервал движения, превышающий плановый более чем на 2 минуты, то на предприятие начисляется по одному штрафному баллу за каждую минуту.
Необходимо вывести на экран список маршрутов и предприятий, чьи автобусы допустили нарушения, и число штрафных баллов в виде: <номер маршрута> <название предприятия> <число штрафных баллов>.
Описание входных и выходных данных.
Исходные данные вводятся в компьютер в следующем порядке.
Сначала вводится число M — число маршрутов, проходящих через данную остановку, а затем вводится M строк вида: <номер маршрута> <интервал движения> <название предприятия>.
Здесь <номер маршрута> — разные целые числа в количестве М, <интервал движения> — целые числа от 5 до 15, <название предприятия>—строка символов, не более 20.
Далее вводится число N — число прошедших через остановку автобусов, затем вводится N строк вида <время прибытия> <номер маршрута>. <Время прибытия> — целые числа от 0 до 60, вводятся в порядке неубывания, <номер маршрута>—целые числа, каждое число обязательно совпадает с одним из номеров маршрута, введённых выше.
Пример входных данных:
3
25 15 Город
37 5 Город
28 15 Смена
8
2 25
5 37
8 28
10 37
17 25
19 37
23 28
32 25
Пример выходных данных для приведённого выше примера входных данных:
37 Город 2
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var Nmar, Id, tpm, Strf: array[1..100] of integer;
Predpr: array[1..100] of string;
M, N, i, j, t,Interv, Nm: integer;
begin
write(’ M = ’);
readln(M);
writeln(’ Nmar Id Predpr’);
for i:=1 to M do
readln(Nmar[i],Id[i],Predpr[i]);
for i:=1 to M do begin
tpm[i]:=0; Strf[i]:=0;
end;
write(’ N = ’);
readln(N);
writeln(’ t Nmar’);
for j:=1 to N do begin
readln(t,Nm);
for i:=1 to M do
if Nm = Nmar[i] then break;
Interv:=t-tpm[i]-Id[i];
if Interv > 2 then
Strf[i]:= Strf[i]+Interv;
tpm[i]:=t;
end;
for i:=1 to M do
if tpm[i]<60 then
begin
Interv:=60-tpm[i]-Id[i];
if Interv > 2 then
Strf[i]:= Strf[i]+Interv;
end;
for i:=1 to M do
write(Nmar[i],’ ’,Strf[i],’ ’,Predpr[i]);
end.
Задача 11
Даны сведения о набранных на ЕГЭ баллах учениками данной школы по трём предметам. Необходимо вывести на экран фамилии и инициалы учеников, набравших максимальную сумму баллов по трём предметам (таких учеников может быть несколько), а также набранную ими сумму баллов.
Описание входных и выходных данных.
На вход программы подаются сведения о набранных на ЕГЭ баллах учениками данной школы по трём предметам. В первой строке сообщается количество учащихся N (N 6 100), каждая из следующих N строк имеет формат: <Фамилия> <Инициалы> <БаллыПоРусскомуЯзыку> <БаллыПоМатематике> <БаллыПоИнформатике>, где <Фамилия>—строка, состоящая не более чем из 20 символов, <Инициалы> — строка, состоящая из 4 символов (буква, точка, буква, точка), <БаллыПоРусскомуЯзыку>, <БаллыПоМатематике>, <БаллыПоИнформатике> — целые числа в диапазоне от 0 до 100. Все элементы одной строки отделены друг от друга пробелом.
Пример входных данных:
5
Петров С.Н. 78 83 70
Киселев К.Н. 56 23 74
Егоров Р.В. 54 47 76
Горин С.М. 25 74 54
Токорев И.Н. 72 75 84
Пример выходных данных для приведённого выше примера входных данных:
Петров С.Н. 231
Токорев И.Н. 231
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N учащихся.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var fio : array[1..100] of string;
bs : array[1..100] of integer;
max,N,i,k,b : integer; c : char;
c : char;
begin
readln(N);
max:=0;
for i:=1 to N do
begin
fio[i]:=’’;
for k:=1 to 2 do
repeat
read(c);
fio[i]:=fio[i]+c;
until c=’ ’;
read(bs[i]);
for k:=1 to 2 do
begin
read(b);
bs[i]:=bs[i]+b;
end;
if bs[i]>max then
max:=bs[i];
end;
for i:=1 to N do
if bs[i]=max then
writeln(fio[i],max);
end.
Задача 12
Даны сведения о набранных на ЕГЭ баллах учениками данной школы по трём предметам. Необходимо вывести на экран фамилии и инициалы учеников, набравших минимальное среднее арифметическое баллов по трём предметам, отличное от 0 (таких учеников может быть несколько), а также среднее арифметическое набранных ими баллов.
Описание входных и выходных данных.
На вход программы подаются сведения о набранных на ЕГЭ баллах учениками данной школы по трём предметам. В первой строке сообщается количество учащихся N (N 6 100), каждая из следующих N строк имеет формат: <Фамилия> <Инициалы> <БаллыПоРусскомуЯзыку> <БаллыПоМатематике> <БаллыПоИнформатике>, где <Фамилия>—строка, состоящая не более чем из 20 символов, <Инициалы> — строка, состоящая из 4 символов (буква, точка, буква, точка), <БаллыПоРусскомуЯзыку>, <БаллыПоМатематике>, <БаллыПоИнформатике> — целые числа в диапазоне от 0 до 100. Все элементы одной строки отделены друг от друга пробелом.
Пример входных данных:
5
Петров С.Н. 78 83 70
Киселев К.Н. 56 23 74
Егоров Р.В. 54 47 76
Горин С.М. 25 74 54
Токорев И.Н. 72 75 36
Пример выходных данных для приведённого выше примера входных данных:
Киселев К.Н. 51
Горин С.М. 51
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N учащихся.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var fio : array[1..100] of string;
bs : array[1..100] of integer;
min,N,i,k,b : integer;
ar : real; c : char;
begin
readln(N);
min:=300;
for i:=1 to N do
begin
fio[i]:=’’;
for k:=1 to 2 do
repeat
read(c);
fio[i]:=fio[i]+c;
until c=’ ’;
read(bs[i]);
for k:=1 to 2 do
begin
read(b);
bs[i]:=bs[i]+b;
end;
readln;
if (bs[i]
min:=bs[i];
end;
ar:=min/3;
for i:=1 to N do
if bs[i]=min then
writeln(fio[i],ar);
end.
Задача 13
Региональный этап олимпиады по экономике проводился для учеников 9–11-х классов, участвующих в общем конкурсе. Каждый участник олимпиады мог набрать от 0 до 50 баллов. Для определения призёров сначала отбираются 45% (с округлением в меньшую сторону) участников, показавших лучшие результаты.
По положению, в случае, если у последнего участника, входящего в 45%, оказывается такое же количество баллов, как и у следующих за ним в итоговой таблице, решение по данному участнику и всем участникам, имеющим с ним равное количество баллов, определяется следующим образом:
— все участники признаются призёрами, если набранные ими баллы больше половины максимально возможных;
— все участники не признаются призёрами, если набранные ими баллы не превышают половины максимально возможных.
Напишите эффективную по времени работы и по используемой памяти программу, которая по результатам олимпиады будет определять, ка- кой минимальный балл нужно было набрать, чтобы стать призёром олимпиады.
Программа должна выводить минимальный балл призёра. Гарантируется, что хотя бы одного призёра по указанным правилам определить можно.
Описание входных и выходных данных.
На вход программе сначала подаётся число участников олимпиады N.
В каждой из следующих N строк находится результат одного из участников олимпиады в следующем формате:
<Фамилия> <Имя> <Класс> <Баллы>, где <Фамилия>—строка, состоящая не более чем из 20 символов;
<Имя>—строка, состоящая не более чем из 15 символов;
<Класс>—число от 9 до 11;
<Баллы>—целое число от 0 до 60 набранных участником баллов.
<Фамилия> и <Имя>, <Имя> и <Класс>, а также <Класс> и<Баллы> разделены одним пробелом.
Пример входных данных:
10
Иванов Пётр 10 47
Капустин Иван 11 35
Никитин Андрей 10 44
Ломов Антон 11 47
Носов Александр 10 32
Егоров Иван 9 30
Городов Михаил 11 44
Васильев Анатолий 10 44
Зоров Денис 10 37
Петров Антон 11 48
Пример выходных данных для приведённого выше примера входных данных:
44
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N участниках олимпиады.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Программа читает все входные данные один раз, сразу подсчитывая в массиве с индексами от 0 до 50 количество участников, набравших тот или иной балл. Путём просмотра этого массива с конца (от 50 баллов) определяется число участников, заведомо попадающих в число 45 % лучших (добавление всех участников, набравших следующий балл, приводит к выходу за 45 %).
Последний балл, который набрали не менее одного участника, запоминается. Если хотя бы один из следующих участников также попадает в 45 %, то проверяется, набрал ли он и следующие, набравшие столько же баллов, более половины баллов.
В этом случае они все добавляются к числу победителей и призёров, и их балл является искомым.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var cnt: array[0..50] of integer;
c: char; i, k, N, b, S, minb: integer;
begin
for i:=0 to 50 do cnt[i]:=0;
readln(N);
for i:=1 to N do begin
repeat
read(c);
until c=’ ’; {считана фамилия}
repeat
read(c);
until c=’ ’; {считано имя}
readln(k,b); cnt[b]:=cnt[b]+1;
end;
S:=0; b:=50;
while (S + cnt[b])*100<=N*45 do begin
S:=S+cnt[b];
if cnt[b]>0 then minb:=b;
b:=b-1
end; {определены те, кто наверняка стал призёром, и пропущены баллы, которые никто не набрал}
if (S+1)*100<=N*45 then
{если ещё хотя бы один участник попадает в 45%, то проверяется, какой балл набрал он и следующие участники}
if b>25 then minb:=b
writeln(minb)
end.
Задача 14
На вход программе поступают сведения о заводах, подающих заявку на участие в некотором государственном тендере. Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию о том, из какого региона было меньше всего заявок (таких регионов может быть несколько). При этом необходимо вывести информацию только по тем регионам, в которых есть завод, подавший заявку.
Описание входных и выходных данных.
В первой строке сообщается количество заявок N, каждая из следующих N строк имеет формат <Название Завода> <Номер Лицензии Завода> <Номер региона>, где <Название Завода>—строка, состоящая не более чем из 50 символов, <Номер Лицензии Завода> — шестизначное число, <Номер региона>— не более чем двузначное натуральное число. <Название Завода> и <Номер Лицензии Завода>, а также <Номер Лицензии Завода> и <Номер региона> разделены одним пробелом.
Пример входных данных:
Ростсельмаш 023398 61
Спринт 342901 77
Рубин 034221 61
Армалит 822145 93
Пример выходных данных:
регион(ы) с наименьшим числом заявок:
77
93
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводятся сведения о N заявках.
Программа считается эффективной по времени, если время работы программы пропорционально N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Программа читает все входные данные один раз, не запоминая их в массиве, а составляя только список встретившихся регионов и количество заявок по каждому из этих регионов, которое хранится в массиве cnt. Если при обработке данных находится регион, в котором несколько заводов подают заявку, то программа каждый раз автоматически увеличивает количество заявок от региона на 1. После окончания обработки данных программа производит поиск самого низкого числа заявок.
После нахождения самого низкого числа заявок программа проверяет, сколько всего имеется регионов с таким же количеством заявок. В конце выводятся коды регионов с самым низким числом заявок.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
var cnt: array[1..99] of integer;
c: char; i, r, N, min: integer; f: boolean;
begin
for i := 1 to 99 do cnt[i] := 0;
readln(N); {считано количество заявок}
for i := 1 to N do
begin
repeat
read(c);
until c = ’ ’; {считано название завода}
repeat
read(c);
until c = ’ ’; {считан номер лицензии завода}
readln(r);
cnt[r] := cnt[r] + 1
end;
min := 0;
f := true;
{производим поиск минимального элемента в массиве cnt}
for i := 1 to 99 do begin
if (cnt[i] < min) and (cnt[i] <> 0) then
min := cnt[i];
if f and (cnt[i] <> 0) then begin
min := cnt[i];
f := false
end
end;
{выводим коды регионов с наименьшим количеством заявок}
writeln(’регион(ы) с наименьшим числом заявок:’)
for i := 1 to 99 do
if cnt[i] = min then
writeln(i)
end.
Задача 15
Имеется набор данных, состоящий из пар целых положительных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел при делении на 5 давала остаток 1 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать −1. Напишите программу для решения этой задачи.
Описание входных и выходных данных.
На вход программе в первой строке подается количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.
Пример входных данных для варианта Б:
6
1 2
7 9
8 3
5 16
19 4
7 7
Пример выходных данных для приведённых выше примеров входных данных:
61
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N пар чисел.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чиселN, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла.
Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Описание алгоритма: создадим три одномерных массива, состоящих из 5 элементов — двух вспомогательных и одного основного. В каждом массиве индекс соответствует остатку от деления на 5 сумм элементов, найденных на предыдущем шаге. Элементами массива являются суммы просмотренных пар элементов, распределённые по соответствующим индексам. К каждой из сумм основного массива добавляем первый элемент из пары и результат сохраняем в первом вспомогательном массиве под номером, соответствующем остатку от деления суммы на 5. К каждой из сумм основного массива добавляем второй элемент из пары и результат сохраняем во втором вспомогательном массиве под номером, соответствующем остатку от деления суммы на 5. Пробегая в цикле от 0 до 4, записываем в каждую ячейку основного массива наибольший из элементов вспомогательных массивов с соответствующим индексом. В результате в основном массиве будут находиться суммы уже просмотренных элементов, распределённых по ячейкам, соответствующих остатку от их деления на 5. Если после ввода всех пар в ячейке основного массива значение элемента с индексом 1 не равно 0, то он и является искомой суммой. Если значение элемента с индексом 1 равно 0, то не существует искомой суммы, которая при делении на 5 даёт в остатке 1.
Программа, C++, gcc 4.9.2.Программа эффективна по времени и по памяти.
#include
using namespace std;
int a, b;
int max_div[5];
int n;
int div1[5], div2[5];
int main() {
cin >> n;
for (int i = 0; i <5; i++)
max_div[i] = 0;
for (int i = 0; i < n; i++) {
cin >> a >> b;
for (int j = 0; j < 5; j++) {
int k = max_div[j] + a;
int x = k % 5;
div1[x] = k;
}
for (int j = 0; j < 5; j++) {
int k = max_div[j] + b;
int x = k % 5;
div2[x] = k;
}
for (int j = 0; j < 5; j++)
max_div[j] = max(div1[j], div2[j]);
}
if (max_div[1] != 0)
cout<
cout << -1;
return 0;
}
Задача 16
Имеется набор данных, состоящий из пар целых положительных чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел делилась на 7 и при этом была максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0. Напишите программу для решения этой задачи. Описание входных и выходных данных.
На вход программе в первой строке подаётся количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 1000.
Пример входных данных:
6
1 2
7 9
8 3
5 16
19 4
7 7
Пример выходных данных для приведённого выше примера входных данных:
56
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N пар чисел.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чисел N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,— 4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Описание алгоритма: создадим три одномерных массива, состоящих из 7 элементов—два вспомогательных и один основной. В каждом массиве индекс соответствует остатку от деления на 7 сумм элементов, найденных на предыдущем шаге. Элементами массива являются суммы просмотренных пар элементов, распределённые по соответствующим индексам. К каждой из сумм основного массива добавляем первый элемент из пары и результат сохраняем в первом вспомогательном массиве под номером, соответствующем остатку от деления суммы на 7. К каждой из сумм основного массива добавляем второй элемент из пары и результат сохраняем во втором вспомогательном массиве под номером, соответствующем остатку от деления суммы на 7. Пробегая в цикле от 0 до 6 записываем в каждую ячейку основного массива наибольший из элементов вспомогательных массивов с соответствующим индексом. В результате в основном массиве будут находиться суммы уже просмотренных элементов, распределённых по ячейкам, соответствующих остатку от их деления на 7.
Если после ввода всех пар в ячейке основного массива значение элемента с индексом 0 не равно 0, то он и является искомой суммой. Если значение элемента с индексом 0 равно 0, то не существует искомой суммы, кратной 7.
Программа, C++, gcc 4.9.2.Программа эффективна по времени и по памяти.
#include
using namespace std;
int a, b, n;
int max_div[7];
int div1[7], div2[7];
int main() {
cin >> n;
for (int i = 0; i < 7; i++)
max_div[i] = 0;
for (int i = 0; i < n; i++) {
cin >> a >> b;
for (int j = 0; j < 7; j++) {
int k = max_div[j] + a;
int x = k % 7;
div1[x] = k;
}
for (int j = 0; j < 7; j++) {
int k = max_div[j] + b;
int x = k % 7;
div2[x] = k;
}
for (int j = 0; j < 7; j++)
max_div[j] = max(div1[j], div2[j]);
}
cout << max_div[0];
return 0;
}
Задача 17
По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности — наибольшее число R, удовлетворяющее следующим условиям:
1) R — произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 14.
Если такого числа R нет, то контрольное значение полагается равным 0. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены. Необходимо написать программу, которая будет проверять правильность контрольного значения.
Описание входных и выходных данных.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.
Пример входных данных:
4
70
25
32
12
2240
Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 2240
Контроль пройден
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N чисел.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чиселN, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла. Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Заметим, что искомое контрольное число может быть получено в результате произведения двух чисел, обладающих свойствами:
1) оба числа кратны 14; первое из чисел — наибольшее среди всех элементов, второе — наибольшее из всех, кроме первого (согласно условию, числа могут быть равными);
2) одно число — наибольшее из чисел, кратных 14, другое — наибольшее из чисел, не кратных 14 (но, возможно, кратных 2 или 7);
3) одно число—наибольшее из чисел, кратных 2, другое—наибольшее из чисел, кратных 7, при этом каждое из чисел не кратно 14.
Таким образом, реализация алгоритма состоит из трёх этапов.
1 этап. В процессе ввода элементов определяем значения четырёх переменных Max14, Max, Max2 и Max7:
Max14—наибольшее из чисел, кратных 14;
Max—наибольшее из чисел, за исключением Max14;
Max2—наибольшее из чисел, не кратных 14, но кратных 2;
Max7—наибольшее из чисел, не кратных 14, но кратных 7.
2 этап. Поиск наибольшего произведения среди Max14*Max и Max2*Max7.
3 этап. Определяем совпадение найденного произведения с контрольным значением.
Решение ЗАДАНИЯ Б. Пример программы на языке PascalABC 1.8.
var x, Max14, Max, Max2, Max7, N, i: longint;
R, R_max : longint;
begin
{1 этап}
Max14:=0; Max=0; Max2=0; Max7:=0; readln(N);
for i:=1 to N do begin
readln(x);
if x mod 14 <> 0 then begin
if x>Max then Max:=x;
if (x mod 2 = 0) and (x>Max2) then Max2:=x
else
if (x mod 7 = 0) and (x>Max7) then Max7:=x
end
else
if x>Max14 then Max14:=x
else if x>Max then Max:=x;
end;
readln(R);
{2 этап}
if (Max14*Max > Max2*Max7) then
R_Max:=Max14*Max
else R_Max:=Max2*Max7;
{3 этап}
if R=R_Max then
writeln(’Контроль пройден’)
else
writeln(’Контроль не пройден’)
end.
Задача 18
По каналу связи каждую минуту передаётся положительное целое число, все числа не превышают 1000.Количество чисел известно и не превышает 10 000.Временем, в течение которого происходит передача, можно пренебречь.
Необходимо вычислить минимальное кратное 3 произведение двух чисел, между моментами передачи которых прошло не менее 5 минут. Если такое значение не удаётся получить, то вывести 0.
Описание входных и выходных данных.
В первой строке задаётся число N —общее количество передаваемых чисел. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число. Программа должна вывести одно число — описанное в условии произведение либо 0, если получить такое произведение не удаётся.
Пример входных данных:
12
4
22
15
3
9
11
14
20
21
17
16
18
Пример выходных данных для приведённого выше примера входных данных:
48
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N чисел. Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чиселN, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,— 4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Первые 6 введённых чисел положим в массив. Перед вводом каждого следующего числа проверим, является ли текущий элемент массива меньше предыдущего минимума (индекс текущего элемента массива —это порядковый номер введённого числа, делённый по модулю на 6). Сохраняем в отдельных переменных минимумы для чисел, кратных 3, и для чисел, не кратных 3.
Считываем следующее число последовательности. Сохраняем его в массиве на месте текущего элемента, т. к. мы уже проверили, является ли текущий элемент минимальным, и если является, то сохранили его в отдельной переменной.
Вычислим два произведения: введённое число, умноженное на минимум, кратный 3, и введённое число, умноженное на минимум, не кратный 3. Полученные произведения проверим на кратность 3.
Каждое из полученных произведений, кратное 3, сравним с текущим минимальным произведением, если новое произведение меньше текущего минимума, заменяем текущий минимум на новый.
Повторяем указанную процедуру до окончания ввода последовательности.
Пример программы на языке PascalABC 1.8. Программа эффективна по времени и по памяти.
const T = 6; {минимальное время между передачами}
var min, min3, {минимальный элемент, не кратный 3 и кратный 3}
p_min, {минимальное произведение}
p, {произведение элементов, один из которых кратен 3}
p3, {произведение элементов, каждый из которых кратен 3}
x, K, S, i ,j,
N: integer; {количество чисел в последовательности}
a: array[1..T] of integer; {значения шести последовательных чисел}
begin
min:=1001;
min3:=1001;
readln(N);
K:=(N-T) div T;
S:=(N-T) mod T;
p_min:=1001*1001;
p:=1001*1001;
p3:=1001*1001;
for i:=1 to T do
readln(a[i]);
{просматриваем по 5 идущих подряд элементов}
for j:=1 to K do
for i:=1 to T do begin {просматриваем
последовательность из Т элементов}
if (a[i] mod 3 <> 0) and (a[i]
не кратный 3 из просмотренных}
if (a[i] mod 3 = 0) and (a[i]
кратный 3 из просмотренных}
readln(x);
a[i]:=x; {текущий элемент помещаем в массив
вместо уже просмотренного}
{находим наименьшее произведение, кратное 3, составленное из просмотренных элементов}
p3:=x*min3;
if x mod 3= 0 then p:=x*min;
if (p3
end
else if (p
{просматриваем оставшиеся в последовательности элементы, выполняя те же действия, что и в предыдущем цикле}
for i:=1 to S do begin
if (a[i] mod 3 <> 0) and (a[i]
if (a[i] mod 3 = 0) and (a[i]
readln(x);
a[i]:=x;
p3:=x*min3;
if x mod 3= 0 then
p:=x*min;
if (p3
end
else if (p
end;
writeln(p_min);
end.
Задача 19
На вход программе подаются пары натуральных чисел. Из каждой пары нужно выбрать одно число так, чтобы сумма выбранных чисел оказалась минимальной и не делилась на 2. Программа должна напечатать полученную сумму или 0, если искомую сумму получить невозможно.
Описание входных и выходных данных.
В первой строке задаётся число N — количество пар чисел. В каждой из следующих N строк задаются два неотрицательных числа, каждое из которых не больше 10 000. Программа должна вывести одно число — описанную в условии сумму либо 0.
Пример входных данных:
5
3 7
9 22
13 8
10 6
Пример выходных данных для приведённого выше примера входных данных:
29
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N пар чисел.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чиселN, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Считываем в цикле пары чисел, прибавляем к сумме S наименьшее число из пары. При этом если числа в паре различны по значению и чётности, то находим разницу между наибольшим и наименьшим числами из пары. Если она оказалась меньше, чем другие, ранее найденные разницы, то сохраним полученную разницу и числа из пары в переменные d, mx иmy соответственно. Если после цикла оказалось, что полученная сумма S делится на 2, то вычитаем из суммы наименьшее число из сохранённой пары и прибавляем наибольшее число из этой же пары. Если не нашлось ни одной пары, удовлетворяющей всем условиям, и сумма S делится на 2, то выводим 0.
Решение задания Б. Пример программы на PascalABC.
var N, i, t, x, y, d, mx, my, S: integer;
begin
S := 0; d := 10001;
mx := 10001; my := 10001;
readln(N);
for i := 1 to N do
begin
readln(x, y);
if y > x then begin
t := x;
x := y; y := t
end;
S := S + y;
if (x <> y) and (x - y < d) and
(((y mod 2 = 0) and (x mod 2 <> 0)) or
((y mod 2 <> 0) and (x mod 2 = 0))) then
begin
d := x - y;
mx := x; my := y
end
end;
if (S mod 2) = 0 then
begin
if d <> 10001 then
S := S - my + mx
else
S := 0
end;
writeln(S)
end.
Задача 20
На вход программе подаются пары неотрицательных чисел.Из каждой пары нужно выбрать одно число так, чтобы сумма выбранных чисел оказалась максимальной и не делилась на 4. Программа должна напечатать полученную сумму или 0, если искомую сумму получить невозможно.
Описание входных и выходных данных.
В первой строке задаётся число N — количество пар чисел. В каждой из следующих N строк задаются два неотрицательных числа, каждое из которых не больше 10 000. Программа должна вывести одно число — описанную в условии сумму либо 0.
Пример входных данных:
4
8 3
1 9
4 4
3 1
Пример выходных данных для приведённого выше примера входных данных:
22
Напишите эффективную как по времени, так и по памяти программу для решения поставленной задачи, если известно, что вводится N пар чисел.
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных чисел N, то есть при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, необходимой программе для хранения всех переменных, не превышает 1 Кбайт и не увеличивается с ростом числа N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающуюправильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти,—4 балла. Максимальная оценка за правильную программу, эффективную только по времени,—3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности,—2 балла.
Вы можете написать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы напишете две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо´ льшая из двух оценок. Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
Решение
Считываем в цикле пары чисел, прибавляя к сумме выбранных чисел S наибольшее.При этом если числа в паре отличны, разность наибольшего и наименьшего не делится на 4, и данная разность меньше других, полученных из других пар, то запишем полученную разность и числа из пары в переменные. Если после цикла окажется, что сумма выбранных чисел S делится на 4 и мы нашли хотя бы одну такую пару, удовлетворяющую всем перечисленным выше условиям, то вычтем из суммы S наибольшее число, которое мы сохранили, и прибавим наименьшее число. Если не нашлось ни одной пары, то присвоим S значение 0.
Программа на языке PascalABC. Программа эффективна повремени и по памяти.
var S, N, i, t, d, x, y, mx, my: integer;
begin
S := 0;
d := 10001;
mx := 10001;
my := 10001;
readln(N);
for i := 1 to N do begin
readln(x, y);
if y > x then begin
t := x; x := y;
y := t
end;
S := S + x;
if (x<>y) and ((x-y) mod 4 <>0) and (x-y
d := x - y;
mx := x; my := y
end
end;
if (S mod 4) = 0 then
begin
if d <> 10001 then
S := S - mx + my
else
S := 0
end;
writeln(S)
end.