Заочная студенческая олимпиада по программированию
(18.02.2009 - 19.02.2009)

Факультет информатики ШГПИ информирует о проведении заочной студенческой олимпиады по программированию в рамках подготовки к студенческому форуму «Актуальные проблемы прикладной информатики и методики обучения информатике»

К участию к заочной студенческой олимпиаде по программированию приглашаются студенты любых вузов. Олимпиада проводится в телекоммуникационном режиме. Задания олимпиады будут опубликованы на сайте ШГПИ shgpi.edu.ru 18.02.2009 года в 14 ч. (12.00 Москвы). Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp_shgpi@list.ru) до 14 ч. 19.02.2009 г. Студенты ШГПИ и других вузов г. Шадринска могут представить решения на электронных носителях по адресу ул. К.Либкнехта 3, ауд. 220А.

Рекомендуемыми языками программирования являются Паскаль и Си (С++) (turbo pascal, free pascal, object pascal, turbo c, borland c++, gcc, visual c++). Комитет олимпиады не гарантирует рассмотрение решений на других языках программирования.

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

Файл с исходным текстом программы должен начинаться с головного комментария, содержащего следующую информацию: номер решаемой задачи, язык и версию языка программирования, фамилию, имя и отчество автора решения, курс, наименование вуза и факультета, город, а также контактные данные (e-mail, по желанию - телефон, почтовый адрес).

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

Итоги олимпиады будут подведены до 1 марта 2009г и опубликованы на сайте shgpi.edu.ru. Дополнительно, при участии в очной олимпиаде в рамках студенческого форума победители заочной олимпиады получают 10% бонус по очкам.

Для обсуждения формулировок задач, организационных вопросов, решений задач в форуме ШГПИ заведена специальная тема: Заочная олимпиада по программированию в ШГПИ

Задачи для заочной студенческой олимпиады по программированию

Вашему вниманию предлагается четыре задачи. При верном и качественном решении задач участник олимпиады может набрать максимум 16 баллов (1 -за первую, 4 – за вторую, 5 – за третью, 5+1 — за четвертую задачу).

Вопросы по условиям задач можно задавать с помощью электронной почты (olimp_shgpi@list.ru), в теме форума Заочная олимпиада по программированию в ШГПИ с помощью личных сообщений пользователям Vladislav_133 и xdsl.

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

Задача 1 (максимум — 1 балл)

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

Интерфейс командной строки является одним из известнейших и старейших способов взаимодействия человека и компьютера. Рассмотрим упрощенные правила формирования команд в интерфейсе:

1. Команда состоит только из набора латинских букв

2. Команда может иметь параметры и опции

3. Параметры и опции отделяются друг от друга и от команды произвольным кол-вом пробелов, порядок следования опций и параметров — произволен.

4. Параметры могут содержать латинские буквы и пробелы. Если параметр содержит пробелы, он должен обрамляться кавычками

5. Опции могут содержать латинские буквы и начинаются со знаков "-" или "/".

Создать программу, которая получает на входе (файл input.txt или стандартный входной поток) строку, содержающую команду (возможно — с параметрами и опциями). Проанализировав команду, программа должна возвратить (файл output.txt или стандартный выходной поток) слово «Error», если строка не соответствует стандарту формирования команд. В противном случае программа должна возвратить количество параметров и опций команды (два числа через пробел)

Задачи 2 и 3.

Автор: Пирогов В.Ю.

О правилах оценки задач 2 и 3

При проверке решений задач 2-3 будет проводиться анализ текста программы с целью выявления нарушений требований к решению задач. Кроме того, мы хотим выявить решения, имеющие незначительные погрешности. За такие решения будут начислены баллы.

О формате чисел с плавающей точкой.

Формат чисел с плавающей точкой используется для хранения больших вещественных чисел в памяти компьютера. Числа в таком формате называют также числами в нормализованном виде. Далее мы рассматриваем формат, основанный на 64-битовом представлении. Другими словами на каждое вещественное число в таком формате отводится ровно 64-бита. В языках программирования такой тип обычно называют double. Заметим, что этот формат поддерживается также на уровне процессора Intel.

В общем случае нормализованный вид числа выглядит так

Здесь ZN – знак числа, M – мантисса числа, обычно удовлетворяет условию <1 (для нормализации мантиссу представляют в виде 1,s, где s - дробная часть, а затем отбрасывают 1, т.е. ‘s’ и есть мантисса, см. далее примеры), N – основание системы счисления, q – показатель, в общем случае может быть и положительным и отрицательным числом. Мы, естественно, будем далее рассматривать двоичное представление чисел с плавающей точкой, так как это происходит при использовании чисел с плавающей точкой в языках программирования.

Для хранения переменной типа double отводится 64 бита. Биты 0-51 отводятся для хранения мантиссы. Биты 52-62 предназначены для хранения числа q, сложенного с числом 1023 (чтобы не хранить знак показателя). Последний 63-й бит определяет знак числа (1 – знак отрицательный, 0 - положительный). Ниже, на рисунке мы схематически представили формат числа.

Примеры

Рассмотрим несколько примеров.

1. Число с фиксированной точкой 123.75. Преобразуем его к типу double.

Целая часть 123 - 1111011, дробная часть 75 – 11 (1/2+1/4=0.75).

Мантисса должна иметь вид 1,11101111, но для этого ее следует умножить на 2 в степени 6. Т.е. показатель 6 и его надо сложить с 1023. Получим 1029 = 10000000101. Отбрасывая первую единицу у мантиссы, получим в результате следующее представление числа 123.75 в формате double.

0100000001011110111100000000000000000000000000000000000000000000

Или

01000000010111101111000000000000 00000000000000000000000000000000

Т.е.

405EF000 0

2. Рассмотрим число -0.5.

Целая часть = 0, дробная часть представляется единицей 1 в двоичной системе (1/2). Составим мантиссу:

1.0, ее следует также умножить на 2 в степени -1, т.е. показатель -1 и его следует сложить с 1023 и получаем 1022 = 1111111110. В результате получаем (не забыв отбросить 1 у мантиссы).

1 01111111110 0000000000000000000000000000000000000000000000000000 (бит 63=1, т.е. отрицательный знак).

Или

10111111111000000000000000000000 00000000000000000000000000000000

BFE00000 0

3. Рассмотрим теперь обратный пример.

4076ab33 33333000

Преобразуем число double к формату с фиксированной точкой. В двоичном формате получим.

01000000011101101010101100110011 00110011001100110011000000000000

Сразу очевидно, что знак числа ‘+’ (бит 63 = 0).

Показатель 10000000111 = 1031. 1031-1023=8.

Мантисса

0110101010110011001100110011001100110011000000000000

Дополняем единицей и сдвигаем вправо на 8 разрядов

101101010.10110011001100110011001100110011000000000000

101101010 = 362 – целая часть.

Подсчитаем теперь дробную часть.

10110011001100110011001100110011000000000000 =

1/2 + 1/8 +1/16 + 1/128 + 1/256 +… = 0,69703125

Действия можно производить и далее (программа, естественно даст более точный результат). Изначально речь шла о числе 362.7, но поскольку дробная часть не может быть точно представлена двоичной дробью – результат будет приближенным (362.699999993), что для конкретных расчетов не имеет большого значения. Кроме того, если, скажем, округлить этот результат, то мы получим точное значение.

Задача 2 (максимум - 4 балла).

Автор: Пирогов В.Ю.

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

405ee3d7 a3d400

(для числа 123.56).

Требования к программе.

1. Нельзя использовать какие-либо библиотечные функции преобразования: из строки в число, из числа в строку, из одного числового формата в другой.

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

3. Целая часть вводимого числа и его дробная часть (если ее рассматривать как целое число, например для 123.56 это просто 56) не должны выходить за рамки 32-битного числа. При нарушении этого правила должна генерироваться ошибка.

4. Число вида 456 (без дробной части) следует считать 456.0, можно также использовать форму 456. . Число вида .789 (без целой части) следует рассматривать как 0.789 .

5. При нарушении входного формата также должна генерироваться ошибка. В представлении числа должны отсутствовать: лишняя точка, посторонние символы, пробелы. Например, ошибкой будет "123 .5" "567.4," и т.д.

6. Число может иметь знак (+ или -). За знаком числа сразу же должны идти цифры.

7. При переводе десятичной дроби в двоичную также должно соблюдаться условие: результат должен быть помещен в 32-битовое число (число, представляющее двоичную дробь). В результате перевода может быть потеряна точность, что чаще всего и бывает, так как в большинстве случаев точно перевести десятичную дробь в двоичную нельзя

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

Задача 3 (максимум — 5 баллов)

Автор: Пирогов В.Ю.

Написать программу, которая на входе получает строку, содержащую число в формате с плавающей точкой в виде двух 16-ричных четырехбайтовых чисел. Например:

405ee3d7 a3d400

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

Требования к программе.

1. Нельзя использовать какие-либо библиотечные функции преобразования: из строки в число, из числа в строку, из одного числового формата в другой.

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

3. Два входных 16-ричных четырехбайтовых числа могут быть разделены произвольных количеством пробелов. В начале строки также могут идти пробелы.

4. Если в мантиссе количество битов дробной части больше 32, то лишние биты должны отбрасываться без округления (!).

Задача 4 (максимум — 5 баллов + 1 балл за крэш-тесты)

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

6
1  -  -  0  50
2  -  -  5  40
3  1  2  25 60
5  1  2  23 70
7  1  2  20 55
8  -  -  20 80
9  5  8  40 90
10 5  8  43 80
4  -  8  35 90
11 -  -  30 100
6  11 4  53 95

4 8 9 10 11

8
1  -  -  0  50
2  -  -  5  40
3  1  2  25 60
5  1  2  23 70
7  1  2  20 55
8  -  -  20 80
9  5  8  40 90
10 5  8  43 80
12 -  -  10 40
4  -  8  35 90
11 -  -  30 100
6  11 4  53 95

4 6 9 10