Заочная
студенческая олимпиада по программированию
(21.02.2008 -
22.02.2008)
Факультет информатики ШГПИ информирует о проведении заочной студенческой олимпиады по программированию в рамках подготовки к студенческому форуму «Актуальные проблемы прикладной информатики и методики обучения информатике»
К участию к заочной студенческой олимпиаде по программированию приглашаются студенты любых вузов. Олимпиада проводится в телекоммуникационном режиме. Задания олимпиады будут опубликованы на сайте ШГПИ www.shgpi.edu.ru 21.02.2008 года в 14 ч. (12.00 Москвы). Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp_shgpi@list.ru) до 14 ч. 22.02.2008 г.
Рекомендуемыми языками программирования являются Паскаль и Си (С++) (turbo pascal, free pascal, object pascal, turbo c, borland c++, gcc, visual c++). Комитет олимпиады не гарантирует рассмотрение решений на других языках программирования.
Все решения задач должны быть консольными, самодостаточными приложениями, т.е. для своего запуска - не требовать подключения внешних библиотек, а для компиляции - не требовать подключения дополнительных модулей, не входящих в стандартную поставку языка или среды программирования. GUI-решения не рассматриваются и не оцениваются.
Файл с исходным текстом программы должен начинаться с головного комментария, содержащего следующую информацию: номер решаемой задачи, фамилию, имя и отчество автора решения, курс, наименование вуза и факультета, город, а также контактные данные (e-mail, по желанию - телефон, почтовый адрес).
Вступительный взнос и заявка для участия в заочной олимпиаде не требуются.
Итоги олимпиады будут подведены до 1 марта 2008г и опубликованы на сайте www.shgpi.edu.ru. Дополнительно, при участии в очной олимпиаде в рамках студенческого форума победители заочной олимпиады получают 10% бонус по очкам.
Задачи для заочной студенческой олимпиады по программированию
Вашему вниманию предлагается три задачи. При верном и качественном решении задач участник олимпиады может набрать максимум 30 баллов (6+3 -за первую задачу, 8 – за вторую, 12+1 – за третью задачу).
Попробовать свои силы приглашаются и школьники. В головном комментарии вместо курса, наименование вуза и факультета школьники должны указать класс и номер школы.
Вопросы по условиям задач можно задавать с помощью электронной почты (olimp_shgpi@list.ru), в форуме http://forum.shadrinsk.net с помощью личных сообщений пользователям Vladislav_133 (задача 2) и xdsl (задачи 1, 3, оргвопросы).
При верных решениях дополнительные баллы получают варианты, успешно проходящие крэш-тесты. Под крэш-тестами понимаются исходные данные очень большого объема или чрезвычайно сложной структуры. Верная обработка таких данных за приемлимое время характеризует качество программы и заслуживает, по нашему мнению, дополнительных баллов.
Участники олимпиады могут выполнить проверку корректности обработки исходных данных с помощью программной системы Solver. Данная система не является основным или обязательным инструментом для проверки решений участников олимпиады, однако ее применение может ускорить решение задач. При обнаружении ошибок в программной системе Solver просим сообщать об этом по адресу olimp_shgpi@list.ru.
Задача 1. Менеджер памяти
(6 баллов, прохождение крэш-тестов - дополнительно 3 балла)
Автор: Слинкин Д.А.
Современные языки и системы программирования обеспечивают корректную работу программы с динамическими переменными с помощью так называемых «менеджеров памяти». Задачей такого менеджера является корректное выделение и освобождение оперативной памяти для переменных, реакция на нехватку памяти, предоставление программисту информации о доступном объеме памяти, объеме памяти, занятом переменными и т.д. В некоторых языках программирования менеджер памяти обеспечивает периодическую «сборку мусора» или «дефрагментацию» памяти. Фрагментация памяти возникает в ситуациях, когда динамические переменные уничтожают не в том (и не в обратном) порядке, в котором они создавались, а в произвольном порядке:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Рис.1. Участок
оперативной памяти до создания динамических переменных
(в
ячейках показаны адреса)
|
|
|
|
|
|
|
|
|
|
|
Рис.2. Участок
оперативной памяти после последовательного создания четырех
переменных
red, green, blue и black
|
|
|
|
|
|
|
|
|
|
|
Рис.3. Участок
оперативной памяти после удаления двух переменных
red и blue
|
|
|
|
|
|
|
|
|
|
|
Рис.4. Участок
оперативной памяти после создания двух переменных
gray и yellow
На рисунке 3 изображен фрагментированный участок памяти. Несмотря на то, что формально доступно четыре ячейки памяти, не удастся разместить на данном участке переменную размером в 3 или 4 ячейки. Результат работы менеджера памяти по созданию еще двух переменных (gray и yellow) показан на рисунке 4. При попытке выделения памяти для новой переменной менеджер (в простейшем случае) ищет первый участок памяти, подходящий для переменной по размерам, после чего размещает ее там.
Задача: создать программу, эмулирующую работу простейшего менеджера оперативной памяти.
Исходный файл (input.txt).
Первая строка — объем доступной оперативной памяти (от 0 до (232)/2 ячеек)
Вторая и последующие строки — команды по созданию и удалению динамических переменных. Команда по созданию переменных состоит из трех параметров, разделенных произвольным количеством пробелов и табуляций. Первый параметр — ключевое слово create, второй — имя переменной (любой набор символов произвольной длины), третий — объем памяти для переменной. Команда по удалению переменных состоит из двух параметров, разделенных произвольным количеством пробелов и табуляций. Первый параметр — ключевое слово destroy, второй — имя переменной (любой набор символов произвольной длины).
Пример на основе рис. 1-4:
10
create red 2
create green 3
create blue 2
create black 3
destroy red
destroy blue
create gray 1
create yellow 2
Результирующий файл (output.txt).
В каждой строке результирующего файла содержится информация о переменной, расположенной в оперативной памяти, а именно — адрес расположения в оперативной памяти, имя переменной и ее размер. Переменные перечисляются по порядку расположения их в оперативной памяти.
Пример на основе рис. 1-4:
0: gray (1)
2: green (3)
5: yellow (2)
7: black (3)
Предусмотреть реакцию программы на следующие ошибки:
Нехватка оперативной памяти для конкретной переменной
Неверный синтаксис команды (нехватка параметров, неверный тип параметров)
Удаление отсутствующей переменной.
Неизвестная команда
Задача 2. Интерпретатор для обработки
арифметических выражений
без скобок (4 балла), и со скобками (8
баллов).
Автор: Пирогов В.Ю.
Внимание! Задачи 2.1 и 2.2 являются взаимоисключающими. Таким образом за решение задачи 2 можно получить максимум 8 баллов.
Задача 2.1: разработать программу-интерпретатор арифметического выражения без скобок (4 балла).
На входе такого интерпретатора строки с арифметическими выражениями, на выходе – результаты вычислений арифметических выражений или сообщение об ошибке, если структура выражения не соответствует правилу составления таких выражений.
Алфавит:
Цифры, точка, знаки арифметических операций, пробел.
Арифметическое выражение состоит из:
- Чисел, целых (345, 8000) или вещественных с плавающей точкой (1.34578, 5489032.00234).
- Знаков арифметических операций (+,-,*,/).
- Между числами и знаками арифметических операций могут располагаться произвольное количество пробелов.
- Длина арифметического выражения не ограничивается.
Например, правильными арифметическими выражениями считаются выражения
123
1.345/23+456-678*0.345
2+34-456*67*0.567-1
Ошибки и допустимые выражения:
Состоящее из пробелов выражение считается ошибкой. Строка, в которой отсутствуют, какие либо символы игнорируется.
Выражение может состоять из одного числа.
Появление в выражении символов, не входящих в алфавит (см. Алфавит) считается ошибкой. Например, 1+234*a/34.56.
Не правильный формат числа: пробелы между цифрами, лишняя точка считается ошибкой. Формат вида .456 (отсутствие разрядов перед точкой) допускается: .456 равносильно 0.456. Также допускается формат числа, в котором вначале идет произвольное количество нулей. Например, 00000345.01 эквивалентно 345.01 .
Ошибкой является следование подряд нескольких знаков арифметических операций. Например, 2++4. Ошибочными также считаются арифметические выражения, начинающиеся и заканчивающиеся символами арифметических операций: +2*34 или 12-.
Деление на 0 должно рассматриваться программой как ошибка.
Программа не различает виды ошибок, т.е. диагностики ошибок не требуется.
При вычислении допустимы округления в рамках операций с числами типа double.
Правила выполнения операций.
Интерпретатор просматривает строку, например, слева направо и выполняет арифметические действие сообразно их приоритетам.
Действия сложения и вычитания имеют более низкий приоритет по отношению к действиям умножения и деления. Например, в результате интерпретации выражения:23+4/2/2+1 должно получиться число 25.
Входные и выходные файлы.
На входе интерпретатор получает текстовый файл (input.txt), где в каждой строке стоят арифметические выражения, на выходе мы получаем текстовый файл output.txt, где в каждой строке стоят результаты вычислений арифметических выражений.
Пример input.txt:
1+3*4*5
q+45
1.2345*4*4+4-56/5*4
123/4/5/0
123+45
123+4*4*4+1
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
Пример output.txt:
61.000000
Error!
-21.048000
Error!
168.000000
188.000000
16.000000
Задача 2.2: разработать программу-интерпретатор арифметического выражения со скобками (8 баллов).
Алфавит, по сравнению с предыдущей задачей, дополняется открывающими ’(’ и закрывающими ‘)’ скобками. Будем считать, что все, что сказано в предыдущей задаче, справедливо и в данной задаче для выражений, стоящих в скобках.
Использование скобок позволяет определить дополнительные приоритеты вычислений. Например, интерпретация выражения: (23+1)/(2+2) должна дать результат 6, так как деление выполняется уже после того, как вычислены выражения в скобках.
Дополнительные ошибки, связанные со скобками:
Ошибка генерируется если количество открывающих скобок не равно количеству закрывающих скобок. В выражении могут отсутствовать скобки. Количество скобок в выражении не ограничено. Допускаются лишние скобки, выражение вида ((((1)+(1)))) допустимо, хотя и содержит лишние скобки.
Выражение, начинающееся с закрывающей скобки или заканчивающееся открывающей скобкой, также считается ошибочным.
Пример input.txt:
(234.567)/(1+2+3+4)
1/2/3/4/5/6+1
((10001+1/5+(45+23.1)))*1.222
((((((1))+(1)))))
(234+34-456.22)-(33*44+2)
((222+2)-(222+2)
((1*2*3*4*5*6*7-100))/100*2
Пример output.txt:
23.456700
1.001389
12304.684600
2.000000
-1642.220000
Error!
98.800000
Задача 3. Точки доступа
(12 баллов, прохождение крэш-тестов – дополнительно 1 балл)
Автор: Слинкин Д.А.
точек доступа
Автомобиль, напичканый аппаратурой для взлома беспроводных сетей, неспешно движется по автомагистрали. Вдоль магистрали расположено множество офисов компаний, не уделяющих особого внимания информационной безопасности и как следствие — активно использующие wi-fi-технологии для подключения компьютеров и мобильных устройств в локальную сеть компании. Используемые wi-fi устройства (точки доступа) обеспечивают радиоохват не только офисов компании, но и всей прилегающей территории, включая автомагистраль.
Задача: найти один (любой) из участков автомагистрали, на протяжении которого можно получить доступ к максимальному количеству беспроводных сетей.
Исходный файл (input.txt).
Первая строка — координаты начала и конца отрезка автомагистрали, по которой движется автомобиль. Будем считать, что начальная и конечная точки движения не находятся в зоне покрытия ни одной wi-fi-сети. В каждой последующей строке хранятся данные, разделенные пробелами, об отдельной точке доступа: название (уникальный набор произвольных символов), координаты центра и радиус покрытия.
Пример файла input.txt:
2.5 26.5 14 1
A 5.5 17 4
B 12.5 18 6
C 6.5 9.5 6
D 13.5 10.5 5
Результирующий файл (output.txt).
Первая строка –
список имен искомых точек доступа
Вторая строка – координаты искомого отрезка автомагистрали
Если пересечение
автомагистрали с зонами радиохвата отсутствует, вывести сообщение об этом
Если происходит только
касание автомагистрали и зоны радиохвата, то координаты начала и
конца отрезка должны совпадать.
Пример файла output.txt:
A B C
(7.499, 15.417)-(8.14, 13.995)
Примечания:
Порядок перечисления точек доступа и координат отрезка значения не имеет. Т.е. результат, приведенный в примере, может выглядеть и так:
B A C (8.14, 13.995) - (7.499, 15.417)
Точность вычислений - не менее одной тысячной.
