До чего техника дошла… Мы в одиннадцатом классе просто считали расстояние от центра масс до самой близкой и самой удаленной точки на границе, а потом смотрели на их отношение. Если близко к 1, то круг. Если в районе корня из двух, то квадрат. Если больше, то треугольник. И ничего, AC.
Gcd можно искать через двоичного Евклида. Это O(L^2).
А так, конечно, есть. Например, метод касательных (Newton-Raphson method). Мне кажется, он работает за O(\log L M(L)), где M(L) — время умножения двух чисел.
Я, конечно, понимаю, что здесь собрался кружок по спортивному программированию, но, блин, укажите нормальную асимптотику в заголовке.
AKS проверяет числа за O(L^{6 + eps}), Рабин-Миллера и Ферма можно написать за O(k * L^2 \log L), где L — длина числа.
Вы же не будете составлять RSA-ключ из чисел, влезающих в long long?
Эта программа и правильная, и нет. Нельзя говорить, что программа содержит ошибку, пока нет всех условий. Нужно указывать предусловия, постусловия и инварианты. Иначе кто угодно может придраться. А вдруг массив не отсортирован? А вдруг его длина больше int-а (long-а)? А что будет, если ключа не найдется или их много?
Насколько я вижу, вся соль шестой строки не в переполнении, а в том, что вычисления остаются в пределах размера массива.
Мне кажется, вы слишком полагаетесь на красивые лозунги, но это не повод обижаться на людей. Хотите от них честности, делайте грамотные экономические механизмы. На русскую сознательность полагаться не стоит.
И еще, вопросы не совсем правильные. Обычно правило типа «нельзя» исправно работает до первого безнаказанного нарушения. Здесь же людей стимулировали к первому нарушению. Так что в опроснике нужны предыстории, когда вы уже хотя бы один раз поступили нехорошо.
Предыдущий комментарий был по поводу исходника.
Формулу использовать можно, но если генерировать большие последовательности, хочется избежать проблем с переполнением стека. Поэтому я развернул рекурсию.
Нет, равномерно так не получится. Возьмем n = 3. После первого запуска скобки могут быть трех типов ()****: 2 штуки. (**)**: 1 штука. (****): 2 штуки.
Каждый из типов выбирается с равной вероятностью. Нехорошо.
Да, все это нужно для анализа. Мы хотим построить взаимно-однозначное отображение между всеми сбалансированными скобками с дефектом k и правильными. Чтобы показать, что отображение взаимо-однозначное, нужно показать его обратимость.
В конечном итоге, мы как бы хотим раскидать все сбаласированные скобки по правильным, и чтобы получилось равномерно.
А так, конечно, есть. Например, метод касательных (Newton-Raphson method). Мне кажется, он работает за O(\log L M(L)), где M(L) — время умножения двух чисел.
AKS проверяет числа за O(L^{6 + eps}), Рабин-Миллера и Ферма можно написать за O(k * L^2 \log L), где L — длина числа.
Вы же не будете составлять RSA-ключ из чисел, влезающих в long long?
Насколько я вижу, вся соль шестой строки не в переполнении, а в том, что вычисления остаются в пределах размера массива.
И еще, вопросы не совсем правильные. Обычно правило типа «нельзя» исправно работает до первого безнаказанного нарушения. Здесь же людей стимулировали к первому нарушению. Так что в опроснике нужны предыстории, когда вы уже хотя бы один раз поступили нехорошо.
pastebin.com/t4CDF91v
Формулу использовать можно, но если генерировать большие последовательности, хочется избежать проблем с переполнением стека. Поэтому я развернул рекурсию.
()****: 2 штуки.(**)**: 1 штука.(****): 2 штуки.Каждый из типов выбирается с равной вероятностью. Нехорошо.
Да, все это нужно для анализа. Мы хотим построить взаимно-однозначное отображение между всеми сбалансированными скобками с дефектом k и правильными. Чтобы показать, что отображение взаимо-однозначное, нужно показать его обратимость.
В конечном итоге, мы как бы хотим раскидать все сбаласированные скобки по правильным, и чтобы получилось равномерно.