Wataru

Тут не нужно решето. Надо просто отдельно проверить каждое число на простоту.

Подсказка: Если число не простое, то у него есть простой делитель не больше корня (потому что иначе - есть хотя бы 2 делителя и они оба больше корня и их произведение уже больше самого числа).

Вам надо арктангенс брать от отношения, а не тангенс (y2-y1) / (x2-x1).

Это называется интерполяция. Вы знаете, что f(a) = 10, f(b)=5. Вам надо найти f(c), при чем f должна попадать под здравый смысл (монтонная, непрерывная функция).

например, можно взять линейную инерполяцию, тогда f(x) = 10-(x-a)/(b-a)*5.

Работает медленно, потому что вы обрезаете входной массив каждый раз. Для этого приходится обходить и копировать всю нужную часть. Поэтому суммарное время работы будет O(n).

Чтобы работало быстро вам надо не менять lst, а помнить индексы границ текущего куска.

Ещё, вам надо останавливаться, когда рассматриваемый кусок станет пустым, чтобы решение не вылетало, если искомого числа в списке нет.

И последнее, в питоне есть операция целочисленного деления - //. Используйте ее вместо приведения к int после деления.

Заведите массив из нулей. Для каждого отрезка сделайте +1 в координату его левого конца и -1 в координату, следующую за правым концом.

Потом пройдитесь по массиву слева-направо, поддерживая счетчик. Прибавляйте к счетчику значение массива и выводите значение счетчика.

Это если вам надо весь массив, как в примере, выводить. Не знаю специфику вашей задачи, может эффективнее будет класть в массив пары {координата, +-1} и сортировать. Потом точно также обойти слева направо поддерживая счетчик.

Генерируются они так:

Есть у вас список уже сгенеренных чисел, изначально содержит только 1.

Вы добавляете в список сделющее число, пока не наберете необходимое количество.

Поддерживайте 3 указателя (изначально на первое число), которые указывают на первые неиспользованные числа для домножения на 2, 3 и 5.

Каждый раз берете и сморите что лучше - взять число из первого указателя, домножить на 2, взять число из второго домноженное на 3 или из последнего указателя и домножить на 5. Кладете это число в список и сдвигаете указатель.

Пример:
шаг 1.
указатели: 1, 1, 1
список: {1}
варианты:1*2, 1*3, 1*5. Лучший - 2.

шаг 2.
указатели: 2, 1, 1
список: {1, 2}
варианты:2*2, 1*3, 1*5. Лучший - 3.

шаг 3.
указатели: 2, 2, 1
список: {1, 2, 3}
варианты:2*2, 2*3, 1*5. Лучший - 4.

шаг 4.
указатели: 3, 2, 1
список: {1, 2, 3, 4}
варианты: 3*2, 2*3, 1*5. Лучший - 5.

Есть неалгоритмический способ ускорить ваше решение - храните в каждой ячейке массива не одну цифру - а несколько. Фактически, проводите вычисления в системе счисления 10000, вместо 10. Или даже 1000000000 - но тогда надо временные вычисления (умножение) делать в int64_t, чтобы переполнения не было.

Еше, при выводе такого числа надо выводить ведущие нули для всех ячеек, кроме самой старшей.

Есть и алгоритмический способ - но он сложнее. Есть алгоритм бинарного возведения в степень. Суть в том, что вы возводите число в квадрат и домножаете на базу если надо.

Но в таком виде алгоритм будет даже медленнее на больших числах. Ему потребуется O(log K) умножений большого на большое (которое делается за O(L^2), где L - длина числа, которая будет O(K)). Итоговая сложность этого алгорима будет O(K^2 log K).

Когда как ваше текущее решение делает K коротких умножений (Каждое - O(K)) - всего O(k^2) операций. Но если применять быстрое умножение длинных чисел через быстрое преобразование Фурье то итоговая сложность будет O(K log^2 K log log K). Для power=100 особо вы разницы не почуствуете, даже медленнее будет, но вот при каких-нибудь 10000 уже будет заметно быстрее.

Советую попробовать обычные оптимизации, прежде чем браться за преобразование фурье.

Еще, вместо хранения конца числа в виде особого значения 10 - вам стоит отдельно хранить длину числа в какой-то переменной с говорящим названием (хотя бы len). Тогда код будет сильно читабельнее.

Это задача о многомерном рюкзаке (multi-dimensional knapsack). Каких-то простых трюков, как с обычным одномерным рюкзаком тут нет. Только перебор с отсечениями.

Еще можно свести задачу к целочисленному линейному программированию. Вводите переменные - сколько штук каждого пункта съели, составляете линейные уравнения. Потом можно это все скормить какому-нибудь решателю. Сейчас много библиотек и они довольно быстро такие задачи щелкают. Гуглите "integer linear programming solver".

Вы наткнулись на важное свойство ассимптотического анализа. O(n^2) -означает, что на достаточно больших n, время работы будет примерно n^2 с точностью до константы. Эта самая константа может быть хоть 0.5, хоть 10000000.

Сравните 2 алгоритма:

// n(n-1)/2 инкремента.
for(i = 0; i < n; ++i){
  for (j = i+1; j < n; j++) {
    cnt1++;
  }
}
// n^2 инкремента.
for(i = 0; i < n; ++i){
  for (j =0; j < n; j++) {
    cnt2++;
  }
}

Оба алгоритма имеют O(n^2) сложность, но один делает примерно в 2 раза меньше операций.

Суть в том, что хоть алгоритмы и работают с одинаковой ассимптотикой, они могут работать разное время! Особые странности могут быть при маленьких n. O(n log n) алгоритм часто может быть медленнее O(n^2) алгоритма. Поэтому все настоящие реализации сортировок для маленьких массивов запускают более тупые квадратичные алгоритмы.

Если же вы хотите показать только ассимптотику, то возьмите n побольше, и тогда эти 30% будут незаметны по сравнению с десятикратным замедлением O(n^2) относительно O(n log n). Или нормируйте ваши сортировки. Искуственно ускорьте одни алгоритмы и замедлите другие, чтобы получить именно тот результат, который вы хотите. Но это как-то нечестно что ли. Если же вы все-таки хотите именно этого, назначьте каждой сортировке время C\*n^2 или С\*n\*log n миллисекунд. Прогоните алгоритмы сортировки без визуализации, подсчитайте, сколько операций замедления вы бы сделали (тот же самый код, что у вас, только вместо usleep() делайте sleep_count++). В конце подсчитайте коэффициент замедления - сколько каждый usleep должен спать, чтобы суммарно sleep_count их спал заданное время. И запускайте каждую сортировку уже с подсчитанными параметрами для usleep.

Еще есть вариант (если у вас все слова разные) - подсчитайте сколько раз каждая длина встречается в наборе.

Если вы видите, что у вас однобуквенных слов меньше, чем букв в алфавите - то можно выдать однобуквенное слово. Иначе, если двух-буквенных слов меньше |alphabet|^2, то можно выдать двубуквенное слово. И так далее. Вот нашли вы минимальную длину.

Чтобы найти и само слово, заведите битмап размером со сколько у вас слов. Потом пройдитесь по словам и если слово нужной длины, поставьте 1 в битмапе с номером равным строке, если ее интерпретировать как число в |alphabet|-ой системе счисления (самый младший символ равен цифре 0). Если число переваливает за размер битмапы, то можно текущую строку проигнорировать. Потом найдите любой 0 бит в битмапе. Его номер переведите назад в |alphabet| систему счисления.

Пример. Алфавит - {a,b}. Слова: "a", "b", "aa", "ab", "bb".

Мы видим 2 однобуквенных слова. Никак. 3 двухбуквенных, но 3 < 2^2 - значит можно выдать двубуквенную строку.

У нас 2 символа в алфавите, интерпретируем a=0, b=1. "aa" = 0, "ab" = 1, "bb" =3. В битмапе останется пустым индекс 2. Это 10 в двоичной системе или "ba" в строках - это и есть ответ. Да еще и лексикографически минимальный.

Если слова могут повторятся, то можно чуть изменить решение: точно также перенумеруйте все возможные слова в вашем алфавите. Сначала будут однобуквенные, потом двубуквенные и т.д. При переводе строки в индекс - также переводите из |alphabet|-ичной системы счисления. Но для слова из l символов прибавляйте смещение |alphabet|^(l-1)+|alphabet|^(l-2)+... |alphabet|^1. Точно так же, если в процессе вычисления видно, что индекс не поместится в битмапу (больше количества строк), то можно забить на эту строку. Поэтому же можно сразу пропускать слишком длинные слова.

Опять же, помечайте бит в битмапе. Потом найдите первый нулевой бит. И назад преобразуйте в строку - сначала найдите смещение (суммируйте степени |alphabet|, пока они не перевалят за текущий индекс). Так вы поймете, сколько символов у вас в строке. Вычтите смещение и переводите индекс в |alphabet|-ичную систему счисления.

Этот вариант в среднем может работать чуть дольше, но все так же очень быстро.

Еще, оба эти варианта самые экономные по памяти.

Куча ошибок. Вы читаете запросы в массив B и больше нигде не используете. Конструкция A{m<i] вообще удивительна. Массив надо отсортировать.

У вас простой DFS. Если ему не повезет пойти не по отрицательному циклу, но при этом обойти какие-то его вершины, то вы запорите перебор и этот цикл никогда не найдется.

Чтобы через DFS найти отрицательный цикл - придется перебирать ВСЕ циклы. Для этого надо не помечать вершины как visited. Правда, работать будет очень медленно и почти гарантированно не пройдет по time limit, ибо циклов в гарфе может быть экспоненциально много.

Edit, вот вам пример. В графе только один отрицательный цикл 1->2->3->1. Но есть еще ребро 1->3. Если вы начнете из 1-ой вершины, потом возьмете ребро 1->3, то дальше вы из вершины 3 никуда не сможете пойти, уберете ее из стека и пометите как visited. Далее вы рассмотрите ребро 1->2 а потом из вершины 2 ребро 2->3 вы пропустите, потому что вершина 3 уже visited.

Этот пример можно бесконечно усложнять - все зависит от того в каком порядке будут обходится ребра в каждой вершине.