27 задание часть 3
Предисловие
Планомерно подходим к году, когда ЕГЭ только появился. Стоит отметить, что условия значительно изменились с далекого 2011 года, раньше не нужно было соблюдать требование к оптимальности (не было ограничений по быстродействию и используемой памяти). Не терпится перейти к решениям!
Демонстрационный вариант ЕГЭ 2013 г. ИНФОРМАТИКА и ИКТ, 11 класс.
1. На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи. В первой строке сообщается число пассажиров N, которое не меньше 3, но не превосходит 1000; во второй строке – количество ячеек в камере хранения K, которое не меньше 10, но не превосходит 1000. Каждая из следующих N строк имеет следующий формат:
<Фамилия> <время сдачи багажа> <время освобождения ячейки>, где <Фамилия> – строка, состоящая не более чем из 20 непробельных символов; <время сдачи багажа> – через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа); <время освобождения ячейки> имеет тот же формат. <Фамилия> и <время сдачи багажа>, а также <время сдачи багажа> и <время освобождения ячейки> разделены одним пробелом. Время освобождения больше времени сдачи.
Сведения отсортированы в порядке времени сдачи багажа. Каждому из пассажиров в камере хранения выделяется свободная ячейка с минимальным
номером. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит, не дожидаясь освобождения одной из них. Требуется написать программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет выводить на экран для каждого пассажира номер ему предоставленной ячейки (можно сразу после ввода данных очередного пассажира). Если ячейка пассажиру не предоставлена, то его фамилия не печатается.
Пример входных данных:
3
10
Иванов 09:45 12:00
Петров 10:00 11:00
Сидоров 12:00 13:12
Результат работы программы на этих входных данных:
Иванов 1
Петров 2
Отметим прикладной контекст данной задачи. Сначала надо заполнить массив из введенных строк. Разделять значения будем по пробельным символам. Первый столбец – под фамилии, второй – под время прибытия (в минутах), третий – под время освобождения ячейки (в минутах), а четвертый – под номер выделенной ячейки. Первой строке присвоим номер ячейки, равный 1. Далее будем проверять, если время прибытия какого-либо пассажира больше, чем время освобождения ячейки другим пассажиром, то присваиваем ему номер освободившейся ячейки. Иначе просматриваем цикл, находим последнюю заполненную ячейку, и присваиваем строке этот номер +1. В выводе проверяем, если номер присвоенной ячейки меньше их количества, то выводим.
program numberoflaggageforpassengers;
var
a:array[1..1000, 1..4]of string;
AmountOfPassengers, AmountOfCells, FirstIndex, SecondIndex, ThirdIndex, temporary, maximum:integer;
InputStringWithData, temporaryhelper, temporaryhelper2, temporaryhelper3:string;
begin
writeln('Введите количество пассажиров = ');
readln(AmountOfPassengers);
writeln('Введите количество ячеек в камере хранения = ');
readln(AmountOfCells);
for FirstIndex := 1 to AmountOfPassengers do
begin
writeln('Введите фамилию пассажира, время сдачи багажа и время освобождения ячейки');
readln(InputStringWithData);
a[FirstIndex, 4] := '0';
for SecondIndex := 1 to Length(InputStringWithData) do
if InputStringWithData[SecondIndex] = ' ' then
begin
temporary := SecondIndex;
break;
end;
for ThirdIndex:=1 to temporary-1 do
a[FirstIndex, 1] := a[FirstIndex, 1] + InputStringWithData[ThirdIndex];
a[FirstIndex, 2] := IntToStr(StrToInt(InputStringWithData[temporary+1])*600 + StrToInt(InputStringWithData[temporary+2])*60 + StrToInt(InputStringWithData[temporary+4])*10 + StrToInt(InputStringWithData[temporary+5]));
a[FirstIndex, 3] := IntToStr(StrToInt(InputStringWithData[temporary+7])*600 + StrToInt(InputStringWithData[temporary+8])*60 + StrToInt(InputStringWithData[temporary+10])*10 + StrToInt(InputStringWithData[temporary+11]));
end;
a[1 , 4] := '1';
for FirstIndex:=1 to AmountOfPassengers do
writeln(a[FirstIndex]);
for FirstIndex := 2 to AmountOfPassengers do
begin
maximum :=1;
for ThirdIndex := FirstIndex-1 downto 1 do
begin
if StrToInt(a[ThirdIndex, 4]) > maximum then
maximum := StrToInt(a[ThirdIndex, 4]);
if a[FirstIndex, 2] >= a[ThirdIndex, 3] then
a[FirstIndex, 4] := a[ThirdIndex, 4]
else if maximum > StrToInt(a[FirstIndex, 4]) then
a[FirstIndex, 4] := IntToStr(maximum+1);
end;
end;
for FirstIndex:=1 to AmountOfPassengers do
if StrToInt(a[FirstIndex, 4]) <= AmountOfCells then
writeln(a[FirstIndex, 1], ' ', a[FirstIndex, 4]);
end.
Демонстрационный вариант ЕГЭ 2012 г. ИНФОРМАТИКА и ИКТ, 11 класс.
2. В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.
Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.
Пример входных данных:
6
A+B
Крестики-Нолики
Прямоугольник
Простой делитель
A+B
Простой делитель
Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.
Пример выходных данных для приведённого выше примера входных данных:
А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1
Сначала будем проверять, есть ли введённая строка в массиве из 11 возможных задач. Если нет, то будем добавлять ее в массив в первую же свободную ячейку. Если есть – то будем увеличивать количество данных встреченных строк на 1. После того, как будет заполнен массив, отсортируем его по убыванию (по количеству встреченных задач). После будем анализировать данные. Если в массиве всего одна значащая строка, то вывести ее. Если 2 – то эти две. Если более двух – будем проверять, есть ли та же частота встречаемости у строки с 4 по 11 с третьей строкой. Если есть, то выводим также и эти строки вместе с тремя первыми.
program countingoftheamountofthemostpopulartask;
var
disorder, indicator:boolean;
InputString, helper, SecondHelper:string;
TheAmountOfRequests, FirstIndex, SecondIndex, ThirdIndex, temporary, SecondTemporary:integer;
a:array[1..11, 1..2] of string;
begin
disorder := true;
writeln('Введите количество поступивших запросов: ');
readln(TheAmountOfRequests);
for FirstIndex := 1 to 11 do
begin
a[FirstIndex, 1] := ' ';
a[FirstIndex, 2] := '0';
end;
for FirstIndex := 1 to TheAmountOfRequests do
begin
indicator := false;
writeln('Введите запросы: ');
readln(InputString);
for SecondIndex := 1 to 11 do
begin
if a[SecondIndex, 1] = InputString then
begin
a[SecondIndex, 2] := IntToStr(StrToInt(a[SecondIndex, 2]) + 1);
indicator := true;
end;
end;
if Indicator = false then
begin
for ThirdIndex := 1 to 11 do
if a[ThirdIndex, 1] = ' ' then
begin
temporary := ThirdIndex;
break;
end;
a[temporary, 1] := InputString;
a[temporary, 2] := IntToStr(StrToInt(a[temporary, 2]) + 1);
end;
end;
while disorder do
begin
disorder:=false;
for FirstIndex := 1 to 10 do
if StrToInt(a[FirstIndex, 2]) < StrToInt(a[FirstIndex+1, 2]) then
begin
SecondHelper := a[FirstIndex, 1];
helper := a[FirstIndex, 2];
a[FirstIndex, 1] := a[FirstIndex+1, 1];
a[FirstIndex, 2] := a[FirstIndex+1, 2];
a[FirstIndex+1, 1] := SecondHelper;
a[FirstIndex+1, 2] := helper;
disorder:=true;
end;
end;
SecondTemporary := 0;
for FirstIndex:=1 to 11 do
begin
if a[FirstIndex, 1] <> ' ' then
SecondTemporary := FirstIndex;
end;
if SecondTemporary = 0 then
writeln('Ошибка');
if SecondTemporary = 1 then
writeln(a[1,1], ' ', a[1,2]);
if SecondTemporary = 2 then
begin
writeln(a[1,1], ' ', a[1,2]);
writeln(a[2,1], ' ', a[2,2]);
end;
if SecondTemporary > 2 then
begin
for SecondIndex := 4 to 11 do
if a[3, 2] = a[SecondIndex, 2] then
temporary := SecondIndex;
for SecondIndex:=1 to temporary do
writeln(a[SecondIndex, 1], ' ', a[SecondIndex, 2]);
end;
end.
Демонстрационный вариант ЕГЭ 2011 г. ИНФОРМАТИКА и ИКТ, 11 класс.
3. На вход программе подается набор символов, заканчивающийся точкой (в программе на языке Бейсик символы можно вводить по одному в строке, пока не будет введена точка, или считывать данные из файла). Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно один ноль.
Если требуемое число составить невозможно, то программа должна вывести на экран слово «NO». А если возможно, то в первой строке следует вывести слово «YES», а во второй – искомое симметричное число. Если таких чисел
несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:
Do not 911 to 09 do.
В данном случае программа должна вывести
YES
91019
Сначала будем считать, сколько раз встречается та или иная цифра, и записывать данные об их количестве в массив. Далее пройдемся по массиву, если количество какой-либо цифры нечетно, то она должна быть в центре искомого числа. Если таких цифр несколько, то построить требуемое число невозможно. Остальные цифры добавляем слева и справа в порядке возрастания, отталкиваясь от их количества. Если на первом месте получившегося числа «0», выдаем ошибку. Выводим число.
program thecreationofsymmetricnumbefrominputstrings;
var
InputString, OutputString:string;
FirstIndex, SecondIndex, oddcounter, temporary:integer;
a:array[0..9, 1..2] of integer;
begin
oddcounter := 0;
for FirstIndex:=0 to 9 do
a[FirstIndex,1]:=FirstIndex;
writeln('Введите строку');
readln(InputString);
for FirstIndex:=1 to Length(InputString) do
begin
if ord(InputString[FirstIndex]) = 48 then
a[0,2]:=a[0,2]+1;
if ord(InputString[FirstIndex]) = 49 then
a[1,2]:=a[1,2]+1;
if ord(InputString[FirstIndex]) = 50 then
a[2,2]:=a[2,2]+1;
if ord(InputString[FirstIndex]) = 51 then
a[3,2]:=a[3,2]+1;
if ord(InputString[FirstIndex]) = 52 then
a[4,2]:=a[4,2]+1;
if ord(InputString[FirstIndex]) = 53 then
a[5,2]:=a[5,2]+1;
if ord(InputString[FirstIndex]) = 54 then
a[6,2]:=a[6,2]+1;
if ord(InputString[FirstIndex]) = 55 then
a[7,2]:=a[7,2]+1;
if ord(InputString[FirstIndex]) = 56 then
a[8,2]:=a[8,2]+1;
if ord(InputString[FirstIndex]) = 57 then
a[9,2]:=a[9,2]+1;
end;
for FirstIndex := 0 to 9 do
if a[FirstIndex, 2] mod 2 <> 0 then
begin
temporary := FirstIndex;
oddcounter := oddcounter + 1;
end;
if oddcounter > 1 then
writeln('NO');
if oddcounter = 1 then
writeln('YES');
begin
OutputString := IntToStr(a[temporary, 1])*a[temporary,2];
for SecondIndex := 0 to 9 do
if (temporary <> SecondIndex) and (a[SecondIndex, 2] > 0) then
begin
OutputString := OutputString + IntToStr(a[SecondIndex, 1])*(a[SecondIndex, 2] div 2);
OutputString := IntToStr(a[SecondIndex, 1])*(a[SecondIndex, 2] div 2) + OutputString;
end;
end;
if oddcounter = 0 then
begin
writeln('YES');
OutputString := '';
for SecondIndex := 0 to 9 do
if a[SecondIndex, 2] > 0 then
begin
OutputString := OutputString + IntToStr(a[SecondIndex, 1])*(a[SecondIndex, 2] div 2);
OutputString := IntToStr(a[SecondIndex, 1])*(a[SecondIndex, 2] div 2) + OutputString;
end;
end;
if (length(OutputString) > 1) and (OutputString[1] = '0') then
writeln ('Ошибка')
else
writeln(OutputString);
end.
Вывод
Рассматривая задачи прошлых лет (2011 по 2013), можно отметить, что решения были сложнее, менее тривиальными. Именно такой тип задач обычно ставят перед программистами.
