27 задание часть 4
Предисловие
Последняя часть по решению 27 задачи ЕГЭ. В ней в совокупности со всеми предыдущими были рассмотрены основные типы 27 задания.
Демонстрационный вариант ЕГЭ 2011 г. ИНФОРМАТИКА и ИКТ, 11 класс
1. На автозаправочных станциях (АЗС) продается бензин с маркировкой 92, 95
и 98. В городе N был проведен мониторинг цены бензина на различных АЗС.
Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет определять для каждого вида бензина, сколько АЗС продают его дешевле всего. На вход программе в первой строке подается число данных о стоимости бензина. В каждой из последующих N строк находится информация в следующем формате:
<Компания> <Улица> <Марка> <Цена>, где <Компания> – строка, состоящая не более, чем из 20 символов без пробелов, <Улица> – строка, состоящая не более, чем из 20 символов без пробелов, <Марка> – одно из чисел – 92, 95 или 98, <Цена> – целое число в диапазоне от 1000 до 3000, обозначающее стоимость одного литра бензина в копейках. <Компания> и <Улица>, <Улица> и <Марка>, а также <Марка> и <цена> разделены ровно одним пробелом.
Пример входной строки:
Синойл Цветочная 95 2250
Программа должна выводить через пробел 3 числа – количество АЗС, продающих дешевле всего 92-й, 95-й и 98-й бензин соответственно. Если бензин какой-то марки нигде не продавался, то следует вывести 0.
Пример выходных данных:
12 1 0
Будем использовать счетчики для количества чисел, равных минимуму для 92 бензина, 95 и 98. Также минимумы для 92, 95, 98. Запрашиваем количество строк. Запрашиваем строки с 1 по последнюю, оттуда берем значения номера бензина, цену. Сравниваем с минимумом, если оно равно минимуму, то увеличиваем счетчик для этой марки. Если меньше – то присваиваем счетчику «1», минимум = данному значению. Далее анализируем: если не было введено ни одного значения для 92, 95, 98, выводим «0», иначе – минимум.
program thecheapestpetrolintownn;
var
InputString:string;
counterfor92, counterfor95, counterfor98, minumumfor92, minumumfor95, minumumfor98, FirstIndex, SecondIndex, ThirdIndex, helper, AmountOfStrings:integer;
begin
minumumfor92 := 3001;
minumumfor95 := 3001;
minumumfor98 := 3001;
counterfor92 := 0;
counterfor95 := 0;
counterfor98 := 0;
SecondIndex := 0;
writeln('Введите количество строк');
readln(AmountOfStrings);
for ThirdIndex := 1 to AmountOfStrings do
begin
SecondIndex := 0;
helper := 0;
writeln('Введите строку');
readln(InputString);
for FirstIndex := 1 to Length(InputString) do
if InputString[FirstIndex] = ' ' then
begin
SecondIndex := SecondIndex + 1;
helper := FirstIndex;
if SecondIndex = 2 then
begin
if (InputString[helper+1] + InputString[helper+2] = '92') and (StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]) < minumumfor92) then
begin
counterfor92 := 1;
minumumfor92 := StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]);
end;
if (InputString[helper+1] + InputString[helper+2] = '92') and (StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]) = minumumfor92) then
counterfor92 := counterfor92 + 1;
if (InputString[helper+1] + InputString[helper+2] = '95') and (StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]) < minumumfor95) then
begin
counterfor95 := 1;
minumumfor95 := StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]);
end;
if (InputString[helper+1] + InputString[helper+2] = '95') and (StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]) = minumumfor95) then
counterfor95 := counterfor95 + 1;
if (InputString[helper+1] + InputString[helper+2] = '98') and (StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]) < minumumfor98) then
begin
counterfor98 := 1;
minumumfor98 := StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]);
end;
if (InputString[helper+1] + InputString[helper+2] = '98') and (StrToInt(InputString[helper+4]+InputString[helper+5]+InputString[helper+6]+InputString[helper+7]) = minumumfor98) then
counterfor98 := counterfor98 + 1;
end;
end;
end;
if counterfor92 = 0 then
writeln('0')
else
writeln(minumumfor92);
if counterfor95 = 0 then
writeln('0')
else
writeln(minumumfor95);
if counterfor98 = 0 then
writeln('0')
else
writeln(minumumfor98);
end.
Демонстрационный вариант ЕГЭ 2010 г. ИНФОРМАТИКА и ИКТ, 11 класс
2. На вход программе подаются сведения о номерах школ учащихся, участ-вовавших в олимпиаде. В первой строке сообщается количество учащих-ся N, каждая из следующих N строк имеет формат: <Фамилия> <Инициа-лы> <номер школы>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> раз-делены одним пробелом. Пример входной строки:
Иванов П.С. 57
Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из каких школ было меньше всего участников олимпиады (но из этих школ был хотя бы один участник).
Очевидно, что, либо последний символ в данной строке – это номер школы (если это школы с 1 по 9), либо – последние два. Будем проверять, соответствует ли номер данного символа номерам цифр от 0 до 9. Дальше в строке таблицы, представляющую собой школы с 1 по 99, увеличивается количество олимпиадников на 1 (в той строке, которая соответствует номеру школы). Потом сортируем получившийся массив от меньшего к большему по количеству олимпиадников. Т.к. требуется вывести номер школы и наименьшее количество участников (>0), добавим условие. Также возможно, что в других школах было то же минимальное количество участников. Выведем и их.
program theleastamountofparticipantsintheolimpiad;
var
InputString:string;
a:array[1..99, 1..2]of integer;
disorder:boolean;
FirstIndex, AmountOfParticipants, temporary, FirstHelper, SecondHelper:integer;
begin
disorder := true;
writeln('Введите количество участников: ');
readln(AmountOfParticipants);
for FirstIndex := 1 to 99 do begin
a[FirstIndex, 1] := FirstIndex;
a[FirstIndex, 2] := 0;
end;
for FirstIndex := 1 to AmountOfParticipants do
begin
writeln('Введите строку с данными');
readln(InputString);
if (ord(InputString[Length(InputString)-1]) > 47) and (ord(InputString[Length(InputString)-1]) < 58) then
temporary := StrToInt(InputString[Length(InputString)-1]+InputString[Length(InputString)])
else
temporary := StrToInt(InputString[Length(InputString)]);
a[temporary,2] := a[temporary,2] + 1;
end;
while disorder do
begin
disorder := false;
for FirstIndex := 1 to 98 do
begin
if a[FirstIndex+1, 2] < a[FirstIndex, 2] then
begin
FirstHelper := a[FirstIndex, 2];
SecondHelper := a[FirstIndex, 1];
a[FirstIndex, 2] := a[FirstIndex+1, 2];
a[FirstIndex, 1] := a[FirstIndex+1, 1];
a[FirstIndex+1, 2] := FirstHelper;
a[FirstIndex+1, 1] := SecondHelper;
disorder := true;
end;
end;
end;
for FirstIndex := 1 to 99 do
if a[FirstIndex, 2] > 0 then
begin
temporary := FirstIndex;
break;
end;
FirstHelper := temporary + 1;
writeln('Школа №', a[temporary, 1], ' Количество участников ', a[temporary, 2]);
for FirstIndex := FirstHelper to 99 do
if a[temporary, 2] = a[FirstIndex, 2] then
writeln('Школа №', a[FirstIndex, 1], ' Количество участников ', a[FirstIndex, 2]);
end.
Источник: ЕГЭ по информатике 30.05.2013. Основная волна. Дальний Восток. Вариант 1.
3. На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является максимальным среди всех возможных множеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то основным считается то, которое содержит наибольшее количество элементов.
Вам предлагается написать программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве. Перед программой укажите версию языка программирования.
Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Пример входных данных:
5
123
2
-1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.
Пример выходных данных для приведённого выше примера входных данных:
1 2 5
Выбираем Б. В основное множество будут входить все положительные числа, все отрицательные (если их четное количество) , все отрицательные (если их нечетное количество), кроме наименьшего по модулю, и числа не равные «0». Следовательно, нужен счетчик количества отрицательных чисел, наименьшее отрицательное, изначально – -300000 (приблизительно, скорость света в вакууме с противоположным знаком). На выводе будут проверяться все описанные выше ограничения.
program themainvariety;
var AmountOfNumbers, minless0, Zero, Helper, Counter, InputNumber, FirstIndex: longint;
begin
writeln('Введите количество частиц');
readln(AmountOfNumbers);
minless0 := -300000;
Helper := 0;
Zero := 0;
Counter := 0;
for FirstIndex := 1 to AmountOfNumbers do
begin
writeln('Введите скорость частицы');
readln(InputNumber);
if InputNumber = 0 then Zero := FirstIndex;
if InputNumber < 0 then
begin
Counter := Counter + 1;
if InputNumber > minless0 then
begin
minless0 := InputNumber;
Helper := FirstIndex;
end;
end;
end;
writeln;
for FirstIndex := 1 to AmountOfNumbers do
if (FirstIndex <> Zero) and ((Counter mod 2 = 0 ) or (FirstIndex <> Helper)) then
writeln(FirstIndex);
end.
Вывод
Вот и завершен цикл статей по 27 заданию ЕГЭ. Радует, что составители государственного экзамена пытаются разнообразить задания, предлагать что-то действительно захватывающее и интересное!
