Группы ExamExt и ExamFExt содержат задания, аналогичные тем которые предлагались на ЕГЭ по информатике в качестве задач повышенной сложности. Начальную часть данной группы составляют задания на обработку сложных наборов данных (записей) с элементами-полями различных типов. В подобных заданиях требуется правильно выбрать способ хранения данных и организовать их эффективную обработку; при этом обычно требуется применить несколько базовых алгоритмов, например, алгоритм суммирования или нахождения минимума/максимума и алгоритм поиска нужного элемента или сортировки набора данных по требуемому ключу.

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

В заданиях групп ExamExt и ExamFExt ввод и вывод имеет те же особенности, что и в заданиях групп ExamBase и ExamFBase. Подобно группам ExamBase и ExamFBase, группы ExamExt и ExamFExt отличаются только способом ввода исходных данных (в заданиях группы ExamFExt исходные данные требуется читать их текстового файла).

Рассмотрим следующее задание.

ExamExt25°. На вход подаются сведения об абитуриентах. В первой строке указывается количество абитуриентов N, каждая из последующих N строк имеет формат
<Номер школы> <Год поступления> <Фамилия>
Номер школы содержит не более двух цифр, годы лежат в диапазоне от 1990 до 2010. Для каждого года, присутствующего в исходных данных, вывести общее число абитуриентов, поступивших в этом году (вначале выводить год, затем число абитуриентов). Сведения о каждом годе выводить на новой строке и упорядочивать по возрастанию номера года.

Программа-заготовка, созданная для этого задания, подобно заготовкам для заданий группы ExamBase, будет использовать специальный модуль PT4Exam:

from pt4exam import *
# Для ввода используйте функцию input()
# Для вывода используйте функцию print()
# Между полученными результатами надо выводить символ пробела
def solve():
    task("ExamExt25")

start(solve)

При запуске этой программы на экране появится окно задачника, содержащее следующие данные:

Окно будет иметь такой вид, если при его предшествующем закрытии оно находилось в режиме отображения всех данных. Для отображения всех данных на экране может потребоваться увеличить высоту окна; для этого достаточно зацепить мышью заголовок окна и переместить его вверх (для перемещения заголовка окна задачника вверх и вниз можно также воспользоваться клавиатурными комбинациями [Ctrl]+{Up] и [Ctrl]+[Down]).

При первом тестовом испытании программы ей будет предложен для обработки набор данных не слишком большого размера (порядка 10–20 элементов).

Вначале следует определиться со структурами данных, которые будут использоваться в программе. Поскольку требуется найти одну характеристику для каждого года, при использовании языка Python удобнее всего использовать словарь (dictionary), ключами в котором будут значения лет, а значениями — количество абитуриентов, поступивших в этом году.

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

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

Приведем первый вариант решения, содержащий одну ошибку (здесь и далее будем приводить только текст функции solve):

def solve():
    task("ExamExt25")
    year = dict()
    for i in range(int(input())):
        y = int(input().split()[1])
        if y in year:
            year[y] += 1
        else:
            year[y] = 1
    for y in year:
        print(y, year[y])

Ошибка связана с тем, что данные выводятся не в порядке возрастания годов (для большей наглядности приведем окно задачника в режиме сокращенного отображения данных, при котором выводятся только пять первых элементов из каждого набора данных):

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

Для исправления ошибки достаточно использовать вспомогательный список ключей, отсортированный по возрастанию:

def solve():
    task("ExamExt25")
    year = dict()
    for i in range(int(input())):
        y = int(input().split()[1])
        if y in year:
            year[y] += 1
        else:
            year[y] = 1
    a = list(year)
    a.sort()
    for y in a:
        print(y, year[y])

Примечание. Вместо сортировки ключей можно было бы перебрать все возможные значения годов (от 1990 до 2010) и вывести данные только для тех значений, которые входят в список ключей словаря year:

def solve():
    task("ExamExt25")
    year = dict()
    for i in range(int(input())):
        y = int(input().split()[1])
        if y in year:
            year[y] += 1
        else:
            year[y] = 1
    for y in range(1990, 2011):
        if y in year:
            print(y, year[y])

Теперь все 9 тестовых испытаний программы, требуемых для того, чтобы решение было зачтено как выполненное, будут пройдены успешно.

Завершая рассмотрение этого задания, опишем некоторые дополнительные возможности, связанные с просмотром больших наборов данных.

Начиная со второго испытания, программе может быть предложен для обработки набор исходных данных большего размера (порядка 50–100 элементов). При этом уже не удастся отобразить на экране все данные, связанные с заданием. В подобной ситуации у правой границы окна задачника появится полоса прокрутки, позволяющая перемещаться к той части данных, которая первоначально не отображается на экране. Прокрутку данных можно выполнять не только с помощью полосы прокрутки, но и используя клавиши со стрелками, [PgUp], [PgDn], [Home], [End], а также колесико мыши.

Помимо стандартных действий по прокрутке данных, в окне задачника предусмотрены возможности «интеллектуальной» прокрутки, позволяющие быстро перейти к началу каждого раздела задания, а также сравнить соответствующие фрагменты полученных результатов и примера верного решения. Для циклического перебора разделов сверху вниз предназначена клавиша [+] (а также комбинация [Ctrl]+[PgDn]), для циклического перебора разделов снизу вверх — клавиша [–] (а также комбинация [Ctrl]+[PgUp]). Для быстрого переключения между соответствующими фрагментами разделов с результатами и с примером верного решения предназначена клавиша [/] (а также комбинация [Ctrl]+[Tab]). Все эти действия можно выполнить и с помощью мыши; для этого предусмотрены кнопки в левом верхнем углу прокручиваемой области окна, отведенной под отображение разделов задания (эти кнопки отображаются на экране, если размер данных, связанных с заданием, превышает размеры окна). Приведем вид окна задачника с полосой прокрутки и дополнительными кнопками:

Обозначения на кнопках совпадают с клавишами, выполняющими те же действия; при наведении мышью на кнопку рядом с ней появляется всплывающая подсказка.

Кроме трех кнопок, связанных с «интеллектуальной» прокруткой, в приведенном на рисунке окне отображаются еще две дополнительные кнопки. Первая из них располагается в правом верхнем углу раздела с формулировкой и позволяет временно скрыть (а в дальнейшем опять отобразить) раздел с формулировкой (эти же действия можно выполнить с помощью клавиши [Del] или двойного щелчка мышью на разделе с формулировкой). Вторая дополнительная кнопка расположена в правом верхнем углу раздела с исходными данными. Как уже отмечалось ранее, эта кнопка позволяет переключаться между полным и сокращенным отображением наборов данных. Напомним, что изображение на этой кнопке показывает текущий режим отображения данных. Например, если на кнопке изображена стилизованная стрелка, направленная вверх (как на приведенном выше рисунке), значит, в данный момент в окне отображаются все данные, а нажатие на эту кнопку переведет окно в режим отображения нескольких начальных (как правило, пяти) элементов каждого набора данных.

Решение с файловым вводом исходных данных

Приведем решение, в котором используется ввод данных из текстового файла (соответствующая задача имеет имя ExamFExt25).

from pt4exam import *
# Исходные данные следует вводить с помощью функций файлового ввода
# Для вывода используйте функцию print()
# Между полученными результатами надо выводить символ пробела
def solve():
    task("ExamFExt25")
    filename = get_str() # имя исходного файла
    f = open(filename, 'r')
    year = dict()
    line = f.readline().split()
    m = int(line[0])
    for i in range(m):
        line = f.readline().split()
        y = int(line[1])
        if y in year:
            year[y] += 1
        else:
            year[y] = 1
    f.close()
    a = list(year)
    a.sort()
    for y in a:
        print(y, year[y]) 

start(solve)

После проверки программы на девяти наборах тестовых данных будет выведено сообщение о том, что задание выполнено:

Теперь рассмотрим более сложное задание.

ExamExt53°. На вход подаются сведения о ценах на бензин на автозаправочных станциях (АЗС). В первой строке содержится значение M одной из марок бензина, во второй строке указывается целое число N, а каждая из последующих N строк имеет формат
<Марка бензина> <Улица> <Компания> <Цена 1 литра (в копейках)>
Имеется не более 20 различных компаний и не более 30 различных улиц; названия компаний и улиц не содержат пробелов. В качестве марки бензина указываются числа 92, 95 или 98. Цена задается целым числом в диапазоне от 2000 до 3000. Каждая компания имеет не более одной АЗС на каждой улице; цены на разных АЗС одной и той же компании могут различаться. Для каждой улицы, на которой имеются АЗС с бензином марки M, определить максимальную цену бензина этой марки (вначале выводить максимальную цену, затем название улицы). Сведения о каждой улице выводить на новой строке и упорядочивать по возрастанию максимальной цены, а для одинаковой цены — по названиям улиц в алфавитном порядке. Если ни одной АЗС с бензином марки M не найдено, то вывести текст «No».

Приведем окно задачника, которое появится на экране при запуске программы-заготовки для данного задания (в данном окне скрыт раздел с формулировкой; в результате оказались скрытыми и кнопки, отвечающие за «интеллектуальную» прокрутку, поскольку в окне полностью отображается содержимое оставшихся разделов):

Выясним, какая структура является наиболее подходящей для хранения информации, необходимой для решения задачи. Нам требуется информация, связанная с различными улицами, причем для каждой улицы надо хранить сведения двух видов: ее название и максимальную цену бензина марки M. Поэтому в данном случае также удобно использовать словарь streets, ключами которого будут названия улиц, а значениями — максимальные цены безнина марки M для АЗС, расположенных на данной улице.

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

Если улица с названием s еще не была включена в словарь streets, то ее необходимо включить в него, указав в качестве значения данного элемента словаря значение переменной p. Если же улица уже присутствует в словаре, то необходимо сравнить значение соответствующего элемента словаря и значение p, изменив при необходимости значение элемента (здесь мы используем базовый алгоритм нахождения максимального значения).

После обработки набора исходных данных необходимо проверить, найдена ли хотя бы одна улица с АЗС, предлагающей марку бензина M (для этого достаточно сравнить количество элементов словаря streets с нулем). Если ни одна улица не найдена, то надо вывести строку «No»; в противном случае требуется выполнить сортировку данных по указанному в условии задачи правилу и вывести полученные данные в требуемом порядке. Поскольку размер полученного набора данных невелик, для его сортировки вполне допустимо использовать один из простых алгоритмов, например, алгоритм пузырьковой сортировки. Предварительно необходимо преобразовать словарь методом items в список пар (кортежей); первым элементом каждой пары является ключ словаря (в нашем случае название улицы), вторым элементом — значение словаря (в нашем случае цена).

Приведем один из вариантов правильного решения задачи:

# Для ввода используйте функцию input()
# Для вывода используйте функцию print()
# Между полученными результатами надо выводить символ пробела
def solve():
    task("ExamExt53")
    streets = dict()
    m = int(input())
    for i in range(int(input())):
        a = input().split()
        if int(a[0]) == m:
            s, p = a[1], int(a[3])
            if s in streets:
                if p > streets[s]:
                    streets[s] = p
            else:
                streets[s] = p
    if len(streets) == 0:
        print("No")
    else:
        # Сортировка по возрастанию максимальной цены,
        # а для одинаковых цен - по названиям улиц
        a = list(streets.items())
        for k in range(len(a)-1):
            for i in range(len(a)-k-1):
                s1, p1 = a[i]
                s2, p2 = a[i+1]
                if p1 > p2 or p1 == p2 and s1 > s2:
                    a[i], a[i+1] = a[i+1], a[i]
        # Вывод результатов в требуемом порядке
        for e in a:
            print(e[1], e[0])

Примечание 1. Вместо явной реализации алгоритма сортировки можно воспользоваться стандартным методом sort или функцией sorted, которые предусмотрены для списков (метод a.sort(), ранее использованный нами при решении задачи ExamExt25, сортирует исходный список a, тогда как функция sorted(a) возвращает отсортированную копию списка а). Поскольку в нашем случае все цены имеют одинаковое число десятичных знаков, можно, например, сформировать список строк, содержащих цену бензина и название улицы (в указанном порядке), после чего отсортировать и вывести полученные строки:

        a = [str(streets[e]) + " " + e for e in streets]
        for e in sorted(a):
            print(e)

Примечание 2. Стандартные методы sort и sorted можно использовать и для сортировки сложных наборов данных по набору ключей. Для этого достаточно выполнить несколько вызовов этих методов, сортируя данные отдельно по каждому ключу сортировки и перебирая эти ключи в обратном порядке (от подчиненных к главному). Например, если требуется отсортировать данные об учащихся по классам, а в пределах каждого класса — по фамилии, то надо вначале выполнить сортировку по фамилиям, а затем полученную последовательность отсортировать по классам. Такой способ будет давать правильный результат, если алгоритм сортировки не изменяет относительное расположение элементов с одинаковыми значениями ключа сортировки (это свойство алгоритма сортировки называется устойчивостью; методы sort и sorted реализуют устойчивый алгоритм сортировки). Для указания ключа, по которому требуется проводить сортировку, в методах sort и sorted предусмотрен именованный параметр key. Если в качестве ключа надо указать одно из полей кортежа, то в качестве параметра key достаточно указать функцию itemgetter(n), где n обозначает индекс требуемого поля. Для возможности использования функции itemgetter необходимо ее импортировать из модуля operator, используя, например, директиву from operator import itemgetter.

Для того чтобы воспользоваться описанной выше дополнительной возможностью метода sort при решении задачи ExamExt53, достаточно, как и в первом варианте решения (с явной реализацией алгоритма пузырьковой сортировки), преобразовать словарь streets методом items в список кортежей и учесть, что в полученном списке первое поле кортежа (название улицы) имеет индекс 0, а второе (максимальная цена бензина) имеет индекс 1:

        a = list(streets.items())
        a.sort(key = itemgetter(0))
        a.sort(key = itemgetter(1))
        for e in a:
            print(e[1], e[0])

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

from operator import itemgetter

Примечание 3. Описанный в примечании 2 прием сортировки сложных наборов данных особенно удобен в случае, если для одних полей требуется выполнить сортировку по возрастанию, а для других — по убыванию. Для настройки методов sort и sorted на сортировку по убыванию достаточно использовать еще один именованный параметр: reverse=True (если параметр reverse отсутствует или равен False, то выполняется сортировка по возрастанию). Если по всем полям требуется выполнить сортировку одного типа (или только по возрастанию, или только по убыванию), то можно обойтись без многократного вызова sort или sorted, используя функцию itemgetter с несколькими параметрами — индексами ключей сортировки (первым указывается главный индекс). В нашем случае получаем:

        a = list(streets.items())
        a.sort(key = itemgetter(1, 0))
        for e in a:
            print(e[1], e[0])

В заключение приведем наиболее краткий вариант завершающего фрагмента программы, обеспечивающего сортировку и вывод полученного набора данных:

        for e in sorted(streets.items(), key = itemgetter(1, 0)):
            print(e[1], e[0])

Решение с файловым вводом исходных данных

Как и для предыдущей задачи, приведем решение, в котором используется ввод данных из текстового файла (соответствующая задача имеет имя ExamFExt53).

from pt4exam import *
# Исходные данные следует вводить с помощью функций файлового ввода
# Для вывода используйте функцию print()
# Между полученными результатами надо выводить символ пробела
def solve():
    task("ExamFExt53")
    filename = get_str() # имя исходного файла
    f = open(filename, 'r')
    streets = dict()
    line = f.readline().split()
    m = int(line[0])
    line = f.readline().split()
    for i in range(int(line[0])):
        a = f.readline().split()
        if int(a[0]) == m:
            s, p = a[1], int(a[3])
            if s in streets:
                if p > streets[s]:
                    streets[s] = p
            else:
                streets[s] = p
    f.close()
    if len(streets) == 0:
        print("No")
    else:
        # Сортировка по возрастанию максимальной цены,
        # а для одинаковых цен - по названиям улиц
        a = list(streets.items())
        for k in range(len(a)-1):
            for i in range(len(a)-k-1):
                s1, p1 = a[i]
                s2, p2 = a[i+1]
                if p1 > p2 or p1 == p2 and s1 > s2:
                    a[i], a[i+1] = a[i+1], a[i]
        # Вывод результатов в требуемом порядке
        for e in a:
            print(e[1], e[0])

start(solve)

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024