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

Знаковые события в научной и общественной жизни вуза.

Модератор: xdsl

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

Сообщение xdsl 09 янв 2012, 12:16

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)
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение Vladislav_133 20 фев 2012, 22:04

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

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

Сообщение Vladislav_133 21 фев 2012, 12:00

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

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

Сообщение Vladislav_133 21 фев 2012, 13:26

На портале задания уже висят
http://shgpi.edu.ru/files/olimps/olimp2 ... _stud.html
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 21 фев 2012, 13:39

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

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

Сообщение profi 21 фев 2012, 14:45

Владислав Юрьевич вопрос по 4 задаче. Могут ли присутствовать одинаковые строки, т.е например
1 4
1 4
profi
Elite
 
Сообщения: 25
Зарегистрирован: 09 июн 2009, 22:30
Полное имя: Сапожников Игорь Валерьевич

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

Сообщение JalbaRu 21 фев 2012, 14:57

Задача 1.
Какое максимальное количество строк?
В ответе в четвертой строке нужно выводить все зараженные антивирусом(в том числе возможно изначально зараженные вирусом) или зараженные только антивирусом(но не зараженные вирусом)?
Задача 2.
Если система исчисления больше 9, то как записывать числа больше 9?
Задача 4.
Какое максимальное количество пар?

И вопрос по всем задачам: какие временные ограничения?
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

Сообщение xdsl 21 фев 2012, 15:15

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)
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение Vladislav_133 21 фев 2012, 15:20

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

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

Сообщение Vladislav_133 21 фев 2012, 15:29

Еще по поводу 4-1 задачи. Соглашусь, что здесь есть неопределенность некоторая. Поэтому уточню: примем, что количество записей (пар) во входном файле не будет превышать 30 000. Данное ограничение будет соответствовать тому количеству очков, которое определено для задачи. Хотя задача может быть решена и для произвольного количества пар.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение profi 21 фев 2012, 15:53

Дмитрий Анатольевич вопрос по 1 задаче. Можете подробнее объяснить вот это -В первой - номер строки (нумерация с 0) файла input.txt, в которой находится последняя коммуникация между системами, после которой можно говорить о купировании или уничтожении пандемии. Да и еще количество систем ограничено латинским алфавитом, т.е. 26 всего?
profi
Elite
 
Сообщения: 25
Зарегистрирован: 09 июн 2009, 22:30
Полное имя: Сапожников Игорь Валерьевич

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

Сообщение JalbaRu 21 фев 2012, 15:54

Задача 1.
Пусть система А заражена вирусом, система В заражена антивирусом. Появляется путь из В в А. Что произойдет дальше?
В условие есть такое предложение "Антивирус заражает любую систему и уничтожает найденный в ней вирус". То есть система А больше не заражена вирусом, а заражена антивирусом?
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

Сообщение Vladislav_133 21 фев 2012, 16:01

Еще по поводу 3-1 задачи.

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


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

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

Сообщение xdsl 21 фев 2012, 16:54

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

Да, система A становится заражена антивирусом, вируса в ней больше нет.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение JalbaRu 21 фев 2012, 16:59

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

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

А почему тогда в первом примере в третьей строке выводится три системы когда зараженных вирусом только одна Z. И аналогично в четвертой строке почему только три вместо пяти?
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

Сообщение xdsl 21 фев 2012, 17:00

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

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

2) Да, 26.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение xdsl 21 фев 2012, 17:12

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

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

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

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

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

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

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

резюме:
чистая система - с
вирус - efz
антивирус - abd
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение CSander 21 фев 2012, 17:31

вопрос по 4 задаче, вывод сортировать, или в таком порядке как есть? (в условии задачи не сказано)
Аватара пользователя
CSander
 
Сообщения: 3
Зарегистрирован: 12 дек 2009, 08:24
Откуда: Шадринск
Полное имя: Усольцев Александр Владимирович

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

Сообщение JalbaRu 21 фев 2012, 18:03

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

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

А почему одна секунда? Такой большой объем данных будет считываться в лучшем случае секунду
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

Сообщение eJay 21 фев 2012, 18:08

Здравствуйте, а можно тестовый файл на первую задачу?
eJay
 
Сообщения: 1
Зарегистрирован: 21 фев 2012, 17:52
Полное имя: Ядрышников Андрей

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

Сообщение Vladislav_133 21 фев 2012, 18:08

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

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

Сообщение kolesa 21 фев 2012, 18:10

xdsl
"Весом" цифры будем считать основание системы счисления кода (от 2 до 35).
"Весом" кода будем считать сумму весов всех цифр кода.

поясните, на примере как происходит расчет веса
на примере, про Васю
00000001001000110100010101100111100010011010101110011100 тут сколько? 112?
0001020310111213202122232130 и тут?
kolesa
 
Сообщения: 18
Зарегистрирован: 21 фев 2012, 17:29
Полное имя: kolesa

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

Сообщение xdsl 21 фев 2012, 18:12

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

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

Сообщение xdsl 21 фев 2012, 18:15

eJay писал(а):Здравствуйте, а можно тестовый файл на первую задачу?

Это который большой с обработкой в 1 секунду? без проблем. Только разархивировать не забудьте.
Вложения
5.txt.gz
(73.88 Кб) Скачиваний: 791
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение xdsl 21 фев 2012, 18:20

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

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

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

След.

Вернуться в Конференции и семинары, олимпиады и форумы, выставки и конкурсы в ШГПУ

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

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