А Вы где-нибудь ведёте доки/схемы/описания игровой механики, извлечённые из уже разобранного кода? Не хочу лезть в чужой монастырь со своим усталым, но, наверное, всем, кто хотел бы помочь, было бы приятно сначала глянуть на какую-нибудь wiki с флоучартом и диаграммами, чтобы была видна системность?
Выше Вы, отвечая на вопрос, указали, что вся реализация математической модели города умещается в одну основную функцию — значит, модель можно визуализировать, а на полученной карте затем отметить «реализовано», «есть расхождения с оригиналом», «не реализовано», и так далее — если у людей появится возможность помогать кодом, тратя меньше времени на «вход в контекст», возможно, число помощников увеличится.
Не хочется занудствовать (ибо автор действительно большой молодец), но по ссылке выше рассказано слегка не про то, как автор дизассемблировал и разгадывал логику игры, больше про то, как там всё рисуется… в связи с чем вопрос:
Логика «клона» действительно повторяет один-в-один логику оригинала? Или выглядит похоже (или идентично), а дьявол — в деталях?
OpenRA, например, тоже выглядит похоже, но это совсем другая игра.
А про процесс извлечения математической модели из дизассемблированного кода я бы тоже почитал с удовольствием.
В любом случае, я свидетельствую респект и уважуху автору. Сам в своё время цезаря гонял за милую душу…
1) сложность О(n²), точное число итераций N*(N+1)/2
for i=1 to n
for k=i to n
-- итерация тут --
2) сложность О(n!):
for a[1]:=1 to n
for a[2]:=a1 to n
...
for a[n]:=a[n-1] to n
-- итерация тут --
Количество for-циклов зависит от n. Вот тогда можно говорить «За факториал». Реализуются такие алгоритмы проще всего рекурсивно. В вашем случае факториал вообще был ни при чём, абсолютно.
Я также понимаю, чем плохо решение через факториал (произведение быстро становится очень большим; разрядная сетка аккумулятора должна быть длиннее разрядной сетки элементов; перемножение очень больших чисел трудно называть операцией О(1)), но если всё же считать умножение целых чисел операцией O(1), то такое решение соответствует требованиям задачи: получение N! за линейное время, один проход по массиву, одна дополнительная переменная.
В решении первой задачи может помочь факториал.
Если известно, что в массиве из N элементов числа из интервала 1..N-1, то действовать можно так:
1) считаем факториал F = N!
2) если F не делится на A[i], повторяющийся элемент найден
3) иначе делим F на A[i] и проверяем следующий элемент.
Я подразумеваю, что N известно заранее, поскольку автор сказал «массив», а не «список».
По поводу лички: если при этом логины видны пользователям, это всё равно, что сказать: «попробуй найди те пять логинов, у которых такой же пароль!».
По поводу сравнения хэша с хэшами плохих паролей: воображаю себе лицо человека, который вбил сумасшедшей сложности пароль, хэш которого
случайно совпал с 12345, и которому сказали, что его пароль слишком простой. Весело, угу)
Угу. Это «числа-градины», про них 3n+1-гипотеза. Ещё вообще неизвестно, для всех ли чисел последовательность вырождается в цикл 4-2-1, если только её вдруг кто-нибудь уже не доказал. разумеется, во всех разумных олимпийских пределах там всё сходится — народ уже обсчитал в том числе и оооочень большие числа.
таблицу, наверное, они подразумевали печатать (не запоминая) — на бумагу или на очень длинный экран.
Да, самое суровое ограничение — это время.
Возможно, тут может помочь (как минимум, самопроверке) вот такое наблюдение: искомое число совпадает с числом «выпуклых» путей на сетке к n-ой диагонали
(«выпуклость» означает «на каждой следующей вертикали взято не больше, чем на предыдущей»), разрыв текущего блока означает переход на следующую вертикаль.
Трижды верно, но не звучит опровержением. Я ни в коем случае не настаиваю, что так всегда и везде, и с каждым таском, и с каждым пользователем.
Единственное, я был некорректен в первом предложении — вывод всё-таки простых делителей.
Не столько сравниваю, сколько просто замечаю, что тогда приходилось держать всю задачу и весь код в голове, а сейчас — есть не только быстрый комп (для задач попроще уже это — решающий фактор), но и отладчик (а вот уже это очень много и «решает» в случае задач посерьёзнее).
Ну и, благодаря инструментарию, появилась возможность ставить и решать задачки потяжелее. В голове-то, наверное, что-нибудь из динамического программирования тяжко было бы держать целиком…
Ну, положим, вывод всех делителей с учётом кратности тут виден довольно прозрачно. Когда бы они знали про то, что спустя 20 лет будет представлять собой минифицированный javascript…
Ну, или тот же ioccc, где сокрытие смысла возведено в ранг искусства.
Однако да, с тем, что условия у них были суровы, не поспоришь.
Тогда: без доступа к компьютеру решай задачку за олимпиадные часы.
Сейчас: google, stackoverflow, google, msdn, пишем, ух ты, codeproject!……… итого в ютреке таск закрыт за 8 часов. Совершенно необязательно, что алгоритмически более сложный (а то и вообще не более сложный).
с флоучартом и диаграммами, чтобы была видна системность?Выше Вы, отвечая на вопрос, указали, что вся реализация математической модели города умещается в одну основную функцию — значит, модель можно визуализировать, а на полученной карте затем отметить «реализовано», «есть расхождения с оригиналом», «не реализовано», и так далее — если у людей появится возможность помогать кодом, тратя меньше времени на «вход в контекст», возможно, число помощников увеличится.
Логика «клона» действительно повторяет один-в-один логику оригинала? Или выглядит похоже (или идентично), а дьявол — в деталях?
OpenRA, например, тоже выглядит похоже, но это совсем другая игра.
А про процесс извлечения математической модели из дизассемблированного кода я бы тоже почитал с удовольствием.
В любом случае, я свидетельствую респект и уважуху автору. Сам в своё время цезаря гонял за милую душу…
Ещё раз, прочувствуйте разницу:
1) сложность О(n²), точное число итераций N*(N+1)/2
2) сложность О(n!):
Количество for-циклов зависит от n. Вот тогда можно говорить «За факториал». Реализуются такие алгоритмы проще всего рекурсивно. В вашем случае факториал вообще был ни при чём, абсолютно.
1) где тут факториал в приведённом коде?
2) в задаче просили O(n), в коде вижу O(n²)…
… Суть задачи ухвачена верно.
Если известно, что в массиве из N элементов числа из интервала 1..N-1, то действовать можно так:
1) считаем факториал F = N!
2) если F не делится на A[i], повторяющийся элемент найден
3) иначе делим F на A[i] и проверяем следующий элемент.
Я подразумеваю, что N известно заранее, поскольку автор сказал «массив», а не «список».
По поводу сравнения хэша с хэшами плохих паролей: воображаю себе лицо человека, который вбил сумасшедшей сложности пароль, хэш которого
случайно совпал с 12345, и которому сказали, что его пароль слишком простой. Весело, угу)
Да, самое суровое ограничение — это время.
Возможно, тут может помочь (как минимум, самопроверке) вот такое наблюдение: искомое число совпадает с числом «выпуклых» путей на сетке к n-ой диагонали
(«выпуклость» означает «на каждой следующей вертикали взято не больше, чем на предыдущей»), разрыв текущего блока означает переход на следующую вертикаль.
Единственное, я был некорректен в первом предложении — вывод всё-таки простых делителей.
Ну и, благодаря инструментарию, появилась возможность ставить и решать задачки потяжелее. В голове-то, наверное, что-нибудь из динамического программирования тяжко было бы держать целиком…
Ну, или тот же ioccc, где сокрытие смысла возведено в ранг искусства.
Однако да, с тем, что условия у них были суровы, не поспоришь.
Тогда: без доступа к компьютеру решай задачку за олимпиадные часы.
Сейчас: google, stackoverflow, google, msdn, пишем, ух ты, codeproject!……… итого в ютреке таск закрыт за 8 часов. Совершенно необязательно, что алгоритмически более сложный (а то и вообще не более сложный).