Заочная студенческая олимпиада по программированию
(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)

Предусмотреть реакцию программы на следующие ошибки:

  1. Нехватка оперативной памяти для конкретной переменной

  2. Неверный синтаксис команды (нехватка параметров, неверный тип параметров)

  3. Удаление отсутствующей переменной.

  4. Неизвестная команда


Задача 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 балл)

Автор: Слинкин Д.А.


Рис. 5: Пример расположения
точек доступа


Автомобиль, напичканый аппаратурой для взлома беспроводных сетей, неспешно движется по автомагистрали. Вдоль магистрали расположено множество офисов компаний, не уделяющих особого внимания информационной безопасности и как следствие — активно использующие 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)

Примечания:

  1. Порядок перечисления точек доступа и координат отрезка значения не имеет. Т.е. результат, приведенный в примере, может выглядеть и так:

    	B A C
    	(8.14, 13.995) - (7.499, 15.417)
    
    
  2. Точность вычислений - не менее одной тысячной.

  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
  • partner
Наверх