| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача: балансировка камней. |
| Автор: qwertynho 8.3.2009, 23:00 |
| Балансировка камней. Вам даны рычажные весы. На левой чаше весов лежит один камень с весом W<2N. У вас есть свое множество камней: 1, 2, 4, … , 2N-1. Определите сколькими способами можно расположить некоторые из этих камней на чашах весов так, чтобы уравновесить их. Выведите это значение по модулю D. Входные данные (input.txt): В первой строке записаны три числа: N, L, D. (1<=L<=N<=1000000, 1<=D<=100). Далее во второй строке ровно L символов – двоичная запись числа W. Выходные данные (output.txt): Единственное число – количество способов, взятое по модулю D. Примеры: Input.txt 6 4 6 1000 Output.txt 3 Input.txt 6 6 100 100110 Output.txt 5 Ссылка: acm-test.bsu.by -> Задания -> Теория алгоритмов -> Рекуррентные , только вы не сможете зайти без регистрации. См. исходник, прикреплённый к сообщению. Как можно ускорить процесс? В системе acm-test проходит один тест из 14, на остальные пишет либо ошибка времени выполнения, либо нарушен предел времени. Добавлено через 2 минуты и 47 секунд Вот исходник. Добавлено через 6 минут и 11 секунд Имеется в виду 2 в степени N, а не 2*N. Всё степени, не умножение. |
| Автор: maxdiver 9.3.2009, 00:31 |
| Не читал вашего решения, но вроде можно решить простой линейной динамикой D[L][2], которую можно назвать и рекуррентной формулой. |
| Автор: maxdiver 9.3.2009, 15:11 |
| Только как там субмитить? Что, просто так зарегаться и открыть нельзя? |
| Автор: qwertynho 9.3.2009, 17:41 |
| В общем, там на acm-test система "логин - номер зачётки; пароль", она по номеру смотрит, какая группа, и открывает только текущее задание. Без номера, соответственно, ничего не откроется, это я просёк уже после того, как дал ссылку. Спасибо за совет, я не волшебник, я только учусь ))) Попробую, скажу, что получится! |
| Автор: maxdiver 9.3.2009, 17:56 |
| Что ж, тогда я своё решение не проверю никак. На ручных тестах работает, с идеей вроде всё в порядке, но здесь я, конечно, выкладывать решение не буду. В длинной арифметике в моём решении вообще нет нужды, так что вы, скорее всего, зашли не в ту сторону. Лучше попытаться понять, как и почему ответ изменяется, когда к числу слева дописывается единичка или нолик, отсюда и получаются довольно простые формулы. |
| Автор: qwertynho 9.3.2009, 18:43 |
| Супер! Сейчас скинул решение, 13 из 14 тестов прошли! В 14ом нарушен предел времени, надо чуть-чуть посмотреть, где и почему это могло произойти. Вы правы, меня понесло совсем не туда, в рекурсию, а не в динамическое программирование. Помнится, задачу решал, людей через мост надо было переводить, каждый со своей скоростью, одновременно через мост могут идти только двое, дело происходит ночью, а фонарик один. Так там было что-то около ста тысяч человек, естественно, что рекурсия шла лесом. А потом нашёл рекуррентное соотношение, и всё стало очень быстро происходить! А тут сходу тормознул. Правда, писать начал только вчера. С такими темпами сегодня хочется закончить. Ещё раз спасибо! |