Wataru

В заголовке у вас про четные, а в теле задания - плолжительные. Программа как бы ищет четные. Но числа float же, для них четность не имеет смысла. Вам нужно вместо float при вводе приводить к int.

edit:
А еще у вас при обходе матрицы только один цикл. А надо так же как при вводе делать двумя вложенными циклами.

Проблема не в коде, а в алгоритме. Долго строить всю строку и считать в ней нули.

Есть вот такая формула. Для каждого простого числа можно опредерить степень просто деля n (не факториал!) на это простое число нацело, пока не получится 0 и суммировать все результаты.

Но это работет только для простых чисел. Т.е. чтобы узнать, в какой степени число 10 входит в N! (или сколько нулей на конце в деситичной записи) надо узнать, сколько раз 2 и 5 входят в N! и взять минимум.

Т.е. надо разложить k на простые множители, для каждого простого множителя подсчитать, сколько раз он входит в n! по формле выше. Потом поделить это на степень простого числа в k, и по всем делителям k взять минимум.

Алгоритм Ахо-Корасика.

Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.

Вы, похоже, забыли обнулять счетчик восьмерок (k) для каждого значения f.

У вас две большие ошибки с языком питон. Вы в цикле в alg итерируетесь по списку add, меняя его. Так делать нельзя. Ломаются итераторы и вы пропускаете половину элементов.

Вместо этого используйте цикл while:

while add:
  item = add[0]
  add.remove(item)
  s.append(item)
...

Вторая большая ошибка, в питоне списки передаются по ссылке! Поэтому s, который у вас параметр рекурсивной функции, на каждом уровне один и тот же список. Но при выводе множества вы сразу же возвращаетесь из функции, не удаляя item из s. Вам надо чтобы все изменения в s были отменены по выходу их функции. Перед return делайте s.remove(item).

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

Еще по коду:
range(n) в python возвращает 0..5. У вас там цикл по ребрам в __main__ и там идет обращение к i-1 в массиве graf. Т.е. обращение к [-1]. Вряд ли вы это хотели. Работает по чистой случайности, потому что в питоне a[-1] дает последний элемент.

И вообще, вы матрицу смежности строите, но нигде не используете.

Вместо функции check(), вы сделайте нормальный список смежности один раз, а то просто глаз режет от неоптимальности.

neighbors = [[] for i in range(count_vershin)]
for edge in graf:
  neighbors[edge[0]-1].append(edge[1]-1)
  neighbors[edge[1]-1].append(edge[0]-1)

Это не совсем ним (где несколько кучек и за ход можно взять сколько угодно камней). Судя по коду, игроки могут брать 1,2 или 3 камня и кучка одна. Кажется, у вас выигрывает тот, кто возьмет последний камень.

Сначала немного теории игр.
Если камней 1-3, то первый игрок выигрывает (очевидно, беря все). Если камней 4, то любой ход приведет к выигрышной позиции. Значит 4 - это проигрышная позиция. Начинающий в ней ВСЕГДА проигрывает (если второй игрок, конечно, не поддается и не делает глупостей). Далее чуть чуть логики и становится понятно, что любая позиция вида 4*k проигрышная. Выигрышный ход - вычесть n%4 камня, чтобы врагу досталась пощиция с делящимся на 4 количеством камней. Что вы делаете из такой проигрышной позиции неважно.

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

Правильная функция choize должна быть:

def choose(s):
  if s%4 == 0: return 1
  else return s%4

Тогда бот обязательно выиграет, если выигрышная позиция есть, или если человек допустит ошибку, хоть у него и была выигрышная стратегия.

Еще по коду. Вместо if i==0 else if i ==1, можно просто делать i=1-i. а лучше вместо i=0 заведите bots_move = true и делайте bots_move = not bots_move.
Вместо s назовите переменную num_stones. Вместо a - human_move. Некоторые ваши комментарии в коде бесполезны, ибо они просто дублируют код, а не объясняют зачем или почему этот код таков.

Простой вариант в реализации - перебирайте перестановку. Вот у вас в ответе буквам сопоставляются числа. Зафиксируйте порядок букв (вершин в одном графе). Тогда вершины второго графа (числа в ответе) будут представлять собой перестановку. Перебирайте все перестановки. Потом проверяйте, что одна матрица смежности после перестановки станет равна второй. Буквально для всех i, j проверяйте, что a[p[i]][p[j]] == b[i][j].

Перебор перестановок - известная задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в python.

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

Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех ja[p[i]][p[j]]==b[i][j] выполняются).

Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.

Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j] поменять на a[i][j]==b[p[i]][p[j]] (Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).

И меня не устраивает "единственный" проблемный отрывок кода:
if ndata[i] % 2 != 0 and nf % 2 != 0: lucky += 1

Там вообще какой-то бред написан. При чем тут проверка на четность вообще?!

Вам надо подсчитать солько чисел из trda есть в ndata и вывести Lucky, если насчитали хотя бы 3 (перечитайте же условие задачи).

Соответственно должно быть что-то вроде

if nf == ndata[s]: cnt+=1
...
if cnt >=3:  print('Lucky')
    else: print('Unlucky')

Еще у вас вложенные циклы по одной и той же переменной i, может в питоне так и можно, но это обычно очень плохая идея.

Если я правильно понял задачу, то надо подсчитать для каждого i
sum_{j=1..n} (i%j?1:0) % 2.

Или - есть n ламп в ряд изначально не горящих. Переключаются каждая первая, каждая вторая, третья и т.д. Вопрос - а какие лампы горят в конце.

Разверните условие. Не переключайте каждую 1-ую, 2-ую и т.д. лампу, а подсчитайте для каждой лампы, сколько раз она будет переключена (потому что переключать их все по одной - это медленно. Надо как-то агрегировать вычисления)?

Лампа будет переключена ровно столько раз, сколько делителей у ее номера. Иными словами - вам надо понять, четное ли количество делителей у каждого числа. Вспоминаем, что любое число представимо в виде разложения на простые множители: p1^k1*p2^k2* ... pm^km. Можно подсчитать количество делителей - это будет (k1+1)(k2+1)...(km+1), ведь каждое простое число может входить в делитель в степени от 0 до ki включительно.

Теперь, в каком случае это число будет нечетным? Только если все ki четные. А это значит, что число - полный квадрат (все степени четные же. Берем корень, делим степени пополам, получаем целое число).

Итого ответ - проставить true в массиве по всем индексам i*i.

Нужна рекурсивная функция, которая обрабатывает строку и возвращает распакованную версию и где ее конец в заданной строке.

Ваша ошибка в том, что в слуае "2(с)3(a)" вы попытаетесь 2 раза повторить результат распаковки строки "с)3(a"

def process(s, begin):
  i = begin;
  ans = ""
  while i < len(s):
    // Внетренность скобок обрабатывается рекурсивно. ) - это конец строки для нас.
    if s[i] == ')': break;
    if '0' <= s[i] and s[i] <= '9':  // если встретили цифру
      k = 0
      // выделяем в k числовое значение записанного числа
      while i < len(s) and '0' <= s[i] and s[i] <= '9':
        // пока встречаются цифры берем их численное значение и приписываем в конец к k
        k = 10*k + ord(s[i]) - ord('0')
        i+=1
      // если после числа идет бува, то просто копируем ее нужное количетсво раз
      if  'a' <= s[i] and s[i] <= 'z': 
        ans += s[i:i+1]*k
        i+=1
      else:
        // иначе - должна быть скобка.
        assert(s[i] == '(')
        // рекурсивно обрабатываем внутренность скобок. Функция вернет нам, где
       // закрывающая скобка для данной.
        (i, cur) = process(s, i+1)
       // копируем результат распаковки строки внутри скобок нужное количетво раз
        ans += cur * k;
    else:
     // цирфы не было. Просто символ без множителя идет в ответ.
      assert('a' <= s[i] and s[i] <= 'z')
      ans += s[i:i+1]
      i += 1
  // мы могли закончить цикл на закрывающей скобке или в конце строки.
  // но скобку надо пропустить. Прибавляем 1 к счетчику.
  if i < len(s): i+=1
  return (i,ans)



print (process("abc", 0))
print (process("3a", 0))
print (process("3(a)", 0))
print (process("2(ab)", 0))
print (process("10(a)", 0))
print (process("2(b2(a))", 0))

Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

Проблема в том, что вы пытаетесь считать параллельно для правой и левой половины. Логично, коэффициенты там симметричные будут, но можно сделать ошибку. И ускорения ваша оптимизация практически не несет. В 2 раза меньше итераций, делающих в 2 раза больше + дополнительная проверка каждый раз. На компилируемых языках может быть еще и медленнее наивного цикла от 0 до n-1. В питоне - не знаю. Уж точно не в 2 раза быстрее, как можно было бы подумать.

Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.

Не понимаю, в чем проблема вообще. Забудьте, что это строки или числа. Все что нужно для бинпоиска - это уметь спрашивать < или = искомая штука и штука в массиве по заданной позиции.

В питоне есть массивы (доступ по индексу) и строки он сравнивает автоматом через операторы == и <.

Т.е. можно написать тот же абсолютно код, что и для бинпоиска по числам и он будет работать на строках. Правда, надо помнить, что сложность у бинпоиска по строкам будет не O(log n), а O(L log n), где L - максимальная длина строк.

Давайте составим рекурентное соотношение. Пусть F(n) - сколько работает ваша функция при входе в n элементов.

В функции:
- Выделяется новый массив: n операций
- Вызывается функция для укороченного массива: F(n-1) операций
- Цикл по всем перестановкам n-1 элемента: (n-1)! повторений
- Вложенный цикл по позициям: n*(n-1)! = n! повторений
- вложенное в циклы построение новой перестановки: n*n! операций

Итого F(n) = n + F(n-1) +n*n!

Можно раскрыть рекурсивно и получим:
F(n) = 1 + 2 + 3 + ... + n + n*n! + (n-1)*(n-1)! + (n-2)*(n-2)! + ... +1
Аккуратно посмотрев на это можно понять, что все члены, начиная от (n-1)*(n-1)!, cумарно меньше n*n!, а первые n членов вообще мизерные и их можно отбросить.
В итоге, F(n) = O(n*n!).

Обратите внимание, тут мало просто взять самый большой член. Их же n штук и если бы они были примерно одинакового порядка, то возник бы еще один множитель n в ответе. Но тут остальные члены как минимум в n раз меньше самого крупного.

Сложность по памяти такая же - ведь вы там в итоге храните все перестановки, их n! и каждая занимает n. Но это оценка ассимптотики - O(n*n!). На самом деле будет чуть больше n*n! элементов, потому что хранится список ответ и список для меньших перестановок, плюс стек и промежуточные массивы при конкатенации.

Это хорошая ассимптотика - для построения всех перестановок меньше нельзя.
Однако, если вам не надо все перестановки хранить в памяти (да и для кэша, кстати) будет заметно быстрее генерировать следующую перестановку из текущей на месте, как описано тут. Хоть и с такой же ассимптотикой, этот алгоритм будет работать в несколько раз быстрее.

Немного пальцем в небо, но попробуйте заменить "/" на "//". Вам же надо в целых числах считать. Возможно, питон пытается блинные числа приводить к даблу и потом назад к длинными и теряет точность.

Вместо ceil(a/b) используйте (a+b-1)//b
Вместо floor(a/b) или, когда делится без остатка используйте a//b

В логике решения ошибки я не вижу.

У вас проблема в решении в том, что вы сравниваете 2 обхода. Это неверно для, как вам уже приводили в пример, этих двух деревьев:

1
 \
  2
   \
    3

    3
   /
  2
 /
1

Тут оба обхода вернут 1,2,3.

Можно в вашем решении добавлять всякие разделители при переходе влево-вправо-вверх. Вставить всякие yeild -1 и другие значения перед походом влево, выводом собственно элемента и походом вправо.

Но есть лучшее решение, через DFS или BFS: вы делайте обход одновременно на двух деревьях. Т.е. у вас параметр функции dfs или в очереди в bfs лежат сразу 2 вершины - по одной из каждого дерева. Вы проверяете, что у них значения одинаковые и что у них у обеих одновременно есть или нет левого и правого ребенка. Потом вызываетесь/кладете в очередь одновременно левых детей и одновременно правых детей. Если в процессе обхода вершины оказались разными, или где-то есть ребенок, а где-то нет - то деревья не равны.

Очень логично реализовывается в виде DFS (ниже псевдокод):

Equals(t1, t2):
   // обработать случай null одного или обоих деревьев.
   return t1.v == t2.v && Equals(t1.left, t2.left) && Equals(t1.right, t2.right)

Все предельно логично - 2 дерева равны, если у них равны корни, левые поддеревья и правые поддеревья.

Кстати, ваше решение, если его исправить, тоже будет за O(n).

Ваша программа ломается, если X=Y, например.
Чтобы ее исправить, вместо веса edge и сравнения его со стоимостью товара, передавайте в функцию число от 1 до 3. Если число <=1, то можно брать x и передавать 1. Если <=2 - то можно брать y и передавать 2, и т.д.