Аля Сапёр, олимпиадная задача |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Аля Сапёр, олимпиадная задача |
hardcase |
Сообщение
#1
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Вот задача про "Минное поле чудес" (постил Я) брутальная задачка
Меня интересует просто алгоритм. Честно говоря я не представляю, как её можно сделать. Конечно, сперва надо действовать как в игре Сапёр - с этим проблем нету. Проблема - как потом считать вероятности? Сообщение отредактировано: hardcase - -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение..
Вот тут я решал задачу про расстановку мин, но правда не в прямоугольнике, а линейную (причем, по требованию клиента, решил двумя способами..). Думаю, переделать в двумерный вариант не очень сложно. Далее, по мере просмотра вариантов нужно просто считать количество мин для каждой клетке. Поясняю. Сначала заводим массив целых чисел размером с поле. Когда найден очередной вариант расстановки, инкрементим те клетки этого массива, где в найденном варианте стоят мины. В конце получим массив, показывающий суммарное число появлений мин в каждой клетке. Осталось поделить эти числа на количество вариантов - все вероятность готова, извольте кушать! Только не забудьте разложить по риал-тарелкам.. Беда только в том, что задача либо довольно долго считается (для нормальных размеров, типа 20) - так как прибавление одного поля даже в линейном варианте удваивает (кажется) количество вычислений, либо жрет памяти немеряно (мой гигабайт ушел играючи на длину массива, кажется, меньше 30). Короче, не все так просто.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
klem4 |
Сообщение
#3
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Цитата мой гигабайт ушел играючи на длину массива, кажется, меньше 30 Извиняюсь за серость, это об оперативной памяти речь идет ? -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
hardcase |
Сообщение
#4
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Ага, я подозревал, что задача про расстановки мин появилась неспроста! Вот и продолжение.. Короче идея мне ясна. Брутфорс расстановок.... Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20... Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми. Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ. Сообщение отредактировано: hardcase - -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
Lapp |
Сообщение
#5
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Извиняюсь за серость, это об оперативной памяти речь идет ? О ней, родимой. Динамическое программирование (ДП) заключается в том, что ты запоминаешь промежуточные результаты, которые не нужны собственно для окончательно ответа, но потребуются при продолжении расчетов. Поскольку надобятся они в произвольном порядке, то класть это в файл на диск нельзя. Но это ускоряет вычисления (пока хватает памяти). Простейший пример: допустим, тебе в расчетах нужен факториал. Ты пишешь функцию с обычным перемножением чисел. Сначала тебе нужен 20!, потом 15!, потом типа 30! ... Можно все вычислять честно, но тогда на каждом вычислении нужно производить все умножения. А можно иначе: вычислил, скажем, 20! - и запомнил.. Потом, когда понадобился 30! - вынул и домножил на десять чисел. И тоже запомнил - пригодится, когда будет вычисляться типа 33! Это, конечно, очень простой пример.. Брутфорс расстановок.... Но сдаётся мне можно и без полного перечисления. Правда, в условии сказано, что максимальный размер поля 20х20... Мне так не сдается. Условия слишком специфические, никаких общих принципов тут не присобачишь. Подумай, конечно - может, я что упустил.. Но, судя по тому, что она давалась setare как объект для ДП, я все же прав.. Можно пробовать выделять области, в которых вероятности нахождения мин равны - тогда задачка немного упрощается и брутфорсить надо только в местах, где открытые области соприкасаются с закрытыми. Перебор есть перебор, и перебирать надо все. Там все слишком завязано на нижнем уровне, оптимизировать не получается (у меня). Для того, чтобы в этом убедиться (или меня разубедить), нужно поиграть с условиями в уме. Кстати про гигабайты - там было ограничение на количество памяти, кажется 64МБ. Значит, решать нужно без ДП. Но 20х20 - терпимо. На моей машинке (двойной Athlon MP 2200+) этот размер пролетал за секунды. Введение двумерности усложнит расчет раза в три-четыре (не больше порядка, это точно) на каждой строке, да умножить на кол-во строк.. Короче, вполне терпимо еще, на ночь оставлять не потребуется Задачка действительно неплохая, респект! -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
hardcase |
Сообщение
#6
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
У меня ещё есть.
С контестов в CBOSS =) У меня тут под монитором есть целый склад таких задач (кипа бумаг) - половина решена, правда файлы *.pas утеряны... -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
klem4 |
Сообщение
#7
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
hardcase, а отсканить и залить есть возможность ?
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
hardcase |
Сообщение
#8
|
code warrior Группа: Пользователи Сообщений: 484 Пол: Мужской Реальное имя: Славен Репутация: 8 |
Отсканить возможность есть - сканер и OCR имеюЦа. Дело в том, что где-то были pdf-эквиваленты, но я не знаю, где. А так могу десяток-другой пропостить.
Кстит часть задач на инглише формулируется - они с международных турниров по программированию. Сообщение отредактировано: hardcase - -------------------- ИзВ ин ИтЕ зА нЕ рОв НЫй П оч ЕРк
|
volvo |
Сообщение
#9
|
Гость |
Сюда ходим:
CBOSS Open Cup - раздел "Задачи", открывается PDF с задачками... |
klem4 |
Сообщение
#10
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Спасибо
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Текстовая версия | 4.05.2024 21:14 |