Методические рекомендации по проведению олимпиады по программированию УГС 09.00.00
олимпиадные задания

ОГБПОУ СОТА

Методические рекомендации

по проведению олимпиады по программированию

УГС  09.00.00

Преподаватель:

Кашталинская И.А.

Смоленск

2019 г.

Содержание

Введение    3

Условия проведения  олимпиады по программированию   4

Литература    5

Приложение А  Задания для проведения олимпиады по программированию    6

Приложение Б   Вариант заданий для проведения олимпиады    10

Введение

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

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

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

Для подготовки к олимпиадам по программированию можно использовать  «интернет-источники»:

1. Разбор олимпиадных задач по программированию http://g6prog.narod.ru/books.html 
2. Олимпиадные задачи по программированию, информатике и ИКТ http://olimp-zadachi.narod.ru/ 
3. Олимпиадные задачи по программированию http://school-collection.edu.ru/catalog/rubr/7d5f9dcd-3c0e-c52c-0181-ed064bbfa22d/86787/ 
4. Школа программиста http://acmp.ru/ 

1  Условия проведения олимпиады по программированию

Олимпиада по программированию проводится в рамках Недели специальности УГС 09.00.00

Цели и задачи олимпиады:

1. Выявление  уровня качества подготовки специалистов в области  современных информационных технологий.
2. Развитие творческих способностей студентов.
3. Воспитание здорового духа конкурентной борьбы, стремления к победе.
4. Выявление одаренных и талантливых студентов, их дальнейшее интеллектуальное развитие.
5. Проверка профессиональной готовности будущего специалиста к самостоятельной трудовой деятельности.

Требования к заданиям

 Задания для проведения олимпиады приведены в приложениях А, Б, содержат практическую часть, включающую 5 заданий, выполнение которых требует наличия у участника знаний и умений по ряду дисциплин. На выполнение практической части отводится до 120 минут. Практические задания предполагает наличие знаний и умений по дисциплинам:

• основы информационной безопасности;
• основы алгоритмизации и программирования;
• операционные системы и среды;
• компьютерные сети;

В ходе выполнения заданий:

• каждому участнику предоставляются рабочее место, оснащенное компьютером на базе процессоров Intel Се1erоn или  Intel Pentium-4, с частотой 900 МГц и более, стандартной клавиатурой US/РУС, мышью и цветным SVGA монитором;

- на компьютерах будет установлено программное обеспечение не ниже:

• операционная система Windows XP

• Воr1аnd Раsсаl 7.0;
• Delphi 7.0,
• пакет  MS – Office 2010.

 -   указанные системы, будут полностью инсталлированы на каждом компьютере, включая встроенные системы помощи. Запрещается использовать какие-либо другие компиляторы и библиотеки.

Подведение итогов.

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

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

 -  эффективность разработанных участником алгоритмов;

• правильность выполнения каждого задания;
• соблюдение лимита времени.

Литература

1. Аркадьев А.Г., Днепров Э.Д. Сборник нормативных документов. Информатика и ИКТ. М. : Дрофа, 2010.
2. Задачи по программированию. Окулов С. М. [и др.]. М. : БИНОМ. Лаборатория знаний, 2016.
3. Методика преподавания информатики: Учебное пособие для студентов педагогических вузов. Лапчик М.П. [и др.]. М. : Издательский центр «Академия», 2014.

Приложение А

Задания для проведения олимпиады по программированию

Задача А (40 баллов). Подстановочный шифр

Даны две строки одинаковой длины, состоящие из заглавных латинских букв. Требуется найти подстановочный шифр, при помощи которого первая строка шифруется во вторую, или определить, что такого не существует. Например, для слов «GOOD» и «WELL» шифра не существует, потому что, с одной стороны буква «О» преобразуется одновременно в «E» и «L», а с другой стороны, буквы «О» и «D» обе превращаются в «L».

Формат входного и выходного файлов

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

В случае если шифра не существует, следует вывести в выходной файл строку «--» (два знака минус).

Примечание: Шифрование строки подстановочным шифром производится путём замены каждого символа алфавита на другой символ. Для однозначного шифрования и дешифрования необходимо, чтобы каждому символу исходного алфавита соответствовал ровно один символ зашифрованного, и наоборот. Например, при помощи шифра М → А, А → R, Y → К слово МАYА будет зашифровано в АRKR.

Решение. Рассмотрим обе строки, задающие исходный и зашифрованный тексты, и составим пары букв (α,β), задающие шифр – отображение α→β. Если для какой-либо буквы имеется два отображения α→β и α→γ, значит, шифр задан неверно. Основная ошибка заключается в том, что при решении сохраняется только прямое отображение. В этом случае не обнаруживаются ошибки в шифре вида α1→β и α2→β.

Для хранения пар (α,β) прямого и обратного отображений удобно использовать структуру типа array[‘A’..’Z’] of char.

Задача В (50 баллов). Длинный отрезок

На плоскости задан многоугольник с целочисленными координатами вершин и сторонами, параллельными осям координат. Требуется найти самый длинный горизонтальный или вертикальный отрезок, лежащий внутри многоугольника. (Многоугольник включает свою границу).

Формат входного и выходного файлов

В первой строке входного файла содержится число вершин N (4 ≤ N ≤ 50). В следующих строках расположены целочисленные координаты вершин хi, уi (1 ≤ хi, уi  ≤ 1000), перечисленные в порядке обхода. (При этом у каждой пары соседних вершин либо координаты х, либо координаты y совпадают).

Выходной файл должен содержать единственное целое число — длину самого длинного отрезка.

Решение. Задача В требует перебора всех возможных отрезков, лежащих внутри многоугольника, и выбора самого длинного из них. Наиболее длинным будет отрезок, не лежащий строго внутри многоугольника, а проходящий по одной (или нескольким) из его сторон. Это значительно снижает количество возможных вариантов при переборе. При решении достаточно провести все горизонтальные и вертикальные прямые, содержащие стороны многоугольника (таких прямых не более N) и найти точки их пересечения со сторонами многоугольника.

Задача С (30 баллов) Миллион «Z»

Дана строка, состоящая из одного миллиона букв «Z». Определим операцию замены, которая характеризуется тремя параметрами (α, i, j) и состоит в замене на букву α букв строки начиная с позиции i до позиции j. Требуется определить, сколько различных букв будет в строке после выполнения заданной последовательности операций замены.

Формат входного и выходного файлов

В первой строке входного файла содержится число замен N (0 ≤ N ≤ 1000). В следующих N строках содержатся тройки α i j, где α — заглавная латинская буква, i и j — целые числа (1 ≤ i ≤ i j ≤ 106).

Выходной файл должен содержать единственное целое число — количество различных букв в результирующей строке.

Решение. Нужно представить исходную строку из букв ‘Z’ в виде отрезка с началом в точке 0 и концом в точке 1000000. Тогда операция замены символов α i j может быть реализована как операция деления исходного отрезка на части. При проведении N замен у нас получится максимум 2N+1 частей, каждая из которых определяется координатами своих концов и символом α. После проведения всех замен остается подсчитать количество отрезков, на которые был разделен исходный отрезок. При создании программы надо аккуратно реализовать различные ситуации, возникающие при наложении отрезков друг на друга.

Задача D. Семикратные подчисла

В данной строке, состоящей из цифр от 0 до 9 найти подстроку, представляющую запись числа, неравного нулю и кратного семи.

Например, в строке 560005672 есть подходящие подстроки— 7, 56, 560, 672 и т.д.

Формат входного и выходного файлов

Во входном файле содержится строка длиной от 1 до 1000. Выходной файл должен содержать число 1, если хотя бы одна такая подстрока найдена, и число 0 в противном случае.

Решение. Для решения данной задачи необходимо перебирать подстроки данной строки до тех пор, пока не будет найдена строка, задающая делящееся на 7 число, или пока не будут перебраны все подстроки. При таком переборе следует исключать из рассмотрения подстроки, начинающиеся с символа ‘0’ (ноль).

Проверка делимости числа на 7 может быть проведена по-разному. Можно просто реализовать деление длинных чисел, но это потребует неоправданных затрат времени и памяти. Есть более простой вариант, использующий особенности записи числа в десятичной системе счисления. Если имеется число M=(α1α2α3…αN) и известно, что остаток деления M на 7 равен r (r=M mod 7), то, очевидно, остаток от деления числа M’=(α1α2α3…αNβ) на 7 равен r’=(10r+β) mod 7.

Задача Е (10 баллов). Новогодний пузырь

Новогодняя вечеринка проходит в плоском прямоугольном зале с координатами левого нижнего угла (0, 0), а правого верхнего — (1000, 1000). С потолка зала свешивается мишура в виде N прямых тонких вертикальных лент с координатами нижних концов (хi  уi).

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

Формат входного и выходного файлов

В первой строке входного файла содержатся числа N R х (0 ≤ М ≤ 100, 0 < R ≤ 50, R < х < 1000-R), в следующих N строках содержатся вещественные числа хi  уi (0 < хi < 1000, 100 < уi < 1000). Числа в строке разделены пробелами. Значения всех хi  во входном файле различны.

В выходном файле должно содержаться единственное число — номер ленты (во входном файле) либо 0 (нуль), если пузырь долетел до потолка. Если пузырь одновременно столкнулся с несколькими лентами (и, возможно, потолком), вывести номер самой левой ленты.

Решение. Для того чтобы успешно решить задачу  достаточно знать уравнение окружности (x- хi)2+(y- yi)2=R2. При решении выделяем ленты, попадающие в полосу с координатами от х-R до х+R, и находим ординату y окружности радиуса R, проходящей через точку (хi  уi). Можно не выделять заранее ленты из полосы, по которой пройдет пузырь, а рассмотреть все имеющиеся ленты. В случае если лента находится далеко от пузыря, при вычислении y мы получим под знаком квадратного корня отрицательное число. Это будет служить сигналом о том, что с данной лентой пузырь не столкнется никогда.

Задача F (20 баллов). Маршрутка

Маршрутное такси на Р посадочных мест движется по линии с N остановками, пронумерованными от 1 до N в порядке следования такси. На остановках стоят очереди из пассажиров, каждый из которых желает попасть на некоторую остановку, расположенную дальше по маршруту. Водитель забирает на первой остановке f пассажиров и отправляется в путь. На каждой следующей остановке выходят все пассажиры, желавшие на неё попасть. Затем пассажиры садятся в порядке очереди до тех пор, пока не заполнится такси или не закончится очередь.

Каждый пассажир платит водителю 5 рублей.

Требуется определить при каком значении f (возможно, нулевом), доход водителя будет наибольшим и вывести этот доход.

Формат входного и выходного файлов

В первой строке входного файла содержатся числа N и Р (2 ≤ N ≤ 50, 1 ≤ Р ≤ 20). В следующих N-1 строках находятся чиста Кi di,1 … di,Ki (0 ≤ Кi ≤ Р, i ≤ di,j ≤ N) — количество пассажиров на очередной остановке и цель каждого пассажира. (На конечной остановке пассажиры не садятся).

Выходной файл должен содержать единственное целое число— максимальный доход водителя в рублях.

Решение. Задача относится к числу тех задач, алгоритм решения которых написан в самом условии задачи. Для ее решения достаточно провести аккуратное моделирование описанной в условии ситуации.

Приложение Б

Вариант заданий для проведения олимпиады

Задача 1 (50 баллов)

Имя входного файла:             percent.in

Имя выходного файла:          percent.out

Ограничения по времени:     1 секунда

Ограничения памяти:        64 Мб

Параллель 11-х классов писала контрольную работу. В результате ровно А% учащихся получили 5, ровно В% учащихся получили 4, ровно С% - 3, а остальные Д% написали ее на 2.

Какое минимальное количество школьников должно быть в параллели восьмых классов для того, чтобы могли получить такие результаты?

Формат входных данных

Вводятся 4 целых числа от 0 до 100 – А, В, С, Д (А+В+С+Д =1)

Формат выходных данных

Выведите единственное целое положительное число – минимальное возможное количество учащихся в параллели.

Пример

Задача 2 (40 баллов)

Имя входного файла:             input.txt

Имя выходного файла:          output.txt

Задан набор слов (слово – последовательность символов, не содержащая пробелов). Первая буква может быть как заглавной, так и строчной, остальные – строчные.

 Пусть в двух произвольных словах этого набора встречается несколько одинаковых букв (регистр букв учитывается).

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

Распределить слова по парам, так чтобы сумма всех процентов совпадений была наибольшей.

Формат входных данных

В первой строке входного файла задано количество слов N.

2<=N<=12 (всегда четное).

В следующих N строках заданы сами слова.

cлово1

…

cлово N

Длина каждого слова не превышает 20 символов.

Формат выходных данных

слово слово процент_совпадения

. . .

слово слово процент_совпадения

где:

в каждой паре слова стоят в алфавитном порядке;

пары отсортированы в алфавитном порядке по первым словам в них.

Пример

Задача 3 (10 баллов)

Мощность алфавита равна 256. Сколько кбайт памяти потребуется для сохранения 480 страниц текста, содержащего в среднем 128 символов на каждой странице.

Задача 4 (20 баллов)

В зрительном зале две прямоугольные области кресел для зрителей: одна 10х5, другая 4х8. Какое минимальное количество бит потребуется для кодирования каждого места в автоматизированной системе?

Задача 5 (30 баллов)

Написать программу, определяющую поля шахматной доски, находящиеся под боем коня.