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

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

Модератор: xdsl

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

Сообщение xdsl 13 дек 2010, 14:08

19-20 февраля 2011 года (с субботы на воскресенье) в рамках подготовки к традиционному весеннему студенческому форуму (http://shgpi.edu.ru/f11/novosti/2011/studencheskii-forum/) факультет информатики проводит заочную студенческую олимпиаду по программированию.

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

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

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


Получить доступ к условиям задач олимпиад прошлых лет (2007-2010 годов) и попробовать свои силы в их решении можно с помощью системы эталонных решений Solver. Для любителей минимализма в интерфейсе доступна предыдущая версия системы.

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

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

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

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

Сообщение Алексей_ 24 дек 2010, 17:18

А где будут выложены условия задач? тут? интересно будет посмотреть :) не думаю конечно что у меня знаний на что нибудь хватит, но хоть мозги по-мучаю :D
Алексей_
 
Сообщения: 55
Зарегистрирован: 15 фев 2010, 16:33
Полное имя: Алексей

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

Сообщение xdsl 25 дек 2010, 09:10

Алексей_ писал(а):А где будут выложены условия задач? тут? интересно будет посмотреть :) не думаю конечно что у меня знаний на что нибудь хватит, но хоть мозги по-мучаю :D

Конечно выложим. А пока можете глянуть в тред предыдущей олимпиады: https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=184
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение Алексей_ 25 дек 2010, 15:42

xdsl писал(а):Конечно выложим. А пока можете глянуть в тред предыдущей олимпиады: https://shgpi.edu.ru/forum/viewtopic.php?f=41&t=184

спасибо. пойду посмотрю=)
Алексей_
 
Сообщения: 55
Зарегистрирован: 15 фев 2010, 16:33
Полное имя: Алексей

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

Сообщение xdsl 14 фев 2011, 09:18

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

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

Сообщение xdsl 18 фев 2011, 16:04

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

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

Сообщение xdsl 19 фев 2011, 14:05

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

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

Сообщение xdsl 19 фев 2011, 20:37

Вопросы по условиям задач можно задавать здесь, предварительно зарегистрировавшись в форуме, а также письмом на olimp_shgpi@list.ru. Напоминаю, что регистрация на форуме требует активации администратором. Можете поторопить активацию письмом на olimp_shgpi@list.ru.

Ах да, ночью мы в основном спим ;). Поэтому вероятность быстрого ответа на вопрос, заданный, например, в 3.00 стремится к нулю.

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

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

Сообщение xdsl 19 фев 2011, 21:13

Поступили вопросы, ответы на которые будут интересны многим:
1. Есть ли какие нибудь ограничения по времени и памяти?
2. По задаче 1. Какие символы кроме пробела и символа табуляции могут быть управляющими символами?

1. По времени - если задача не отвечает в течении 5 секунд, она считается зависшей. По памяти - объем исходных данных может быть очень большой. Таким будет как минимум один тест для каждой задачи (кроме задачи 3 - там это невозможно по условию). Непрохождение такого теста снизит оценку.

2. Символы, код которых меньше кода пробела (32), считаются управляющими. Символ(ы) перевода строк (10,13) не считать, у них свой функционал.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение DEIMON 19 фев 2011, 21:28

есть вопрос по четвертой задаче
110111
100000
101111
100111
111111
куда пойдет капля в данной ситуации по законам гравитации не понятно.
DEIMON
Elite
 
Сообщения: 88
Зарегистрирован: 14 сен 2009, 19:03
Откуда: ВЦ ШГПИ
Полное имя: Сысоев Д.М

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

Сообщение xdsl 19 фев 2011, 21:42

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

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

Сообщение DEIMON 19 фев 2011, 21:58

хорошо тогда в таком случае что будет в принципе капля может пойти в обе стороны но исход разный
111101111
100000001
101111101
000111000
110110001
100110001
111111111
111111111
111111111
DEIMON
Elite
 
Сообщения: 88
Зарегистрирован: 14 сен 2009, 19:03
Откуда: ВЦ ШГПИ
Полное имя: Сысоев Д.М

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

Сообщение Vladislav_133 19 фев 2011, 22:03

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

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

Сообщение xdsl 19 фев 2011, 22:05

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

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

Сообщение AsdeK 19 фев 2011, 22:09

не могли бы Вы подробнее объяснить почему(как и в какой последовательности идет заполнение) здесь:
10111
10110
11010
11011
11111
получается 3, а здесь:
11101111
10101111
10101000
10100011
10000110
11111000
00000000
11100001
получается 9, я просто самого условия понять не могу...
AsdeK
 
Сообщения: 12
Зарегистрирован: 19 фев 2011, 21:44
Полное имя: Нагибин Д.В.

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

Сообщение xdsl 19 фев 2011, 22:48

В первом случае две капли заполнят лабиринт (прохода нигде нет, по диагонали вода не сливается по условию задачи), третья уже не войдет в лабиринт, соответственно - вода покажется на выходе. Ответ - 3.

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

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

Сообщение AsdeK 19 фев 2011, 23:35

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

и ещё по третьей задаче: в каком углу квадрата начинается система координат и какая ось Х и Y соответственно?
AsdeK
 
Сообщения: 12
Зарегистрирован: 19 фев 2011, 21:44
Полное имя: Нагибин Д.В.

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

Сообщение Vladislav_133 19 фев 2011, 23:44

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

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

Сообщение xdsl 19 фев 2011, 23:50

11101111
10101111
10101000
10100011
10000110 <-- вот он, нижний уровень. ниже воды не будет, значит - нижний
11111000
00000000
11100001

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

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

Сообщение AsdeK 20 фев 2011, 09:07

всё равно метод заполнения остаётся непонятым, хотелось бы поподробнее о самой процедуре заполнения, когда капля делится, а когда, и возможно ли, одной каплей заполнить уровень, или как по условию: капля - клетка...
я могу ошибаться, но вот понял:
111011 111511
000000 444444
111011 111311
111000 111222
100011 111111
111111 111111
и того пять капель надо, а в ответе 4, или есть другая логика:
111011 111.11
000000 89...
111011 111711
111000 111456
100011 112311
111111 111111
тогда чтобы капля появилась сверху нужно вообще 13 капель.

а в последней ситуации я так и не понял как на "нижний уровень" попадёт вода, если она льётся сверху
11101111 11151111
10101111 14141111
10101000 13131333
10100011 12122211
10000110 11111110
11111000 11111000
00000000 00000000
11100001 11100001
здесь при такой логике получается всего 5, а не 9

если Вы как-то прокомментируете мои рассуждения, буду очень признателен
AsdeK
 
Сообщения: 12
Зарегистрирован: 19 фев 2011, 21:44
Полное имя: Нагибин Д.В.

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

Сообщение xdsl 20 фев 2011, 09:27

111011 111511
000000 444444
111011 111311
111000 111222 <-- второй уровень
100011 111111 <-- первый уровень
111111 111111

1) по условию задачи "объем каждой порции равен объему одной ячейки матрицы", а по вашему рисунку выходит, что первая и вторая капли объемом в три ячейки , а четвертая - в шесть ячеек.

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

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

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

Сообщение xdsl 20 фев 2011, 09:40

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

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

Сообщение AsdeK 20 фев 2011, 09:43

111011
000000 <-- четвёртый уровень
111011
111000 <-- второй уровень
100011
111111
ну а как же быть с четвёртым уровнем, ведь там вода должна также появиться?

"Задача заключается в определении минимально необходимого количества порций воды, которое требуется залить в матрицу-лабиринт для появления воды на любом из выходов лабиринта."
AsdeK
 
Сообщения: 12
Зарегистрирован: 19 фев 2011, 21:44
Полное имя: Нагибин Д.В.

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

Сообщение xdsl 20 фев 2011, 09:47

а в последней ситуации я так и не понял как на "нижний уровень" попадёт вода, если она льётся сверху
.
Еще раз показываю, что понимается под нижним уровнем: https://shgpi.edu.ru/forum/viewtopic.php?p=3574#p3574
Или Вы не понимаете, как вода, которая льется сверху, оказывается внизу? ;)
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение xdsl 20 фев 2011, 09:51

AsdeK писал(а):111011
000000 <-- четвёртый уровень
111011
111000 <-- второй уровень
100011
111111
ну а как же быть с четвёртым уровнем, ведь там вода должна также появиться?

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

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

След.

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

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

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

cron