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

11.02.19

Разработка - Математика и алгоритмы

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

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

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1753    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4415    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7455    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7854    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4444    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8832    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7797    dusha0020    8    

70
Оставьте свое сообщение