Задание C4: знания / сюжеты / методы решения
Создание: 17.04.2013

Для большинства учеников самой сложной и решаемой задачей в ЕГЭ по информатике является задача C4. Ее отличительные особенности:

  • Замысловатый сюжет с текстом из 200-300 слов, для понимания которого требуется 3-5 прочтений.
  • Программа получает набор данных, которые требуется обработать и получить набор выходных значений.
  • Как правило, требуется создать «эффективный» алгоритм.
  • Среднее время, которое ученик тратит на решение – один час.

Как и любую «типовую» задачу ее можно научиться решать!

Проанализировав несколько десятков задач С4 ЕГЭ по информатике из демонстрационных вариантов, реальных вариантов, а также многочисленных сборников для подготовки к экзамену. Из всего многообразия можно выделить несколько «типовых сюжетов» и методов их решения, знаний, которыми должен обладать ученик.

Знания:

Для успешного решения задачи необходимым минимумом является:

  • понимание структуры программы,
  • работа с различными типами данных,
  • ввод-вывод данных
  • работа с условными операторами
  • написание циклов с условиями и с параметрами
  • написание вложенных циклов

все эти знания используются в других частях единого экзамена, но помимо этих минимальных требований, есть и более специфичные.

Работа со строками

Необходимые знания

синтаксис в языке Pascal

определение длины строки

n:= length(str);

получение отдельного символа по его номеру в строке

ch := str[10]; {выделяем десятый символ в строке}

получение кода символа по его коду

code:=ord(ch);

получение символа по коду

ch:=ctr(code);

поиск подстроки в строку

pos(‘ ‘,str); {поиск первого пробела в строке}

выделение подстроки в строке

name:=copy(str,1,10); {выделяем первые пять символов в строке и сохраняем их в строковой переменной phone}

удаление части строки

delete(str,1,10) ; {удаляем первые десять символов в строке. Это – оператор.}

перевод строки в число val()

val(str,i,err); {значение строки str преобразовывается в числовое и записывается в переменную i, err- номер ошибочного символа, в случае успеха равен нулю}

работать с массивами

Необходимые знания

синтаксис в языке Pascal

описание и формирование массива

var m: array[1..99] of integer;

поиск значения по заданному критерию

for i:=1 to n do
if (m[i]=k) then
begin
num := I;
break;
end;

{запомнили индекс элемента массива с заданным значением k}

поиск минимального элемента в массиве

min := m[1];
num_min:=1;
for i:=2 to n do
if(m[i] < min) then
begin
min := m[i];
num_min:=i;
end;

обмен элементами массива

z:=m[1];
m[1]:=m[10];
m[10]:=z;

{элементы массива с индексами 1 и 10 поменялись местами}

сортировка массива

for i:=2 to n_qwest do
for j:=1 to i do
if m[i] > m[j] then
begin
z := m[j];
m[j] := m[i];
m[i] := z;
end;

работать с записями

Необходимые знания

синтаксис в языке Pascal

описание записей

type student = record
name: string[20];
class: integer;
end;
var
r: student;
mas:array[1..1000] of student;

формирование новой записи

r.name := ‘abc’;
r.class := 11;

формирование массива записей

все тоже самое, но в цикле

. . .
mas[i].name := ‘abc’;
mas[i].class := 11;
. . .

Большинство задач так или иначе использует все из перечисленных знаний.

Экзамен по информатике начинают проводить за компьютером, и у ученика появляется отличный инструмент для проверки того, что он написал, для получения знания о том, что помнил, да забыл. Важно уметь этим инструментом пользоваться.

Готовясь к экзамену в любом случае нужно писать программы, учиться отлаживать их.

Сюжеты и методы:

Ниже представлены одиннадцать различных вариантов задач С4, которые встречались демонстрационных, пробных и реальных экзаменах за последние три года. Для простоты обращения к каждой из задач им даны краткие названия, для каждой задачи приведен краткий метод ее решения.

1. «Результаты экзаменов»
Из полученных строк формируется массив записей, с их последующей статистической обработкой.

текст задачи:
На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:

<Фамилия> <Имя> <оценки>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Имя> – строка, состоящая не более чем из 15 символов, <оценки> – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. <Фамилия> и <Имя>, а также <Имя> и <оценки> разделены одним пробелом.

Пример входной строки:
Иванов Петр 4 5 3

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран фамилии и имена трех худших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех худших, то следует вывести и их фамилии и имена.

метод решения:

  • получение N строк и их обработка:
    • выделение имени
    • выделение трех оценок
    • получение суммарного балла (аналог среднего балла, но целое число)
    • добавление в массив [0..15] имен учеников, набравших бал, равный индексу массива
  • вывод трех наименьших не пустых значения массива

 

2. Участие в олимпиаде
Из полученных строк формируется массив записей, с последующей статистической обработкой.

Текст задачи:

На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат: <Фамилия> <Инициалы> <номер школы>, где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> – строка, состоящая из 4-х символов (буква, точка, буква, точка), <номер школы> – не более чем двузначный номер. <Фамилия> и <Инициалы>, а также <Инициалы> и <номер школы> разделены одним пробелом. Пример входной строки:

Иванов П.С. 57

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из каких школ было меньше всего участников олимпиады (но из этих школ был хотя бы один участник).

метод решения:

  • получение N строк и их обработка:
    • выделение имени
    • выделение номера школы
    • добавление в массив записей [1..99] имен учеников, участвовавших в олимпиаде , в индекс, равный номеру школы. Так как после этот массив нужно будет сортировать, то помимо строки имен запись должна содержать номер школы и количество учеников (последнее значение должно увеличиваться на единицу при обработке новой строки).
    • сортировка массива по полю количество учеников
  • вывод трех наименьших не пустых значения массива

 

3. «Ученики школы»
Из списка учеников формируется массив записей, который подвергается статистической обработке.

Текст задачи:

На вход программе подаются сведения об учениках некоторой средней школы. В первой строке сообщается количество учеников N, каждая из следующих N строк имеет следующий формат: <Фамилия> <Имя> <класс>, где

<Фамилия> – строка, состоящая не более, чем из 20 символов,
<Имя> – строка, состоящая не более, чем из 15 символов,
<класс> – год обучения (от 1 до 11) и заглавная буква (от “А” до “Я”) без пробела.

<Фамилия> и <Имя>, а также <Имя> <класс> разделены одним пробелом.

Пример входной строки:
Иванов Петр 10Б

Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию о параллелях (годе обучения) с наименьшим числом учеников. Программа должна выводить на экран в первой строке количество учеников в искомых параллелях, а во второй строке – в порядке возрастания номера этих параллелей через пробел.

Например:
100
1 7 11

метод решения:
вариация предыдущих задач

  • получение N строк и их обработка:
    • выделение имени
    • выделение номера класса
    • добавление в массив записей [1..11] имен учеников, в индекс, равный номеру класса. Так как после этот массив нужно будет сортировать, то помимо строки имен запись должна содержать номер параллели и количество учеников в ней (последнее значение должно увеличиваться на единицу при обработке каждой новой строки).
  • сортировка массива по полю количество учеников
  • вывод трех наибольших не пустых значения массива

 

4. «Среднесуточная температура»
Из полученных строк с среднесуточной температурой формируется массив записей, произволится статистическая полученных данных.

Текст задачи:

На вход программе подаются 365 строк, которые содержат информацию о среднесуточной температуре всех дней 2007 года. Формат каждой из строк следующий: сначала записана дата в виде dd.mm (на запись номера дня и номера месяца в числовом формате отводится строго два символа, день от месяца отделен точкой), затем через пробел (для Бейсика – через запятую) записано значение температуры — число со знаком плюс или минус, с точностью до 1 цифры после десятичной точки. Данная информация отсортирована по значению температуры, то есть хронологический порядок нарушен. Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию о месяцах с минимальной среднемесячной температурой. Найденные минимальные значения следует выводить в отдельной строке для каждого месяца в виде: номер месяца, значение среднемесячной температуры, округленное до одной цифры после десятичной точки.

метод решения:

  • получение 365 строк
    • выделение номера месяца
    • выделение температуры (перевод ее в числовое значение)
    • заполнение массива записей [1..12] суммарным значением температуры за текущий месяц, т.е. в первом элементе массива будет храниться суммарная температура за январь. Помимо суммарной температуры, записи имеют поля с номером месяца, количеством дней (вносится заранее) и среднемесячной температурой (вычисляется после заполнения массива.
    • вычисление и сохранение среднемесячной температуры
  • сортировка массива по полю среднемесячная температура
  • вывод трех первых элементов массива

 

5. «Автозаправочные станции»
Формирование массива записей, выбор значения по заданному критерию.

Текст задачи:
На автозаправочных станциях (АЗС) продается бензин с маркировкой 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

метод решения: подробно описан в моем сервисе подготовка к ЕГЭ: http://www.titorov.ru/ege/

 

6. «Числовой палиндром»
Обработка текстовой строки, выделение в ней чисел, их анализ на возможность получения палиндрома.

Текст задачи:
На вход программе подается набор символов, заканчивающийся точкой. Напишите эффективную, в том числе и по используемой памяти, программу, которая сначала будет определять, есть ли в этом наборе символы, соответствующие десятичным цифрам. Если такие символы есть, то можно ли переставить их так, чтобы полученное число было симметричным (читалось одинаково как слева направо, так и справа налево). Ведущих нулей в числе быть не должно, исключение – число 0, запись которого содержит ровно один ноль.

Если требуемое число составить невозможно, то программа должна вывести на экран слово «NO». А если возможно, то в первой строке следует вывести слово «YES», а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:

Do not 911 to 09 do.

В данном случае программа должна вывести

YES
91019

метод решения: подробно описан в моем сервисе подготовка к ЕГЭ: http://www.titorov.ru/ege/

 

7) «Олимпиадные задачи»
Обработать входящие строки, сформирование массив с количеством решенных задач, выбрать значения из массива по заданному критерию.

текст задачи:
В командных олимпиадах по программированию для решения предлагается не больше 11 задач. Команда может решать предложенные задачи в любом порядке. Подготовленные решения команда посылает в единую проверяющую систему соревнований. Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет статистически обрабатывать пришедшие запросы, чтобы определить наиболее популярные задачи. Следует учитывать, что количество запросов в списке может быть очень велико, так как многие соревнования проходят с использованием Интернет.

На вход программе в первой строке подаётся количество пришедших запросов N. В каждой из последующих N строк записано название задачи в виде текстовой строки. Длина строки не превосходит 100 символов, название может содержать буквы, цифры, пробелы и знаки препинания.

Пример входных данных:

6
А+B
Крестики-Нолики
Прямоугольник
Простой делитель
А+В
Простой делитель

Программа должна вывести список из трёх наиболее популярных задач с указанием количества запросов по ним. Если в запросах упоминаются менее трех задач, то выведите информацию об имеющихся задачах. Если несколько задач имеют ту же частоту встречаемости, что и третья по частоте встречаемости задача, их тоже нужно вывести.

Пример выходных данных для приведённого выше примера входных данных:

А+В 2
Простой делитель 2
Крестики-Нолики 1
Прямоугольник 1

метод решения: подробно описан в моем сервисе подготовка к ЕГЭ: http://www.titorov.ru/ege/

 

8. «Заклинание»
Получить строку, выполнить преобразования с символами по заданным правилам, вывести полученную строку.

Текст задачи:
На вход программе подается текст заклинания, состоящего не более чем из 200 символов, за­канчивающийся точкой (символ «точка» во входных данных единственный). Оно было за­шифровано юным волшебником следующим об­разом. Сначала волшебник определил количест­во букв в самом коротком слове, обозначив по­лученное число К (словом называется непрерыв­ная последовательность латинских букв, слова друг от друга отделяются любыми другими сим­волами, длина слова не превышает 20 симво­лов). Затем он заменил каждую латинскую бук­ву в заклинании на букву, стоящую в алфавите на К букв ранее (алфавит считается цикличе­ским, то есть перед буквой А стоит буква Z), ос­тавив другие символы неизменными. Строчные буквы при этом остались строчными, а пропис­ные — прописными. Требуется написать про­грамму на языке Паскаль или Бейсик, которая будет выводить на экран текст расшифрованного заклинания.

Например, если зашифрованный текст был таким:
Zb Ra Са Dab Ra,

то результат расшифровки должен быть сле­дующим:
Вd Тс Ее Fed Тс.

метод решения:

  • Выделение исходной строки
  • Определение длины самого короткого слова – K.
  • Замена в исходной строке каждого символа с кодом C на новый: CA + (C+K) mod CA для заглавных и Ca + (C+K) mod Ca для прописных. (мы добавляем, т.к. идет расшифровка кода).
  • Вывод нового кода на экран.

 

9. «Камера хранения»
Получить список строк, сформировать массив записей, выбрать значения по заданному критерию.

Текст задачи:
На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи.

В первой строке сообщается число пассажиров N, которое не меньше 3, но не превосходит 1000; во второй строке – количество ячеек в камере хранения М, которое не меньше 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

метод решения: подробно описан в моем сервисе «Подготовка к ЕГЭ»: http://www.titorov.ru/ege/

 

10. «Контрольное значение»
На основе полученной последовательности чисел вычислить контрольного значение, которое строится по заданным правилам, сравнить вычисленное значение с полученным на входе.

Текст задачи:

По каналу связи передается последовательность положительных целых чисел, все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается отдельно. Признаком конца передаваемой последовательности является число 0. После числа 0 передается контрольное значение – наибольшее число R, удовлетворяющее следующим условиям:

1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных, но равных по величине элементов допускаются);
2) R делится на 6

Напишите эффективную программу, которая получает последовательность чисел и следующие за ней признак конца и контрольное значение, а также проверяет правильность контрольного значения. Программа должна напечатать отчет по следующей форме:

Получено .. чисел
Полученное контрольное значение: ….
Вычисленное контрольное значение:…
Контроль пройден (или – контроль не пройден).

Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Перед текстом программы кратко опишите используемый вами алгоритм решения задачи.

Пример входных данных:
60
17
3
7
9
60
0
3600

Пример выходных данных для приведенного выше примера входных данных:

Получено 6 чисел
Полученное контрольное значение: 3600
Вычисленное контрольное значение: 3600
Контроль пройден.

метод решения:

В N полученных числах ищем:

  • максимальное значение,
  • максимальные значение кратное шести (если есть)
  • максимальные значение кратное трем (если есть)
  • максимальные значение кратное двум (если есть)

из этих полученных чисел формируем максимальное контрольное значение, сравниваем с полученным.

11. «Последовательность чисел»
Анализ последовательности чисел, выделение в ней участка с наибольшим «подъемом».

Текст задачи:
По каналу связи передается последовательность положительных целых чисел X1, X2 …, все числа не превышают 1000, их количество заранее неизвестно. Каждое число передается в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0. Участок последовательности от элемента XT до элемента XT-N называется подъемом, если на этом участке каждое следующее число больше предыдущего. Высотой подъема называется разность XT-N - XT Напишите эффективную программу, которая вычисляет наибольшую высоту среди всех подъемов последовательности. Если в последовательности нет ни одного подъема, программа выдает 0.

Программа должна напечатать отчет по следующей форме:
Получено ... чисел
Наибольшая высота подъема: …
Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел.

метод решения:

  • задаем максимальную высоту подъема равную нулю
  • в цикле While() получаем числа пока не получим 0. Всякий раз сохраняем предыдущее значение.
  • Получив новое число, которое больше предыдущего считаем, что это - новый подъем, вычисляем его текущую высоту.
  • По окончании подъема сравниваем его с текущим максимальным, в случае если текущий подъем больше - перееопределяем значение.

P.S.

Подробное обсуждение нескольких последних задач C4 можно найти в сервисе «Подготовка к ЕГЭ»: http://www.titorov.ru/ege/