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

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

СообщениеДобавлено: 13 дек 2010, 14:08
xdsl
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).

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

Условия задач

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

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

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

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

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

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

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

спасибо. пойду посмотрю=)

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

СообщениеДобавлено: 14 фев 2011, 09:18
xdsl
Осталась неделя. Активно готовим задачки. Думаю, их будет 4-5.

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

СообщениеДобавлено: 18 фев 2011, 16:04
xdsl
По просьбам трудящихся внесены и выделены жирным шрифтом уточнения в головной пост темы.

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

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

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

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

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

Немного статистики: судя по логам сервера, на текущий момент условия задач внимательно и не по разу прочитали 46 человек.

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

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

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

2. Символы, код которых меньше кода пробела (32), считаются управляющими. Символ(ы) перевода строк (10,13) не считать, у них свой функционал.

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

СообщениеДобавлено: 19 фев 2011, 21:28
DEIMON
есть вопрос по четвертой задаче
110111
100000
101111
100111
111111
куда пойдет капля в данной ситуации по законам гравитации не понятно.

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

СообщениеДобавлено: 19 фев 2011, 21:42
xdsl
На выход. На самом деле, и налево и направо, падение распределит ее равномерно, а т.к. мы рассматриваем идеальную систему, сил, способных аннулировать правый импульс - нет. Значит - на правом выходе половина капли сольется. Ответ - 1.

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

СообщениеДобавлено: 19 фев 2011, 21:58
DEIMON
хорошо тогда в таком случае что будет в принципе капля может пойти в обе стороны но исход разный
111101111
100000001
101111101
000111000
110110001
100110001
111111111
111111111
111111111

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

СообщениеДобавлено: 19 фев 2011, 22:03
Vladislav_133
естественно капля выйдет в левое отверстие

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

СообщениеДобавлено: 19 фев 2011, 22:05
xdsl
И здесь ответ - 1. Половина от капли уходит влево. Там она разбивается еще пополам и четверть выплескивается наружу.

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

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

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

СообщениеДобавлено: 19 фев 2011, 22:48
xdsl
В первом случае две капли заполнят лабиринт (прохода нигде нет, по диагонали вода не сливается по условию задачи), третья уже не войдет в лабиринт, соответственно - вода покажется на выходе. Ответ - 3.

Во втором случае 4 капли заполнят нижний уровень. Еще 4 - уровень выше. Последняя, девятая капля, поднимет уровень достаточно, чтобы вода вылилась справа. Ответ - 9.

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

СообщениеДобавлено: 19 фев 2011, 23:35
AsdeK
я конечно извиняюсь, но если по условию, по диагонали капли скатываться не могут, как они сверху на нижний уровень попадут?

и ещё по третьей задаче: в каком углу квадрата начинается система координат и какая ось Х и Y соответственно?

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

СообщениеДобавлено: 19 фев 2011, 23:44
Vladislav_133
Ситуация симмеричная, и результат не должен зависеть от этого. Ну, примите, что начало координат в левом нижнем углу, это наиболее естественно.

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

СообщениеДобавлено: 19 фев 2011, 23:50
xdsl
11101111
10101111
10101000
10100011
10000110 <-- вот он, нижний уровень. ниже воды не будет, значит - нижний
11111000
00000000
11100001

Если не нравится слово "нижний", то пусть будет, например - пятый сверху. Или четвертый снизу.

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

СообщениеДобавлено: 20 фев 2011, 09:07
AsdeK
всё равно метод заполнения остаётся непонятым, хотелось бы поподробнее о самой процедуре заполнения, когда капля делится, а когда, и возможно ли, одной каплей заполнить уровень, или как по условию: капля - клетка...
я могу ошибаться, но вот понял:
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

если Вы как-то прокомментируете мои рассуждения, буду очень признателен

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

СообщениеДобавлено: 20 фев 2011, 09:27
xdsl
111011 111511
000000 444444
111011 111311
111000 111222 <-- второй уровень
100011 111111 <-- первый уровень
111111 111111

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

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

Правильный ответ - 4, ваш рисунок - неверен.

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

СообщениеДобавлено: 20 фев 2011, 09:40
xdsl
Мне кажется, что у вас имеется принципиальное непонимание происходящего в задаче. Вода - это жидкость, а не твердое тело. При попадании новой капли в лабиринт она перемешивается с уже находящимися там и можно сказать, что какая-то часть новой капли будет во всех заполненных водой ячейках лабиринта. Дополнительно, совершенно не обязательно заполнение одной каплей ячейки до краев. Если у Вас 15 сообщающихся друг с другом ячеек на одной горизонтали, ограниченных стенами, то одна капля разольется по всем 15, заполнив каждую на 1/15 уровня. Вторая капля поднимет уровень еще на 1/15 итого - 2/15 и т.д.

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

СообщениеДобавлено: 20 фев 2011, 09:43
AsdeK
111011
000000 <-- четвёртый уровень
111011
111000 <-- второй уровень
100011
111111
ну а как же быть с четвёртым уровнем, ведь там вода должна также появиться?

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

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

СообщениеДобавлено: 20 фев 2011, 09:47
xdsl
а в последней ситуации я так и не понял как на "нижний уровень" попадёт вода, если она льётся сверху
.
Еще раз показываю, что понимается под нижним уровнем: https://shgpi.edu.ru/forum/viewtopic.php?p=3574#p3574
Или Вы не понимаете, как вода, которая льется сверху, оказывается внизу? ;)

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

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

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

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