Заочная олимпиада по программированию в ШГПИ - 2009 год

[xdsl]

Внимание! Окончательно зафиксирована дата проведения заочной олимпиады: с 18 по 19 февраля 2009 года

13 февраля 2009 года (в пятницу ) в рамках подготовки к традиционному весеннему студенческому форуму (http://shgpi.edu.ru/f11/info/conf_olimp_2009/stud_konf.html) факультет информатики проводит заочную студенческую олимпиаду по программированию. Обратите внимание на перенос даты проведения олимпиады (с 5 февраля на 13 февраля)!

Ознакомиться с правилами, задачами и результатами проведения олимпиад прошлых лет можно здесь:http://shgpi.edu.ru/f11/info/conf_olimp_2008/objavl_zao_olimp_2008.html

Вспомогательным механизмом для проверки собственных решений может служить программа Solver (http://shgpi.edu.ru/scripts/tasks/).

По стародавнему обычаю в оргкомитет олимпиады входят два человека: Пирогов Владислав Юрьевич (к.п.н, профессор, зав. кафедрой Прикладной Информатики, ник в форуме - Vladislav_133) и Слинкин Дмитрий Анатольевич (к.п.н, доцент, преподаватель программирования кафедры Программирования и Сетевых Технологий, зав. Вычислительным Центром ШГПИ, ник в форуме - xdsl). Уфф, даже устал писать ... . По столь-же стародавнему обычаю оргкомитет олимпиады самостоятельно придумывает и прорешивает олимпиадные задачи. Любые совпадения условий задач нашей олимпиады с олимпиадными задачами всероссийских и международных олимпиад чаще всего случайны. Изредка сторонние олимпиадные задачи берутся за основу при создании наших задач.

На текущий момент нерешенными остаются 2 вопроса:
1. Проводить заочную олимпиаду в один день (с пятницы на субботу) или в три дня (с пятницы на понедельник)?
2. Количество задач. Минимум будет 3 (уже придуманы и прорешаны), максимум - ???. Решение этого вопроса во многом зависит от решения первого.

[Kido.fm]

1. Предлагаю проводить олимпиаду на неделе, а именно, со среды на четверг. Так как примерно в эти дни мозг проявляет свою большую активность. В конце учебной/рабочей недели хочется прежде всего отдохнуть, нежели решать олимпиадные задания. К тому же, в пятницу многие студенты разъезжаются по месту жительства, а в числе этих студентов могут быть те, кто хотел бы участвовать в олимпиаде.
2. Четыре задачи будет самое то. Больше возможностей для решения. Большинство студентов глянет на первые три задачи, подумают что сложно, и не станут решать. А с четырьмя задачами мы имеем шансы на то, что студент зацепится таки за одну из четырех задач. А после ее решения может и дальше пойдет... По той же схеме пять задач будет уже слишком много. Все таки на решение-то всего сутки. И элемент случайности тут возрастет гораздо выше, чем при четырех задачах. Соответственно, два человека, решившие разные задачи не будут объективно оценены, так как времени на адекватную оценку и реальную попытку решения всех задач нет ни у того ни другого(человека решившего больше всех задач не считаем, так как он по умолчанию займет первое место).

[6puCCeH]

Если я ничего не путаю - 13 февраля на факультете информатики будет Экватор. Ну и 14 февраля день святого Валентина. Несколько мероприятий в один день...возможно кому-то придется делать выбор.

[xdsl]

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

Можно предложить 18-19 февраля (среда-четверг). Сдвинуть назад (на 11-12 февраля) не выйдет, т.к. рассыл информационного письма по вузам уже сделан. Возражения-предложения-варианты?

[Vladislav_133]

Я в основном согласен:

1. Делать надо в середине недели, это наибольшая активность.
2. Четыре задачи - наверное. Но здесь надо подумать. Есть два подхода - либо взять количеством либо качеством. Например 10 достоточно простых задач, но их ведь надо решить, или одна сложная алгоритмически задача. Пока наша заочная олимпиада делала уклон в сторону сложных задач.

Есть еще один вопрос, который следовало бы обсудить. Сколько времени дается на решение. Есть мнение, что можно дать и более суток. Это тоже спорный вопрос. Мне так, например, требуется несколько суток, поскольку я все тщательно продумываю, при том часто решение приходит утром, а не вечером. Но я и не участник олимпиады и задачами, которые я придумываю, я занимаюсь иногда по неделе - полторы.

[xdsl]

Думаю, ждем еще день, и, если других предложений-возражений не будет, останавливаемся на 18-19 февраля. Задач будет четыре, две - В.Ю., две - мои. Время старта олимпиады 14.00 местного (12.00 московского). Завершение - то-же время следующего дня.

[xdsl]

Других предложений не поступило, дату фиксируем, запускаем процесс рассыла информационных писем.

[Vladislav_133]

Есть еще один вопрос, который, на мой взгляд, следует обсудить. Собственно он только частично относится к данной олимпиаде.
Как проверять олимпиадные задания? Сейчас очень модны тесты. И в этом есть смысл: большое количество участников и малый промежуток времени, который отводится для проверки, заставляет переходить к тестовой проверке. В очной олимпиаде, несомненно, придется пользоваться тестовым подходом. Но в заочной олимпиаде, где количество участников (в нашей пока так) относительно не велико (я думаю 10-15 человек) есть смысл проверять тексты программ. Тем самым мы сможем расширить диапазон возможных задач и более внимательно подойдем к участникам. Время для проверки будет. Мне кажется тем самым мы не отпугнем некоторых потенциальных участников. С Д.А. мы уже говорили на эту тему, он в приниципе с такой постановкой согласен.

[xdsl]

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

[Vladislav_133]

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

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

[xdsl]

Итак, до старта олимпиады остался один день. Последнее причесывание условий задач, последние тестирования. К сожалению, полноценных четыре задачи скорее всего не выйдет. Буквально позавчера ночью обнаружил нерешаемость (типа теоремы Ферма ) одной из своих задач. Оказалось, что учел только частный случай. В результате, вся красота у задачки испарилась как снежок летом, а решение стало почти тривиальным. Ее условие пока не разглашаю, т.к. питаю слабые надежды за сегодняшний вечер ситуацию все-таки исправить.

Таким образом гарантировано будут 3 задачи: две от В.Ю., как воспоминание об инженерных проблемах нашей молодости, и одна моя, навеянная пиратскими мотивами Джека Воробья

Стартуем завтра, 18 февраля 2009 года, в 14.00 местного (GMT+5)!

[Vladislav_133]

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

[xdsl]

START! http://shgpi.edu.ru/f11/info/conf_olimp_2009/objavl_zao_olimp_2009.html
Плюс ссылка с головной страницы shgpi.edu.ru

Запоздали на целых полчаса, правили стиль.

И еще: можно прогонять тестовые данные через наши варианты решений и наблюдать за результатом. Для этого в очередной раз запустили Solver: http://shgpi.edu.ru/vc.shgpi/solver2009/

[Vladislav_133]

Несколько слов о задачах 2 и 3.
Если ваши программы будут давать правильный результат в некоторых случаях и не правильный в других,
все равно присылайте решения. Будет анализироваться алгоритм и, возможно, вы получите баллы за не решенную полностью задачу.

Напоминаю, что работает решатель http://shgpi.edu.ru/vc.shgpi/solver2009/ .

[vovan]

Здравствуйте, у меня 2 вопроса по поводу первой задачи.
1) Могут ли опции в командах состоять лишь из символов - и /?
Например: com - /
2) Есть ли ограничения на длину строки?

[Vladislav_133]

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

[xdsl]

1. Длина строки может быть произвольной, ограничений нет
2. В условие сказано, что опция может состоять из латинских букв. На самом деле - это оговорка. Опция состоит из латинских букв. Поэтому просто "-" или "/" я опцией не считаю, однако если укажете в заголовке задачи, что учитываете такой вариант, ваше решение будет считаться корректным.

[xdsl]

Появились первые решения и это - не наши . Челябинский Государственный Педагогический Университет. Вот так-то.
Хотя, зная наших студентов, прогнозирую - решения поступят с 13ч59м01с до 13ч59м58с

[Chess]

Здравствуйте!

По рекомендации в письме, задаю вопросы здесь:
1. По задачам 2 и 3: написано, что нельзя использовать функции проеобразования строка-число. Это что, значит даже "разделив" строку на части (по одной или несколько цифр) нельзя воспользоваться паскалевским val или дельфийским StrToInt, чтобы дальше вычисления уже с числами производить? Может ограничение касается только дробных чисел?
2. По задаче 3: имеет ли значения в каком регистре набраны "цифры" шестнадцатеричного числа? Т.е. входные данные всегда 'abcdef' или могут быть ABCDEF', 'AbCdEf'?

и ещё:
3. По задаче 3: Есть ли требования на количество знаков после запятой?
4: По задаче 1: Правильно ли я понял, что начинаться с пробела строка не может (т.е. должна идти сразу команда)? И параметр может быть в кавычках, вне зависимости от того, есть ли в нём пробелы("a b" и "ab")? Пустые кавычки ("")- ошибка?

P.S.
Четвёртая задача понравилась
Только по легенде задачи приходская книга автоматически была бы "отсортирована" по году рождения и id шли бы в порядке возрастания.

[Vladislav_133]

Здравствуйте!

По рекомендации в письме, задаю вопросы здесь:
1. По задачам 2 и 3: написано, что нельзя использовать функции проеобразования строка-число. Это что, значит даже "разделив" строку на части (по одной или несколько цифр) нельзя воспользоваться паскалевским val или дельфийским StrToInt, чтобы дальше вычисления уже с числами производить? Может ограничение касается только дробных чисел?
2. По задаче 3: имеет ли значения в каком регистре набраны "цифры" шестнадцатеричного числа? Т.е. входные данные всегда 'abcdef' или могут быть ABCDEF', 'AbCdEf'?

и ещё:
3. По задаче 3: Есть ли требования на количество знаков после запятой?
4: По задаче 1: Правильно ли я понял, что начинаться с пробела строка не может (т.е. должна идти сразу команда)? И параметр может быть в кавычках, вне зависимости от того, есть ли в нём пробелы("a b" и "ab")? Пустые кавычки ("")- ошибка?

P.S.
Четвёртая задача понравилась
Только по легенде задачи приходская книга автоматически была бы "отсортирована" по году рождения и id шли бы в порядке возрастания.

1. Да, предполагалось, что нельзя использовать никакие функции преобразования. Но если вы будете использовать функции преобразования для целых чисел, это будет считаться лишь погрешностью.
2. Регистр не должен иметь значение.
3. Количество знаков после запятой будет ограничено тем, что у вас хранится в мантиссе. Если я не ошибаюсь, получается 9 знаков в десятичной системе. Ну если на дробную часть предполагается 32-бита.

[LMP]

2 и 3 задачи: является ли вывод на экран числа запрещённым преобразованием из числа в строку(например writeln(15) напишет "15")?

[xdsl]

4: По задаче 1: Правильно ли я понял, что начинаться с пробела строка не может (т.е. должна идти сразу команда)? И параметр может быть в кавычках, вне зависимости от того, есть ли в нём пробелы("a b" и "ab")? Пустые кавычки ("")- ошибка?

Н-да, вот что значит вспешке формулировать "разминочную" задачу

Пустые кавычки - ошибка, т.к. кавычки должны ограничивать параметр, а параметра, получается, нет.
Кавычки могут быть у любого параметра. Если в параметре пробелы - то должны.
Начальные и завершающие пробелы - не более чем разделители. Делайте trim(исх.строка) и начинайте анализ

[Vladislav_133]

2 и 3 задачи: является ли вывод на экран числа запрещённым преобразованием из числа в строку(например writeln(15) напишет "15")?

Нужно вывести строку, как сказано в задаче.

[vovan]

вопрос по 1 задаче. Если параметр в кавычках состоит только из пробелов, то это тоже ошибка?

[xdsl]

вопрос по 1 задаче а если параметр в кавычках состоит только из пробелов то это тоже ошибка?

Нет, это не ошибка. Пробел - разрешенный символ для параметра (см. условие задачи). Также как любая латинская буква. Например "ZZZZ" и четыре пробела в кавычках структурно эквивалентны