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

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

СообщениеДобавлено: 21 фев 2012, 18:25
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

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

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

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

СообщениеДобавлено: 21 фев 2012, 18:50
xdsl
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

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

СообщениеДобавлено: 21 фев 2012, 19:22
Vladislav_133
Третья задача. Координаты и проходов и перегородок в строке стоят хаотично. Да и какой порядок можно здесь установить.

Прикрепляю тесты к третьей задаче. Прошу прощения, у меня не input.txt и output.txt, а input и output. Сейчас обратил на это внимание.
Но я думаю, что это не проблема. Всего 18 тестов. Тесты содержат варианты с выдачей всех возможных путей.

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

СообщениеДобавлено: 21 фев 2012, 19:23
JalbaRu
Не могли бы Вы подсказать сколько по времени работает ваша программа на тесте вида
za
ab - 10млн раз
zc

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

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

СообщениеДобавлено: 21 фев 2012, 19:25
Vladislav_133
Еще по поводу третьей задачи. Программа может выбрать любой предпочтительный вариант нахождения правильного пути.
Вы получите 8 очков, если ваша программа будет выдавать один любой но самый короткий путь. 9 - за все самые короткие пути.

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

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


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

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

СообщениеДобавлено: 21 фев 2012, 19:28
Vladislav_133
Parlement - любой порядок.

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

СообщениеДобавлено: 21 фев 2012, 19:34
Vladislav_133
Что касается внешних проходов, то их может быть несколько и даже совпадать с числом секторов.

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

СообщениеДобавлено: 21 фев 2012, 19:36
xdsl
Владислав Юрьевич, как-же вы тесты-то выдали до окончания олимпиады!? Или это примерные тесты, а проверять на других будете?

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

СообщениеДобавлено: 21 фев 2012, 19:44
xdsl
JalbaRu писал(а):Не могли бы Вы подсказать сколько по времени работает ваша программа на тесте вида
za
ab - 10млн раз
zc

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


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

cz
ab

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

СообщениеДобавлено: 21 фев 2012, 19:45
Vladislav_133
Да это просто у меня часть тестов. У меня по этой задаче уже штук 40. В этом смысле я спокоен.

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

СообщениеДобавлено: 21 фев 2012, 19:53
xdsl
to JalbaRu: сейчас скомпилировал свое решение первой задачи под виндовс в virtualbox и запустил на этом-же тесте. Время работы - порядка 3 секунд, большая часть - на чтение с виртуального диска. Понятно, что на реальной виндовой машине то-же будет меньше секунды. Так-что ищите методы оптимизации алгоритма.

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

СообщениеДобавлено: 21 фев 2012, 20:05
profi
Владислав Юрьевич вы можете выложить самый большой тест на задачу 4(конечно же не на котором будет проверка в конце олимпиады :) ). Хочу проверить скорость работы.

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

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

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

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

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

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

СообщениеДобавлено: 21 фев 2012, 21:00
Vladislav_133
Вариант 30 на 30 у меня считает меньше секунды. Я имею в виду, что моя программа выдает не одно, а все 30 в данном случае решений.
Это на виртуальной машине BSD.
Дело в оптимизации.

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

СообщениеДобавлено: 21 фев 2012, 21:08
JalbaRu
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

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

СообщениеДобавлено: 21 фев 2012, 21:22
Vladislav_133
Да, этот вариант тяжеловат. Для моего, во всяком случае, алгоритма.
А как у вас?

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

СообщениеДобавлено: 21 фев 2012, 21:28
JalbaRu
Vladislav_133 писал(а):Да, этот вариант тяжеловат. Для моего, во всяком случае, алгоритма.
А как у вас?

Свой я еще не дописал, и мой не сможет набрать на 9 баллов. Это тест дает 530 млн решений, в каждой строке около 350 символов. Получается около 170 гигабайт вывода

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

СообщениеДобавлено: 21 фев 2012, 21:28
profi
Владислав Юрьевич вы можете выложить самый большой тест на задачу 4 (конечно же не на котором будет проверка в конце олимпиады :) ). Хочу проверить скорость работы.

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

СообщениеДобавлено: 21 фев 2012, 21:31
Vladislav_133
По четвертой задаче как бы не вижу проблему в скорости. Там нет рекурсии, перебора не много. Но в конце тесты будут, конечно.

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

СообщениеДобавлено: 21 фев 2012, 21:39
Vladislav_133
JalbaRu, проверяться программа будет по моим тестам. Ваш тест и моя программа будет считать также долго.
Так что решайте смело. Такие ситуации у нас бывают. Можно уменьшить количество стен, например, но я хотел бы оставить вариант 30*30 (30 проходов каждой стене), поскольку он требует дополнительной оптимизации и вполне решаем.

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

СообщениеДобавлено: 21 фев 2012, 22:13
Vladislav_133
3-я задача.
Поразмышляв над проблемой, я думаю можно остановиться на 16 кругах.
Тогда не возникнет ситуации, что какие то тесты программа не может пройти в силу "жадности" алгоритма.

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

СообщениеДобавлено: 21 фев 2012, 22:16
Vladislav_133
Так, время позднее. Давайте определимся, со временем. Буду еще около часа на связи. Потом иду спать.