Страница 1 из 6

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

СообщениеДобавлено: 09 янв 2012, 12:16
xdsl
21-22 февраля 2012 года (со вторника на среду) в рамках подготовки к традиционному весеннему студенческому форуму факультет Информатики, математики и физики (С 9 декабря 2011 года - объединенный факультет на базе информатиков и физмата) проводит заочную студенческую олимпиаду по программированию.

Начало олимпиады 21.02.2012 года в 14 ч. (12.00 Москвы). Условия задач будут опубликованы здесь, на форуме, а также в новостях веб-портала http://shgpi.edu.ru. Решения (два файла: с исходным текстом программы на одном из распространенных языков программирования и исполняемый файл) будут приниматься по электронной почте (olimp@shgpi.edu.ru) до 14 ч. 22.02.2012 г.

Файл с исходным текстом программы должен начинаться с головного комментария, содержащего следующую информацию: номер решаемой задачи, фамилию, имя и отчество автора решения, курс, группу, специальность, наименование вуза и факультета, город, а также контактные данные (e-mail, по желанию - телефон, почтовый адрес).
Например:
Код: Выделить всё
// задача 1
// Иванов Иван Иванович
// 2 курс, 286 группа, спец. ПОВТ (230105.65 Программное обеспечение вычислительной техники и автоматизированных систем)
// ФГБОУ ВПО Шадринский государственный педагогический институт, г. Шадринск
// email - iii@shgpi.edu.ru
// ...
...


Итоги олимпиады будут подведены до 1 марта 2011 г и опубликованы на форуме и на веб-портале ШГПИ shgpi.edu.ru. Дополнительно, при участии в очной олимпиаде в рамках конференции, победители заочной олимпиады получают 10% бонус по очкам. Ах да, еще мы награждаем победителей небольшими, но приятными призами ;).

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

Оргкомитет олимпиады самостоятельно придумывает и прорешивает олимпиадные задачи. Любые совпадения условий задач нашей олимпиады с олимпиадными задачами всероссийских и международных олимпиад чаще всего случайны. Изредка сторонние олимпиадные задачи берутся за основу при создании наших задач. Для проверки решений мы обычно формируем набор тестов, которые публикуем по окончании олимпиады.

Получить доступ к условиям задач олимпиад прошлых лет (2006-2011 годов) и попробовать свои силы в их решении можно с помощью системы эталонных решений Solver (http://shgpi.edu.ru/solver/).

Анонсы, обсуждения, тесты, решения заочных олимпиад прошлых лет доступны здесь:
2009 год (https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=46),
2010 год (https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=184),
2011 год (https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=502)

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

СообщениеДобавлено: 20 фев 2012, 22:04
Vladislav_133
Ну, что же, время X приближается. Мы с Дм. Анатольевичем почти готовы.

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

СообщениеДобавлено: 21 фев 2012, 12:00
Vladislav_133
Остался один час. Все согласовано: тексты, очки. Волнуюсь, словно я участник.

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

СообщениеДобавлено: 21 фев 2012, 13:26
Vladislav_133
На портале задания уже висят
http://shgpi.edu.ru/files/olimps/olimp2 ... _stud.html

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

СообщениеДобавлено: 21 фев 2012, 13:39
Vladislav_133
Возникающие вопросы публикуйте здесь. Будем стараться отвечать оперативно.

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

СообщениеДобавлено: 21 фев 2012, 14:45
profi
Владислав Юрьевич вопрос по 4 задаче. Могут ли присутствовать одинаковые строки, т.е например
1 4
1 4

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

СообщениеДобавлено: 21 фев 2012, 14:57
JalbaRu
Задача 1.
Какое максимальное количество строк?
В ответе в четвертой строке нужно выводить все зараженные антивирусом(в том числе возможно изначально зараженные вирусом) или зараженные только антивирусом(но не зараженные вирусом)?
Задача 2.
Если система исчисления больше 9, то как записывать числа больше 9?
Задача 4.
Какое максимальное количество пар?

И вопрос по всем задачам: какие временные ограничения?

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

СообщениеДобавлено: 21 фев 2012, 15:15
xdsl
JalbaRu писал(а):Задача 1.
Какое максимальное количество строк?
В ответе в четвертой строке нужно выводить все зараженные антивирусом(в том числе возможно изначально зараженные вирусом) или зараженные только антивирусом(но не зараженные вирусом)?

Тест на десяток мегабайт input.txt у меня есть. Сколько там строк - не считал, не подумал, что кто-то будет загружать весь файл в память. Давайте тогда ограничим: 5 миллионов строк максимум.

JalbaRu писал(а):Задача 2.
Если система исчисления больше 9, то как записывать числа больше 9?

abcdef...xyz

JalbaRu писал(а):И вопрос по всем задачам: какие временные ограничения?

по первым двум - 1 секунда
сейчас проверил на первой задаче, >30МБ, >10млн.строк моя программа работает 0.97 с. (dell vostro 1015, linux 32 bit, freepascal 2.4.2)

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

СообщениеДобавлено: 21 фев 2012, 15:20
Vladislav_133
Для profi. Я так понимаю, вы спрашиваете о входной информации. Поскольку ничего не оговорено, то да, может. Это не противоречит другим положениям задачи и общему ее духу.

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

СообщениеДобавлено: 21 фев 2012, 15:29
Vladislav_133
Еще по поводу 4-1 задачи. Соглашусь, что здесь есть неопределенность некоторая. Поэтому уточню: примем, что количество записей (пар) во входном файле не будет превышать 30 000. Данное ограничение будет соответствовать тому количеству очков, которое определено для задачи. Хотя задача может быть решена и для произвольного количества пар.

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

СообщениеДобавлено: 21 фев 2012, 15:53
profi
Дмитрий Анатольевич вопрос по 1 задаче. Можете подробнее объяснить вот это -В первой - номер строки (нумерация с 0) файла input.txt, в которой находится последняя коммуникация между системами, после которой можно говорить о купировании или уничтожении пандемии. Да и еще количество систем ограничено латинским алфавитом, т.е. 26 всего?

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

СообщениеДобавлено: 21 фев 2012, 15:54
JalbaRu
Задача 1.
Пусть система А заражена вирусом, система В заражена антивирусом. Появляется путь из В в А. Что произойдет дальше?
В условие есть такое предложение "Антивирус заражает любую систему и уничтожает найденный в ней вирус". То есть система А больше не заражена вирусом, а заражена антивирусом?

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

СообщениеДобавлено: 21 фев 2012, 16:01
Vladislav_133
Еще по поводу 3-1 задачи.

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


имеется в виду, что будут выдаваться пути, длина которых равна минимальному количеству шагов.

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

СообщениеДобавлено: 21 фев 2012, 16:54
xdsl
JalbaRu писал(а):Задача 1.
Пусть система А заражена вирусом, система В заражена антивирусом. Появляется путь из В в А. Что произойдет дальше?
В условие есть такое предложение "Антивирус заражает любую систему и уничтожает найденный в ней вирус". То есть система А больше не заражена вирусом, а заражена антивирусом?

Да, система A становится заражена антивирусом, вируса в ней больше нет.

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

СообщениеДобавлено: 21 фев 2012, 16:59
JalbaRu
xdsl писал(а):
JalbaRu писал(а):Задача 1.
Пусть система А заражена вирусом, система В заражена антивирусом. Появляется путь из В в А. Что произойдет дальше?
В условие есть такое предложение "Антивирус заражает любую систему и уничтожает найденный в ней вирус". То есть система А больше не заражена вирусом, а заражена антивирусом?

Да, система A становится заражена антивирусом, вируса в ней больше нет.

А почему тогда в первом примере в третьей строке выводится три системы когда зараженных вирусом только одна Z. И аналогично в четвертой строке почему только три вместо пяти?

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

СообщениеДобавлено: 21 фев 2012, 17:00
xdsl
profi писал(а):Дмитрий Анатольевич вопрос по 1 задаче. Можете подробнее объяснить вот это -В первой - номер строки (нумерация с 0) файла input.txt, в которой находится последняя коммуникация между системами, после которой можно говорить о купировании или уничтожении пандемии. Да и еще количество систем ограничено латинским алфавитом, т.е. 26 всего?

1) По номеру строки. Это означает, что все дальнейшие коммуникации, описанные в input.txt, изменений в составе зараженных систем не внесут. Вырожденный случай - второй пример. Там как был изначально один компьютер заражен, так он и остается зараженным до самого конца - вирус купирован.
Или, допустим, вирус исчез после какого-то шага.

2) Да, 26.

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

СообщениеДобавлено: 21 фев 2012, 17:12
xdsl
JalbaRu писал(а):А почему тогда в первом примере в третьей строке выводится три системы когда зараженных вирусом только одна Z. И аналогично в четвертой строке почему только три вместо пяти?

Не понял про первый пример.Разберем:
z - вирус
a - анитивирус
Далее:
ab
ba
cd
ab
антивирус на системах ab

ze
de
вирус на системах ze

ea
вирус попытался заразить систему с антивирусом. Неудачно, все остались при своих, т.к. коммутации - однонаправленные

ef
вирус на системах zef

ad
антивирус на системах abd

fa
пять неудачный наезд вируса на антивирус, все остались при своих.

резюме:
чистая система - с
вирус - efz
антивирус - abd

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

СообщениеДобавлено: 21 фев 2012, 17:31
CSander
вопрос по 4 задаче, вывод сортировать, или в таком порядке как есть? (в условии задачи не сказано)

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

СообщениеДобавлено: 21 фев 2012, 18:03
JalbaRu
xdsl писал(а):
JalbaRu писал(а):И вопрос по всем задачам: какие временные ограничения?

по первым двум - 1 секунда
сейчас проверил на первой задаче, >30МБ, >10млн.строк моя программа работает 0.97 с. (dell vostro 1015, linux 32 bit, freepascal 2.4.2)

А почему одна секунда? Такой большой объем данных будет считываться в лучшем случае секунду

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

СообщениеДобавлено: 21 фев 2012, 18:08
eJay
Здравствуйте, а можно тестовый файл на первую задачу?

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

СообщениеДобавлено: 21 фев 2012, 18:08
Vladislav_133
По поводу 4-й задачи. Для CSander. Нет, сортировать не надо. Нужен просто список.

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

СообщениеДобавлено: 21 фев 2012, 18:10
kolesa
xdsl
"Весом" цифры будем считать основание системы счисления кода (от 2 до 35).
"Весом" кода будем считать сумму весов всех цифр кода.

поясните, на примере как происходит расчет веса
на примере, про Васю
00000001001000110100010101100111100010011010101110011100 тут сколько? 112?
0001020310111213202122232130 и тут?

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

СообщениеДобавлено: 21 фев 2012, 18:12
xdsl
Про секунду:
Факты говорят, что гораздо быстрее. Секунда - это у меня на объеме в 2 раза большем и с полной обработкой. Характеристики своей системы я привел, они вполне даже средние. Ах да - два ядра и 2ГБ памяти. В любом случае - проверять решения буду на своей машине, так что при эффективном алгоритме проблем быть не должно.

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

СообщениеДобавлено: 21 фев 2012, 18:15
xdsl
eJay писал(а):Здравствуйте, а можно тестовый файл на первую задачу?

Это который большой с обработкой в 1 секунду? без проблем. Только разархивировать не забудьте.

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

СообщениеДобавлено: 21 фев 2012, 18:20
xdsl
kolesa писал(а):xdsl
"Весом" цифры будем считать основание системы счисления кода (от 2 до 35).
"Весом" кода будем считать сумму весов всех цифр кода.

поясните, на примере как происходит расчет веса
на примере, про Васю
00000001001000110100010101100111100010011010101110011100 тут сколько? 112?
0001020310111213202122232130 и тут?

Да, 112. Во втором варианте - тоже 112 и это минимальное значение из всех возможных.