Подготовка ребёнка к ЕГЭ по информатике. Часть десятая

Публикация № 1000984

Программирование - Практика программирования

2
Последний уровень, часть третья.

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), можно отметить, что решения были сложнее, менее тривиальными. Именно такой тип задач обычно ставят перед программистами.

2

См. также

Специальные предложения

Избранное Подписка Сортировка: Древо
В этой теме еще нет сообщений.
Оставьте свое сообщение