Заочная олимпиада 2010

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Заочная олимпиада 2010

Сообщение Vladislav_133 19 фев 2010, 11:56

Через 2.5 часа начнется очередная заочная олимпиада по программированию. По окончанию олимпиады, здесь будут обсуждаться задания, выкладываться варианты решений и т.д.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 20 фев 2010, 16:18

Ну что же, олимпиада закончилась, по-крайней мере, вторая ее часть. Первая - подготовка, третья - проверка и оглашение результатов. Можно высказываться по поводу задач, решений и т.д. Кажется нынче учатников гораздо больше чем в прошлые годы. Конечно, мы тоже старались, ведь многие о ней просто не знали.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 21 фев 2010, 16:06

Начались комментарии. Проверка работ - это целая эпопея. Позднее поделюсь. Начал проверять около 11 и закончу, наверное, также к 11. Думаю, что у Дмитрия Анатольевича такая же ситуация.

По делу.

1.Удалены лишние пробелы. Другими словами, если между словами имеется n пробелов, то должен остаться только один. В случае, если пробелы стоят в начале строки, то должен остаться один пробел.

2.Если после слова идут несколько пробелов, а потом знак препинания, то пробелы должны быть удалены.

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


По-моему, все очень четко написано. "aba , habba" --> "aba, haba", разве не так? Поэтому и "aba,habba" тоже --> "aba, haba". Ну нет другого истолкования. У меня складывается впечатление, что некоторые чего-то не поняли. Например, посчитав, что есть разница между точкой и запятой. По условию задачи нет.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 21 фев 2010, 20:07

Нынешняя олимпиада побила рекорды по диапазону используемых яыков и компиляторов: Pascal (Freepascal, Delphi, Turbo Pascal), C++, php, Pyton, Java, JavaScript. Проверять, конечно, сложно, но радует, что люди, программирующие на разных языках, стараются владеть этим инструментом в совершенстве.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 24 фев 2010, 21:09

ну что ж приступим...
выскажу только своё мнение
1ая задача:
самая простая, решение там элементарное... получил за неё 0 баллов... как всегда из-за своей невнимательности
для работы скрипта надо было поставить пробелы после знаков препинания.(исправлено)
2ая задача:
пожалуй третья по сложности. получил за неё 2 балла
до сих пор не могу понять где там у меня ошибки, но ведь они есть(как было так и осталось)
3я задача:
самая сложная. убив изначально на её решение порядка 6часов получил 4 балла... ошибок в ней было много по этому описывать их я не буду... (переписал весь алгоритм, вроде работает)
4ая задача:
вторая по сложности (долго думал вторая или третья)... ошибка в ней элементарнейшая... погнался за скоростью работы забыв про качество... в итоге 0 баллов(исправлено)

P.S. то что написано в скобках в конце описания задачи это то на каком этапе находится моё решение этой задачи на текущий момент.
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 24 фев 2010, 21:24

Думаю, что все же 4-я задача самая сложная. В ней есть две вещи: 1. Алгоритм выявления тегов. Он очевидно рекурсивный, так как теги могут быть вложенными. 2. Реализация всех положений о тегах.
Замечу, что 4-ю задачу полностью решил тоько один человек.
Впрочем, это все лирика. Если DD, у вас действительно дело в мелочах, то давайте правильное решение. Тем более, что там у вас на основе регуярных выражений и это интересно. Интересно рассмотреть разные решения.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 24 фев 2010, 21:36

поясню почему четвёртая задача для меня не самая сложная...
все гениальное просто, я когда-то делал класс шаблонизатор, он как раз этим и занимался... эт раз...
второе: мне когда-то было лениво изучать класс для работы с BB кодами для форумов и сайтов и по этому написал свой...

вот моё исправленное решение
Вложения
4.tar.gz
(933 байт) Скачиваний: 516
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение xdsl 24 фев 2010, 21:38

Замечу, что 4-ю задачу полностью решил тоько один человек.

Ха, а третью - вообще из студентов никто не решил ;). Но считаю, что четвертая задача - сложнее, т.к. имеет в условии много слабоучитываемых нюансов, можно легко запутаться (как, впрочем, и вторая). В то время как третья - проста в условии, как топор. Лично мне такие задачи решать проще.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Заочная олимпиада 2010

Сообщение [DD] 24 фев 2010, 21:50

если в скрипте будут ошибки(а они скорее всего будут) сообщите о них тут буду исправлять дальше...

P.S. думаю xdsl как никто другой знает, то, что я не умею искать баги в своих скриптах :D
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 24 фев 2010, 22:02

DD
по новому решению

Пример
<1><1><1><1>1< /></></>

<1><1><1>>/

но это не верно

<2>123</>
123
и это не верно
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 24 фев 2010, 23:47

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

1. Порядок следования тегов: отсутствие закрывающего тега, отсутствие открывающего тега.
2.Ошибка в структуре тега: наличие пробелов между символами < и 1 и между символами < и 2, отсутствие хотя бы одного параметра для тега 2.
3.Ошибка в записи параметров. Отсутствие символов в пар2. Отсутствие символов в пар1 ошибкой не является.


судя по тому, что теги игнорируются(именно теги а не их содержимое) то второй пример верен...
возможно я что-то не так понял, по этому сделаю игнорирование тега вместе с содержимым(что делает задачу еще проще)...
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение [DD] 25 фев 2010, 04:21

вроде исправил...
Вложения
4.tar.gz
(928 байт) Скачиваний: 489
Последний раз редактировалось [DD] 25 фев 2010, 12:00, всего редактировалось 3 раз(а).
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 08:15

Вечером проверим. А на счет второго примера. Игнорировать, значит оставить без изменения.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 25 фев 2010, 11:24

вот оно что... изменил в соответствии с этим требованием
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 14:31

DD
ну и ждем результат
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 25 фев 2010, 16:04

решение тут
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 17:40

Ну и что? Рузельтат тот же.
<2>123</>

<2>123</>
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 25 фев 2010, 17:45

это соответствует вашему решению... проверено в солвере...
P.S. эта ситуация мне сильно напоминает ту что была у нас при выполнении лабораторных работ Кириллова А.Г., он всегда говорил что если у него что-то не правильно работает то мы это должны исправить... но он то хотя бы сообщал что он хочет видеть в результате...
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 17:53

Прошу прощения. Я только что от зубного врача и голова не соображает.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 17:56

Но вот это вариант то точно не работает.

<2 """3">123</>

<2 """3">123</>
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 25 фев 2010, 18:10

исправлено
Вложения
4.rar
(987 байт) Скачиваний: 461
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 18:19

<1><2 """2">123</></>

321>"2""" 2<</>

все, больше ничего не присылать, пока не сделаете окончательно. А то мы тут всю ветку забьем, да и я не тестировщик.
В конце концов, пора и решения разбирать.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение [DD] 25 фев 2010, 20:13

хорошо. присылать больше ни чего не буду...
только вот в ходи исправлений возникла парочка вопросов...
входящие данные: <1><2"<1>""b">1b32</></></>
solver: b23
мой скрипт: 321

1) какой вариант правильный?
2) если первый - то как это получилось?
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 21:05

Как получилось в солвере ответить не могу, пока свой код не посмотрел.
Однако, это пример не прописанной в условии ситуации, когда
тег оказывается в качестве параметра. Ситуация, действительно, неопределнна, так
записанную строку можно трактовать и так и так: <2"<1>""b">.... - это тег 2 или тег 1?
Для меня это не ясно. Это надо прописывать в условии. Таким образом, оба ответа следует
признать правильными.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Заочная олимпиада 2010

Сообщение Vladislav_133 25 фев 2010, 21:13

Кстати, проблема бы разрешилась, если бы были введены закрывающие теги отдельно для тега 1 и отдельно для тега 2. Я об этом в условии написал. Поэтому можно сказать так: неопределнность вытекает из того, что имеется только один закрывающий тег.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

След.

Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 3

cron