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

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

Модератор: xdsl

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

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

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

ok! тогда мне не понятно, во втором примере (ababcdcde) ответ 010123234
там получается 3 одинаковых минимальных (с весом 54) Или что-то я все таки не понял в задании?
000 001 000 001 010 011 010 011 100
00 01 00 01 02 10 02 10 11
0 1 0 1 2 3 2 3 4
kolesa
 
Сообщения: 18
Зарегистрирован: 21 фев 2012, 17:29
Полное имя: kolesa

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

Сообщение Parlament 21 фев 2012, 18:40

По 3-ей задаче. Координаты переходов и преград располагаются хаотично или по мере поступления? Если преграда, то двигаться против часовой?
Parlament
 
Сообщения: 2
Зарегистрирован: 21 фев 2012, 10:12
Полное имя: Давыдов Владимир

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

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

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

ok! тогда мне не понятно, во втором примере (ababcdcde) ответ 010123234
там получается 3 одинаковых минимальных (с весом 54) Или что-то я все таки не понял в задании?
000 001 000 001 010 011 010 011 100
00 01 00 01 02 10 02 10 11
0 1 0 1 2 3 2 3 4

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

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

Сообщение Vladislav_133 21 фев 2012, 19:22

Третья задача. Координаты и проходов и перегородок в строке стоят хаотично. Да и какой порядок можно здесь установить.

Прикрепляю тесты к третьей задаче. Прошу прощения, у меня не input.txt и output.txt, а input и output. Сейчас обратил на это внимание.
Но я думаю, что это не проблема. Всего 18 тестов. Тесты содержат варианты с выдачей всех возможных путей.
Вложения
test3.zip
(7.62 Кб) Скачиваний: 395
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение JalbaRu 21 фев 2012, 19:23

Не могли бы Вы подсказать сколько по времени работает ваша программа на тесте вида
za
ab - 10млн раз
zc

На моем компьютере ваш тест работает около 7 сек, из которых чтение секунды 3. Правда я виндовсе сижу, может из за этого
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

Сообщение Vladislav_133 21 фев 2012, 19:25

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

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

Сообщение Parlament 21 фев 2012, 19:27

Parlament писал(а):По 3-ей задаче. Координаты переходов и преград располагаются хаотично или по мере поступления? Если преграда, то двигаться против часовой?


Я имел в виду, что, допустим координаты первого прохода будут в начале строки или могут располагаться в любом месте строки во входных данных?
Parlament
 
Сообщения: 2
Зарегистрирован: 21 фев 2012, 10:12
Полное имя: Давыдов Владимир

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

Сообщение Vladislav_133 21 фев 2012, 19:28

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

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

Сообщение Vladislav_133 21 фев 2012, 19:34

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

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

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

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

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

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

JalbaRu писал(а):Не могли бы Вы подсказать сколько по времени работает ваша программа на тесте вида
za
ab - 10млн раз
zc

На моем компьютере ваш тест работает около 7 сек, из которых чтение секунды 3. Правда я виндовсе сижу, может из за этого


Время работы 0.79с
ответ:
10000001

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

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

Сообщение Vladislav_133 21 фев 2012, 19:45

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

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

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

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

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

Сообщение profi 21 фев 2012, 20:05

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

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

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

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

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

Сообщение JalbaRu 21 фев 2012, 20:36

Vladislav_133 писал(а):Да, когда будем проверять, то посмотрим и на большом. Там ведь указано ограничение по количеству стен и секторов.
Попробуйте для себя такой вариант: 30 стен, тридцать секторов, сквозные проходы до центра (т.е. 900 проходов), преград в коридорах нет, программа должна выдать все варианты. Но я не искал самый большой тест.

Тест вида 30 стен, 4 сектора. В каждой стене один проход, чередуются проходы 1 и 3. Получается что от каждого i-того слоя можно добраться в (i+1)-ый 2 способами. Итого получается 2 в степени 29 решений, то есть почти миллиард. Это далеко не худший случай, вроде бы можно придумать случаи с количеством решений 10^15 и больше. В связи с этим вопрос сколько должна работать программа?
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

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

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

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

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

Vladislav_133 писал(а):Вариант 30 на 30 у меня считает меньше секунды. Я имею в виду, что моя программа выдает не одно, а все 30 в данном случае решений.
Это на виртуальной машине BSD.
Дело в оптимизации.

Не могли бы Вы проверить этот тест

30
4
29 0 28 2 27 0 26 2 25 0 24 2 23 0 22 2 21 0 20 2 19 0 18 2 17 0 16 2 15 0 14 2 13 0 12 2 11 0 10 2 9 0 8 2 7 0 6 2 5 0 4 2 3 0 2 2 1 0
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

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

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

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

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

Vladislav_133 писал(а):Да, этот вариант тяжеловат. Для моего, во всяком случае, алгоритма.
А как у вас?

Свой я еще не дописал, и мой не сможет набрать на 9 баллов. Это тест дает 530 млн решений, в каждой строке около 350 символов. Получается около 170 гигабайт вывода
JalbaRu
 
Сообщения: 14
Зарегистрирован: 19 фев 2011, 18:51
Полное имя: Рунар

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пред.След.

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

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

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