Wataru

Как это часто бывает в задачах на отражение света, не надо отражать луч. Представьте, что зеркало - это портал в Зазеркалье. Луч идет прямо и, проходя через зеркало, попадает в соседнюю треугольную комнату.

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

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

Но в этой задаче это вам не поможет никак - ибо симулировать эти 100500 отражений и квантилионы возможных начальных углов никакого времени не хватит.

У вас решение за O(N^2), когда как можно сделать решение за O(N). Тут не в питоне дело, а в плохом алгоритме.

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

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

Я не совсем питонист, но вот примерный код:

def days_till_warming(T):
    counts = []
    stack = []
    for i, curr_temp in enumerate(reversed(T)):
        while len(stack)>0 and stack[-1][0] <= curr_temp:
            stack.pop()
        delta = i - stack[-1][1] if len(stack) > 0 else 0
        stack.append([curr_temp, i])
        counts.append(delta)
    return list(reversed(counts))

Пусть координаты x0,y0. Расстояние можно считать по этой формуле (вики).

Вам придется или скопировать код по ссылке и переписать на питоне, или использовать этот пакет.

Дальше, вам надо начиться отступать от заданной точки на север или восток на 1 метр. Это можно или медетировать над формулой выше а можно просто запустить бинарный поиск, который будет искать изменение широты или долготы. Пусть d - сколько вам надо отложить в метрах, R - радиус земли в метрах. Тогда ищите изменение на отрезке (0, 4*r*180/(2*Pi*R)). Пробуйте откладывать текущее значение по широте или долготе, считайте расстояние по формуле и, если оно больше d, заменяйте верхнюю границу отрезка на середину, иначе заменяйте нижнюю границу. Остановите бин.поиск, когда отрезок станет достаточно мелким (например <1e-10).

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

Сначала сгенерируйте точки на одной вертикале с начальной. Для этого повторно откладывайте 1м на север и юг от нее, пока расстояние до (x0,y0) не превысит ваш радиус. Бинпоиск достаточно запустить ровно один раз в самом начале и дальше именно это приращение откладывайте вверх и вниз.

Потом аналогичным образом откладывайте от каждой сгенеренной точки новые точки на запад и восток. Сначала для каждой точки бинпоиском найдите нужное приращение по долготе. Потом откладывайте его влево и вправо, пока не выйдите за радиус от (x0,y0).

В заголовке у вас про четные, а в теле задания - плолжительные. Программа как бы ищет четные. Но числа 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)