Как видно на скриншоте, в системе установлено девелоперское окружение Ultra 64 размером 1 ГБ.
В видео на Youtube автор находки говорит, что 1.0G — это номер версии. В принципе, если бы это была емкость, то было бы написано, вероятно, «GB» или «Gb» (просто предположение).
Кстати, сталкивался ли кто с такой ситуацией, что ICQ (официальный клиент) всегда показывает, что пользователь находится в сети даже при выключенном компьютере? Если зайти через веб-интерфейс ICQ, то видно, что сессия открыта. То есть, фактически не закрывается сессия. Пробовал устаналивать Pidgin на тот же комп — та же проблема.
Черт, уже не помню, что там на 20-ом было (23-ий уровень уже весь мозг выел =). Напомните мне, плиз, что там на 20-ом за вопрос был, и я попробую намекнуть.
В 20-ой задаче понравилось, что по задумке автора кнопки не должны бы дизейблится на определенном урле 'http://puzzle.mail.ru/[censored]', но про вводе его в адресную строку выполняется автоматический редирект на https://<то же самое>, и кнопки все равно блокируются ))
В общем, тупо отредактировал оба свойства руками в «Инструментах веб-разработки», чтобы отправить ответ )
Тоже так думал, а потом понял, что при «9» выполняется заход в цикл, а там сначала идет увеличение X на 1, то есть, X становится равным '10', а потом умножение на эту 10-ку. То есть, ошибки нет.
Честно говоря, не совсем понял, откуда вы взяли все эти цифры, в частности 2000 точек и связанные с ними 0.1%. Ну ладно, не суть. Давайте по-простому. У нас есть массив из 80 точек (цифра взята просто для удобства последующего деления). В нем есть некоторая последовательность из 20 одинаковых элементов. Предположим, мы решили взять шаг разбиения в 10 элементов. Таким образом, наш массив поделен на 8 равных частей, каждая часть состоит из 10 точек. Мы перебираем пары соседних точек и смотрим, чтобы элементы массива в них имели одинаковые значения, а соседние с ними элементы были не равны им. Найдя такую пару точек мы можем предположить, что в этом месте расположена последовательность нужной нам длины. Искать реальные концы последовательности мы не можем, так как в этом случае будет нарушено требование «константной» временной сложности. Фактически же длина найденной нами последовательности может быть в дианазоне от 10 до 30 точек (то есть, от N/8 до 3N/8). И вероятность нашего «угадывания» составляет 1/20 (1 вариант из 20 возможных) или 5%.
Конечно, мы можем разделить массив с шагом не 10, а, например, 5, получая не 8, а 16 точек разбиения. В этом случае, вероятность угадывания составит уже 10%. Таким образом, увеличивая количество точек разбиения мы повышаем вероятность правильного ответа. Но в этом случае, как я уже писал ранее, наш алгоритм приобретает все более «линейную» сложность., так как для получения требуемой вероятности правильного ответа нам нужно будет постоянно увеличивать количество точек разбиения при увеличении количества элементов входного массива.
Ну и по поводу «плохих» данных. Разумеется, во входном массиве могут быть как N/4+1, так и N/4-1, N/4-2 и прочие последовательности указанных длин. В общем, любые последовательности длины от N/8 до 3N/8 включительно. Ничего противоестественного в таких наборах нет и говорить об исключительности этой ситуации весьма странно, на мой взгляд.
Кстати, буду признателен, если вы приведете алгоритм, который в 99.9% будет иметь «константное» решение для случая, когда заранее известно, что некоторый элемент точно присутствует в массиве и встречается там N/4 раз. Просто почему я сомневаюсь в этом. Для того, чтобы алгоритм обеспечивал чаще константное решение, необходимо после разбиения на фиксированное кол-во точек и поиске цепочки подходящей длины, проверять только соседние точки (без переборов и двоичных поисков). Повысить вероятность этого можно только увеличением кол-ва точек разбиения (вырожденный случай, дающий 100% вероятность — когда количество точек разбиения равно размерности самого массива). В этом случае вероятность выше, но тогда нельзя сказать, что алгоритм «константен», потому как с увеличением размерности массива придется всегда увеличивать кол-во точек разбиения для получения высокой вероятности. А если число точек разбиения не увеличивать, то, соответствнно, и вероятность будет значительно ниже. Но я подожду вашего решения.
=) Даже если есть хоть 1 возможный вариант из миллиарда, когда алгоритм будет работать не по «константной» схеме, значит, он «неконстантный». Потому что ты не можешь гарантировать константное время его работы для любых произвольных данных. Это как если бы ты в произвольном алгоритме сортировки сначала всегда проверял все пары соседних элементов, а не находится ли входной массив уже в отсортированном порядке. Такие случаи вполне могут быть. Но это не значит, что сложность алгоритма сортировки станет считаться как O(N), верно?
===
Найти число которое повторяется N/4 (где N это размер массива) раз.
===
Да, нет слова «РОВНО», но, по-моему, оно тут и не нужно, так как и без него условие очевидно.
Вы не могли бы описать суть «константного» алгоритма, если массив состоит исключительно из цифр от 0 до 9? Я надеюсь, это будет интересно не только мне.
Если я правильно понимаю, данный алгоритм находит действительно одну последовательность, но не может гарантировать, что ее длина равна ровно N/4 элементов. Безусловно, мы можем дополнить условие задачи тем, что у нас имеется только один элемент в массиве, для которого выполняется условие, что он встречается от N/8 до 3N/8 раз, и других таких элементов в массиве нет. В этом случае согласен с вашим решением.
То есть, мы разбиваем массив на 8 равных частей и смотрим, есть ли в парах соседних точек одинаковые элементы (и при этом следующие граничные точки не содержат это же значение)? Но при этом, если я правильно понимаю, мы можем только гарантировать, что найденная последовательность имеет длину >= N/8, но не можем гарантировать, что в найденной последовательности ровно N/4 чисел.
Возможно, я в чем-то ошибаюсь.
И даже если рассмотреть случай, когда точек разбиения можно взять больше (миллион! :), то, с одной стороны, это все равно только повышает вероятность нахождения правильного решения, а с другой стороны такая зависимость количества точек разбиения от возможной длины массива уже не может рассматриваться как решение с константной сложностью. То есть, грубо говоря, на каждый вариант разбиения на N точек можно найти массив с кол-вом элементов >= 8 * N.
ps. =)
В видео на Youtube автор находки говорит, что 1.0G — это номер версии. В принципе, если бы это была емкость, то было бы написано, вероятно, «GB» или «Gb» (просто предположение).
В общем, тупо отредактировал оба свойства руками в «Инструментах веб-разработки», чтобы отправить ответ )
Конечно, мы можем разделить массив с шагом не 10, а, например, 5, получая не 8, а 16 точек разбиения. В этом случае, вероятность угадывания составит уже 10%. Таким образом, увеличивая количество точек разбиения мы повышаем вероятность правильного ответа. Но в этом случае, как я уже писал ранее, наш алгоритм приобретает все более «линейную» сложность., так как для получения требуемой вероятности правильного ответа нам нужно будет постоянно увеличивать количество точек разбиения при увеличении количества элементов входного массива.
Ну и по поводу «плохих» данных. Разумеется, во входном массиве могут быть как N/4+1, так и N/4-1, N/4-2 и прочие последовательности указанных длин. В общем, любые последовательности длины от N/8 до 3N/8 включительно. Ничего противоестественного в таких наборах нет и говорить об исключительности этой ситуации весьма странно, на мой взгляд.
Найти число которое повторяется N/4 (где N это размер массива) раз.
===
Да, нет слова «РОВНО», но, по-моему, оно тут и не нужно, так как и без него условие очевидно.
Возможно, я в чем-то ошибаюсь.
И даже если рассмотреть случай, когда точек разбиения можно взять больше (миллион! :), то, с одной стороны, это все равно только повышает вероятность нахождения правильного решения, а с другой стороны такая зависимость количества точек разбиения от возможной длины массива уже не может рассматриваться как решение с константной сложностью. То есть, грубо говоря, на каждый вариант разбиения на N точек можно найти массив с кол-вом элементов >= 8 * N.