Межрегиональные предметные олимпиады КФУ по информатике
Межрегиональные предметные олимпиады КФУ проводятся осенью и весной. Победители и призёры олимпиады получают дополнительные баллы к ЕГЭ. Отборочный этап по профилю «Информатика» проводится онлайн...
Межрегиональные предметные олимпиады КФУ проводятся осенью и весной. Победители и призёры олимпиады получают дополнительные баллы к ЕГЭ.
Отборочный этап по профилю «Информатика» проводится онлайн в системе тестирования PCMS пос-
ле регистрации на сайте https://abiturient.kpfu.ru. Задания размещаются тремя пакетами по 5 задач в каждом и доступны с момента размещения до момента окончания отборочного этапа. Сумма баллов за отборочный этап высчитывается при условии выполнения всех трёх пакетов задач.
Для проверки задачи отправляются исходные коды программы, которые проверяются на наборе тестов, и, исходя из количества пройденных тестов, выставляются баллы за задачу. За каждую задачу участник может получить максимум 100 баллов. Максимальное количество баллов за выполнение трёх пакетов задач –
1500. Список доступных компиляторов в тестирующей системе: С++, Java, Python, Pascal.
Для каждой задачи необходимо написать программу на одном из предложенных языков программирования: C, C++, Python, Java, C#, Pascal, алгоритмический язык.
Для каждой задачи временное ограничение: 2 секунды (время работы программы).
Для каждой задачи ограничение по памяти: 256 Мб (память, выделяемая на работу программы).
Разбор задач
1-я задача. На заводе по производству наборов сладостей наборы составляются следующим образом: изначально в набор кладут k сладостей, цены которых a1,…ak, затем, чтобы уравнять получившийся набор с другими N наборами на складе, этот набор сравнивают со всеми наборами на складе в порядке нумерации (наборы пронумерованы от 1 до N) и делают следующую операцию: если самая дорогая сладость в новом наборе дороже самой дорогой из i-го набора со склада, то надо самую дорогую из нового набора поменять на самую дешёвую из i-го набора со склада. Какова будет суммарная стоимость набора после такого «уравнивания»?
Входные данные. В первой строке дано k – количество сладостей в новом наборе, затем k чисел через пробел a1,…ak – стоимости сладостей в наборе. В третьей строке даётся N –
число подарков на складе, затем N строк по 2 числа в строке – стоимость самой дорогой и самой дешёвой сладости в i-ом наборе на складе. Все заданные числа положительные целые.
1<N<300 000,
1<k<300 000,
1<ai<109
Выходные данные. Итоговая стоимость набора.
Пример
Разбор. Для решения данной задачи используется такая структура данных, как упорядоченное бинарное дерево. На языке С++ такой структуре может соответствовать тип данных multiset (обычный set не подойдёт, так как цены могут быть одинаковыми). Такая структура позволяет за O(log k) получать значение, удалять некоторое значение и добавлять новое во множестве размера k.
В multiset мы будем хранить сладости из собираемого набора. Для каждого набора со склада мы сравниваем максимальное значение в multiset, которое мы получаем из множества за O(log k), *st.begin() (multiset st) с максимальным значением из набора со склада. Если значение из множества больше, удаляем его во множестве и кладём новое значение, равное максимальному значению со склада.
В конце проходим по множеству и считаем сумму его элементов.
Для заданных ограничений 9 и 10 класса подойдёт обычный перебор. Для каждого набора со склада ищем максимальное значение в массиве нового набора, заменяем максимальное значение, если оно больше, чем максимальное значение i-ого набора. В конце считаем сумму элементов массива.
Для ограничений 9 и 10 класса подойдёт моделирование ситуации на «быстрых языках программирования». Сложность O(N*k).
2-я задача. В отеле поселились n групп туристов, которые хотят поехать на экскурсию. Для i-ой группы определены время начала экскурсии si и завершения экскурсии fi (оба времени включительно). Чтобы группе туристов поехать на экскурсию, нужен один автобус. Группа занимает его полностью. Но один автобус может отвезти несколько групп туристов, если их время экскурсий не пересекается. Определите минимальное число автобусов, которое нужно заказать отелю, для того чтобы обслужить все группы туристов.
Входные данные. В первой строке задано целое число n – количество групп туристов. Далее в n строках пары целых чисел si, fi через пробел – время начала и конца экскурсии.
1<n<100 000
0<si<fi<109 (времена заданы в виде целых чисел, в секундах).
Выходные данные. Выведите минимальное число автобусов.
Пример
Разбор. Сохраняем значения всех времён в одном массиве с отметкой, какое время является началом экскурсии, а какой концом. Например, можно использовать структуру
данных pair в C++, где первое значение – значение времени, второе –
0 (начало экскурсии) или 1 (конец экскурсии). На языке Pascal можно описать свою структуру данных через type record.
Сортируем массив пар по возрастанию. Проходимся по массиву: если какая-то экскурсия началась, увеличиваем количество автобусов, если закончилась, уменьшаем количество автобусов. Ответом будет максимальное значение автобусов за всё время.
По изображению мы видим, что максимальное количество автобусов, которое было за всё время, равно 2, это и будет ответом. Автобус, который отвёз оранжевую группу на экскурсию, сможет отвезти и зелёную группу на экскурсию.
Для ограничений 9 и 10 класса можно использовать пузырьковую сортировку. Ограничения 11 класса требуют использовать сортировки, работающие за O(N log N).
3-я задача. Астрономы часто изучают карты звёзд, где звёзды представлены точками на плоскости, и каждая звезда имеет декартовы координаты (xi,yi). На карте находится N звёзд. Астрономы называют уровнем звезды количество звёзд, которые не выше и не правее этой звезды. Астрономы хотят знать распределение уровней звёзд. Напишите программу, которая считает количество звёзд каждого из уровней от 0 до N-1.
Входные данные. В первой строке находится одно целое число N – количество звёзд.
В каждой из следующих N строках находятся по два целых числа xi, yi – координаты звёзд.
1<N<1000
0<X<10000
0<Y<10000, i=1, …, N
Гарантируется, что в одной точке не находятся две звезды.
Выходные данные. Выведите N чисел каждое в отдельную строку, где i-ое число – это количество звёзд (i-1)-го уровня.
Пример.
Пояснение. У звезды с координатами (1, 1) уровень 0, потому что нет звёзд ни выше и ни правее её. У звезды (5, 1) уровень 1, есть только одна звезда (1, 1) не выше и не правее её. У звезды (7, 1) уровень 2, есть две звезды (1, 1) и (5, 1) не выше и не правее её. У звезды (3, 3) уровень 1, есть одна звезда (1, 1) не выше и не правее её. У звезды (5, 5) уровень 3, есть три звезды (1, 1), (3, 3) и (5, 1) не выше и не правее её. Итого уровень 0 у 1-й звезды, уровень 1 у 2-х звёзд, уровень 2 у 1-й звезды, уровень 3 у 1-й звезды, и уровень 4 у 0 звёзд.
Разбор. Объявим массив целых чисел Levels[N], где нумерация будет от 0 до N-1, и обнулим его. Храним все точки в массиве пар. Сортируем массив по значению X. Для каждой i-ой звезды в отрезке от 0 до i-1 проверяем значения yi ≥ yj для j = [1, .., i-1], считаем количество таких yj, записываем полученное количество в k. Levels[k], увеличиваем на 1. И так для каждой звезды. Сложность O(N2).
Для ограничений всех классов подойдёт переборный алгоритм. Нужно для каждой i-ой звезды проверять условия, что звезда j не правее и не выше, а также j не равно i.
4-я задача. Василий проверяет скобочные последовательности. Правильной скобочной последовательностью называется такая строка из открывающихся и закрывающихся скобок, в которую можно подставить символы 1 и + так, чтобы получилось верное арифметическое выражение. Например, (()()) – правильная скобочная последовательность. Потому что можно составить арифметическое выражение 1+((1+1)+(1+1)). А вот (())) неправильная скобочная последовательность.
У Василия есть строка s, состоящая только из круглых скобок. Помогите Василию найти максимальную длину префикса строки s, являющегося правильной скобочной последовательностью. Префиксом строки называется часть строки, которая начинается с первого символа и заканчивается на каком-то другом символе. Формально, если строка состоит из символов s1...sn, то префикс это s1...si для некоторого i. Сама строка тоже является префиксом самой себя.
Входные данные. Единственная строка содержит строку s. Длина строки не превышает 105.
Выходные данные. Выведите максимальную длину префикса, являющегося правильной скобочной последовательностью. Если таких префиксов нет, то выведите 0.
Пример
Пояснение к первому примеру. Есть два префикса, являющихся правильной скобочной последовательностью, () и ()(()(())). При этом у второго из них длина больше.
Пояснение к третьему примеру. Вся строка является правильной скобочной последовательностью, она же является префиксом, поэтому ответ – длина строки.
Разбор. Поддерживаем разность открывающихся и закрывающихся скобок. Если у нас разность стала отрицательна, то ответ текущая позиция -1. Если дошли до конца, и разность не была отрицательна, и сейчас она не 0, тогда нет ответа (ответ 0). Если дошли до конца строки, и разность равна 0, тогда ответ – длина строки.
Большинство участников искали максимальную правильную подстроку в строке. Это неверно. Задача состояла в поиске правильного префикса.
5-я задача. Фаниль собирается отправиться к бабушке в деревню. Деревня бабушки Фаниля очень далеко от Казани. Возможно, ему придётся ехать на нескольких автобусах. Фаниль знает информацию о всех m автобусах и n станциях в округе. Каждый i-ый автобус едет без остановок от станции ai до станции bi и путь этой длины pi. Автобус едет только в одном направлении. Длиной пути от Казани до деревни Фаниль называет суммарную длину всех путей автобусов, на которых он ехал. При этом если Фаниль доехал до какой-нибудь остановки, он на ней же должен сесть на следующий автобус, пока не доберётся до деревни. Помогите Фанилю найти длину кратчайшего пути из Казани до деревни бабушки. Если таких путей несколько, выберите путь, который состоит из максимального количества пересадок, чтобы Фаниль смог полюбоваться красотой каждой станции.
Входные данные. В первой строке заданы два целых числа n и m – количество станций и автобусов, которые могут быть полезны для поездки Фаниля. Во второй строке заданы два целых числа a и b: a – номер станции в Казани, b – номер станции в деревне у бабушки Фаниля (1<a, b <n). В следующих m строках заданы тройки целых положительных чисел ai, bi, pi, описывающие станции, которые соединены автобусным маршрутом, и длина пути между ними. Имейте в виду, что автобус едет только в одну сторону.
1<n<100
1<m<10 000
1<pi<109
Выходные данные. В первой строке выведите единственное целое число – длину кратчайшего пути из Казани (станция с номером a) до деревни бабушки Фаниля (станция с номером b). В следующей строке выведите путь –
номера станций по очереди через пробел, через которые едет Фаниль в порядке следования. Гарантируется, что такой путь существует. Если таких путей несколько, выведите путь, который содержит в себе максимальное число станций.
Пример.
Пояснение. Есть два кратчайших пути длины 9: это путь через 1 и 5 и путь через станции 1, 3, 4 и 5. Необходимо выдать второй из них, так как в нём больше станций.
Разбор. Для решения задачи используем алгоритм Дейкстры. Для каждой вершины храним количество вершин, из которых мы пришли в эту вершину. Пусть массив P[N] будет хранить количество таких вершин-родителей. Пусть массив Par[N] – массив родителей. Par[i] – номер вершины, из которой мы пришли в вершину i. Для вершины a P[a]=0. Когда мы производим релаксацию по рёбрам, увеличиваем P[e.to]=P[v]+1, где v – выбранная вершина с минимальным расстоянием, а e ребро, исходящее из вершины v, e.to – номер смежной v вершины.
При выборе минимальной вершины v, выбираем ту, у которой количество вершин-родителей больше:
for jЄV
if !used[j] and (v == null or d[j] < d[v] or d[j]==d[v] and P[j]>P[v])
v = j
for e: исходящие из v ребра
if d[v] + e.len < d[e.to]
d[e.to] = d[v] + e.len
P[e.to] = P[v] + 1
Par[e.to] = v
Длина пути будет сохранена в d[b]. Путь можно восстановить рекурсивно или итеративно с помощью массива Par.
Некоторые участники не учитывали, что цикл в графе не исключён. Классические алгоритмы dfs и bfs либо не проверяли все пути, либо зацикливались. Такие алгоритмы считаются неверными решениями.
Отборочный этап по профилю «Информатика» проводится онлайн в системе тестирования PCMS пос-
ле регистрации на сайте https://abiturient.kpfu.ru. Задания размещаются тремя пакетами по 5 задач в каждом и доступны с момента размещения до момента окончания отборочного этапа. Сумма баллов за отборочный этап высчитывается при условии выполнения всех трёх пакетов задач.
Для проверки задачи отправляются исходные коды программы, которые проверяются на наборе тестов, и, исходя из количества пройденных тестов, выставляются баллы за задачу. За каждую задачу участник может получить максимум 100 баллов. Максимальное количество баллов за выполнение трёх пакетов задач –
1500. Список доступных компиляторов в тестирующей системе: С++, Java, Python, Pascal.
Для каждой задачи необходимо написать программу на одном из предложенных языков программирования: C, C++, Python, Java, C#, Pascal, алгоритмический язык.
Для каждой задачи временное ограничение: 2 секунды (время работы программы).
Для каждой задачи ограничение по памяти: 256 Мб (память, выделяемая на работу программы).
Разбор задач
1-я задача. На заводе по производству наборов сладостей наборы составляются следующим образом: изначально в набор кладут k сладостей, цены которых a1,…ak, затем, чтобы уравнять получившийся набор с другими N наборами на складе, этот набор сравнивают со всеми наборами на складе в порядке нумерации (наборы пронумерованы от 1 до N) и делают следующую операцию: если самая дорогая сладость в новом наборе дороже самой дорогой из i-го набора со склада, то надо самую дорогую из нового набора поменять на самую дешёвую из i-го набора со склада. Какова будет суммарная стоимость набора после такого «уравнивания»?
Входные данные. В первой строке дано k – количество сладостей в новом наборе, затем k чисел через пробел a1,…ak – стоимости сладостей в наборе. В третьей строке даётся N –
число подарков на складе, затем N строк по 2 числа в строке – стоимость самой дорогой и самой дешёвой сладости в i-ом наборе на складе. Все заданные числа положительные целые.
1<N<300 000,
1<k<300 000,
1<ai<109
Выходные данные. Итоговая стоимость набора.
Пример
| INPUT | OUTPUT |
| 5 3 4 2 10 3 3 11 1 3 2 3 2 | 12 |
Разбор. Для решения данной задачи используется такая структура данных, как упорядоченное бинарное дерево. На языке С++ такой структуре может соответствовать тип данных multiset (обычный set не подойдёт, так как цены могут быть одинаковыми). Такая структура позволяет за O(log k) получать значение, удалять некоторое значение и добавлять новое во множестве размера k.
В multiset мы будем хранить сладости из собираемого набора. Для каждого набора со склада мы сравниваем максимальное значение в multiset, которое мы получаем из множества за O(log k), *st.begin() (multiset
В конце проходим по множеству и считаем сумму его элементов.
Для заданных ограничений 9 и 10 класса подойдёт обычный перебор. Для каждого набора со склада ищем максимальное значение в массиве нового набора, заменяем максимальное значение, если оно больше, чем максимальное значение i-ого набора. В конце считаем сумму элементов массива.
Для ограничений 9 и 10 класса подойдёт моделирование ситуации на «быстрых языках программирования». Сложность O(N*k).
2-я задача. В отеле поселились n групп туристов, которые хотят поехать на экскурсию. Для i-ой группы определены время начала экскурсии si и завершения экскурсии fi (оба времени включительно). Чтобы группе туристов поехать на экскурсию, нужен один автобус. Группа занимает его полностью. Но один автобус может отвезти несколько групп туристов, если их время экскурсий не пересекается. Определите минимальное число автобусов, которое нужно заказать отелю, для того чтобы обслужить все группы туристов.
Входные данные. В первой строке задано целое число n – количество групп туристов. Далее в n строках пары целых чисел si, fi через пробел – время начала и конца экскурсии.
1<n<100 000
0<si<fi<109 (времена заданы в виде целых чисел, в секундах).
Выходные данные. Выведите минимальное число автобусов.
Пример
| INPUT | OUTPUT |
| 53 6 4 7 1 3 8 9 1 10 | 3 |
Разбор. Сохраняем значения всех времён в одном массиве с отметкой, какое время является началом экскурсии, а какой концом. Например, можно использовать структуру
данных pair в C++, где первое значение – значение времени, второе –
0 (начало экскурсии) или 1 (конец экскурсии). На языке Pascal можно описать свою структуру данных через type record.
Сортируем массив пар по возрастанию. Проходимся по массиву: если какая-то экскурсия началась, увеличиваем количество автобусов, если закончилась, уменьшаем количество автобусов. Ответом будет максимальное значение автобусов за всё время.
По изображению мы видим, что максимальное количество автобусов, которое было за всё время, равно 2, это и будет ответом. Автобус, который отвёз оранжевую группу на экскурсию, сможет отвезти и зелёную группу на экскурсию.
Для ограничений 9 и 10 класса можно использовать пузырьковую сортировку. Ограничения 11 класса требуют использовать сортировки, работающие за O(N log N).
3-я задача. Астрономы часто изучают карты звёзд, где звёзды представлены точками на плоскости, и каждая звезда имеет декартовы координаты (xi,yi). На карте находится N звёзд. Астрономы называют уровнем звезды количество звёзд, которые не выше и не правее этой звезды. Астрономы хотят знать распределение уровней звёзд. Напишите программу, которая считает количество звёзд каждого из уровней от 0 до N-1.
Входные данные. В первой строке находится одно целое число N – количество звёзд.
В каждой из следующих N строках находятся по два целых числа xi, yi – координаты звёзд.
1<N<1000
0<X<10000
0<Y<10000, i=1, …, N
Гарантируется, что в одной точке не находятся две звезды.
Выходные данные. Выведите N чисел каждое в отдельную строку, где i-ое число – это количество звёзд (i-1)-го уровня.
Пример.
| INPUT | OUTPUT |
| 5 1 1 5 1 7 1 3 3 5 5 | 1 2 1 1 0 |
Пояснение. У звезды с координатами (1, 1) уровень 0, потому что нет звёзд ни выше и ни правее её. У звезды (5, 1) уровень 1, есть только одна звезда (1, 1) не выше и не правее её. У звезды (7, 1) уровень 2, есть две звезды (1, 1) и (5, 1) не выше и не правее её. У звезды (3, 3) уровень 1, есть одна звезда (1, 1) не выше и не правее её. У звезды (5, 5) уровень 3, есть три звезды (1, 1), (3, 3) и (5, 1) не выше и не правее её. Итого уровень 0 у 1-й звезды, уровень 1 у 2-х звёзд, уровень 2 у 1-й звезды, уровень 3 у 1-й звезды, и уровень 4 у 0 звёзд.
Разбор. Объявим массив целых чисел Levels[N], где нумерация будет от 0 до N-1, и обнулим его. Храним все точки в массиве пар. Сортируем массив по значению X. Для каждой i-ой звезды в отрезке от 0 до i-1 проверяем значения yi ≥ yj для j = [1, .., i-1], считаем количество таких yj, записываем полученное количество в k. Levels[k], увеличиваем на 1. И так для каждой звезды. Сложность O(N2).
Для ограничений всех классов подойдёт переборный алгоритм. Нужно для каждой i-ой звезды проверять условия, что звезда j не правее и не выше, а также j не равно i.
4-я задача. Василий проверяет скобочные последовательности. Правильной скобочной последовательностью называется такая строка из открывающихся и закрывающихся скобок, в которую можно подставить символы 1 и + так, чтобы получилось верное арифметическое выражение. Например, (()()) – правильная скобочная последовательность. Потому что можно составить арифметическое выражение 1+((1+1)+(1+1)). А вот (())) неправильная скобочная последовательность.
У Василия есть строка s, состоящая только из круглых скобок. Помогите Василию найти максимальную длину префикса строки s, являющегося правильной скобочной последовательностью. Префиксом строки называется часть строки, которая начинается с первого символа и заканчивается на каком-то другом символе. Формально, если строка состоит из символов s1...sn, то префикс это s1...si для некоторого i. Сама строка тоже является префиксом самой себя.
Входные данные. Единственная строка содержит строку s. Длина строки не превышает 105.
Выходные данные. Выведите максимальную длину префикса, являющегося правильной скобочной последовательностью. Если таких префиксов нет, то выведите 0.
Пример
| INPUT | OUTPUT |
| ()(()(()))) | 10 |
| ))))(((((((( | 0 |
| ()(()) | 6 |
Пояснение к первому примеру. Есть два префикса, являющихся правильной скобочной последовательностью, () и ()(()(())). При этом у второго из них длина больше.
Пояснение к третьему примеру. Вся строка является правильной скобочной последовательностью, она же является префиксом, поэтому ответ – длина строки.
Разбор. Поддерживаем разность открывающихся и закрывающихся скобок. Если у нас разность стала отрицательна, то ответ текущая позиция -1. Если дошли до конца, и разность не была отрицательна, и сейчас она не 0, тогда нет ответа (ответ 0). Если дошли до конца строки, и разность равна 0, тогда ответ – длина строки.
Большинство участников искали максимальную правильную подстроку в строке. Это неверно. Задача состояла в поиске правильного префикса.
5-я задача. Фаниль собирается отправиться к бабушке в деревню. Деревня бабушки Фаниля очень далеко от Казани. Возможно, ему придётся ехать на нескольких автобусах. Фаниль знает информацию о всех m автобусах и n станциях в округе. Каждый i-ый автобус едет без остановок от станции ai до станции bi и путь этой длины pi. Автобус едет только в одном направлении. Длиной пути от Казани до деревни Фаниль называет суммарную длину всех путей автобусов, на которых он ехал. При этом если Фаниль доехал до какой-нибудь остановки, он на ней же должен сесть на следующий автобус, пока не доберётся до деревни. Помогите Фанилю найти длину кратчайшего пути из Казани до деревни бабушки. Если таких путей несколько, выберите путь, который состоит из максимального количества пересадок, чтобы Фаниль смог полюбоваться красотой каждой станции.
Входные данные. В первой строке заданы два целых числа n и m – количество станций и автобусов, которые могут быть полезны для поездки Фаниля. Во второй строке заданы два целых числа a и b: a – номер станции в Казани, b – номер станции в деревне у бабушки Фаниля (1<a, b <n). В следующих m строках заданы тройки целых положительных чисел ai, bi, pi, описывающие станции, которые соединены автобусным маршрутом, и длина пути между ними. Имейте в виду, что автобус едет только в одну сторону.
1<n<100
1<m<10 000
1<pi<109
Выходные данные. В первой строке выведите единственное целое число – длину кратчайшего пути из Казани (станция с номером a) до деревни бабушки Фаниля (станция с номером b). В следующей строке выведите путь –
номера станций по очереди через пробел, через которые едет Фаниль в порядке следования. Гарантируется, что такой путь существует. Если таких путей несколько, выведите путь, который содержит в себе максимальное число станций.
Пример.
| INPUT | OUTPUT |
| 5 6 1 5 1 2 2 1 3 3 2 4 3 3 4 1 4 5 5 1 5 9 | 9 1 3 4 5 |
Пояснение. Есть два кратчайших пути длины 9: это путь через 1 и 5 и путь через станции 1, 3, 4 и 5. Необходимо выдать второй из них, так как в нём больше станций.
Разбор. Для решения задачи используем алгоритм Дейкстры. Для каждой вершины храним количество вершин, из которых мы пришли в эту вершину. Пусть массив P[N] будет хранить количество таких вершин-родителей. Пусть массив Par[N] – массив родителей. Par[i] – номер вершины, из которой мы пришли в вершину i. Для вершины a P[a]=0. Когда мы производим релаксацию по рёбрам, увеличиваем P[e.to]=P[v]+1, где v – выбранная вершина с минимальным расстоянием, а e ребро, исходящее из вершины v, e.to – номер смежной v вершины.
При выборе минимальной вершины v, выбираем ту, у которой количество вершин-родителей больше:
for jЄV
if !used[j] and (v == null or d[j] < d[v] or d[j]==d[v] and P[j]>P[v])
v = j
for e: исходящие из v ребра
if d[v] + e.len < d[e.to]
d[e.to] = d[v] + e.len
P[e.to] = P[v] + 1
Par[e.to] = v
Длина пути будет сохранена в d[b]. Путь можно восстановить рекурсивно или итеративно с помощью массива Par.
Некоторые участники не учитывали, что цикл в графе не исключён. Классические алгоритмы dfs и bfs либо не проверяли все пути, либо зацикливались. Такие алгоритмы считаются неверными решениями.
Язмага реакция белдерегез
Вход на сайт
РЕКОМЕНДУЕМ
Комментарийлар