Wataru

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

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

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

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

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

Тут можно решать динамическим программированием. Пусть F(l,r) - минимальное количество операций удаления, чтобы сделать из строки с l по r правильную скобочную последовательность.

База - если l..r - пустая строка - ответ 0.
Иначе надо рассматривать варианты, что будет с последним символом. Если в конце стоит открывающая скобка, то ее надо удалить - других вариантов нет: F(l,r) = 1+F(l,r-1).

Если же там закрывающая скобка, то есть 2 варинта: или этот символ удаляем, или берем в ответ. В первом варианте ответ такой-же, как выше. Во втором - надо перебрать, а какой же символ в строке будет открывающей скобкой для данной. Пусть это символ i (там должна стоять открывающая скобка того же типа). Тогда ответ F(l,i-1)+F(i+1,r-1) - ведь части перед парой скобок и внутри их должны тоже быть правильными последовательностями.
Из всех вариантов надо выбрать минимальный - это и будет ответ для текущего состояния.

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

Ответ к задаче - F(1,n) - для всей строки.

Это решение потребляет O(n^2) памяти и занимает O(n^3) времени.

Контрпример - это тот, который опровергает утверждение.
Утверждение - каждый связный граф имеет хотя бы одну вершину степени 2.
Т.е. контрпример - связный граф, который не имеет ни одной вершины степени 2.
Степень вершины - это сколько ребер в нее входит. Можете найти такой граф на картинке?

Если в условии "трех различных цифр" означает, что все цифры разные, то ответ - количество сочетаний из 10 по 3, умноженное на 3 факториал: C(10,3)*3! = 10*9*8 = 720.

Логично: есть 10 вариантов выбрать первую цифру, 9 - вторую (исключив вариант повторения), и 8 - третью (минус 2 варианта повторения первой и второй цифры).

matrix - у вас пустой список, а вы пытаетесь в [i,j]-ую ячейку что-то записать. Ошибка о том и говорит, что идет обращение по недопустимому индексу.

Вы после ввода m, n сделайте вот это:
matrix = [[0 for x in range(n)] for y in range(m)]

А уже потом ваши 2 цикла с генерацией делайте.

Ну или в циклах добавляйте в matrix новые элементы:

matrix = []
for i in range(m):
  matrix.append([])
  for j in range(n):
    matrix[i].append(random.randint(1,9))

(n+k-1) / k даст округление вверх, потому что прибавление k-1 к числителю переваливает его за следующее делящееся на k число после n. Если остаток от деления n на k был не ноль, то мы к этому остатку прибавили k-1 и получили число не меньше k, которое даст +1 к результату деления (что тут и нужно, ведь при неделящемся на k n - округление вверх на 1 больше округления вниз). Если же n делилось на k, то прибавление k-1 не перевалит за следующее делящееся на k число и результат деления не поменяется.

Округление вниз уже есть встроенное в большинство языков - это просто целочисленное деление. Поэтому сводят к нему.

У вас решение за 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))

Проверьте для мелких чисел сначала.
2,5 - 2
4,25 - 3
8,125- 4
16,625 - 5.

Вроде как напрашивается паттерн, что ответ в вашей задаче 2021.

Почему так? Его можно доказать. Как Rsa97 уже написал, количество цифр - log_10, округленный вниз+1. Пусть k=2020, тогда ваш ответ:

2+floor(log(2^k))+floor(log(5^k)).

Если бы floor не было, учитывая log(a)+log(b) = log(ab), то мы бы получили 2+log(10^k), что было бы 2+k. Но у нас есть floor, каждый из которых уменьшает занчение на число от 0 до 1, больше 0, но меньше 1 (ведь ни 2 ни 5 ни в какой спени не дадут степень 10 - log дает нецелое число). Итого - ответ меньше чем k+2 на некое число, от 0 до 2 (невключительно) и целое. Такое число только одно - k+1.

У вас путь к файлу аж в трех местах написан!

Вы попробуйте только в одном месте путь передавать (или в конструкторе ofstream без вызоыва open() или используйте конструктор без параметров, но тогда оставьте open). И используйте string, раз уж его завели. И сделайте его const string заодно.

Первый цикл читает входные данные в массив x. Ваши "1, 1, 1, 0, 0, 1, 0, 1, 1" будут в этом массиве (только нужно сначала 9 ввести в качестве n).

Поэтому проверка на 1 имеет смысл и даст истину для первых трех итераций, но не для двух следующих, и т.д.

Пока вижу проблему, которая 100% приведет к тайм-лимиту. Вы при изменении приоритета ищите по всей очереди. Если вам дадут 500000 добавлений в очередь, а потом 500000 уменьшений случаного элемента, то ждать вы завершения программы будете очень долго.

Надо поддерживать массив позиций по по всем айдишникам. При любом перемещении пары элементов в массиве в очереди надо обновлять этот массив позиций.

При изменении приоретета уже не надо никакого find, потому что позиция уже будет доступна в массиве.

При добавлении нового элемента не надо вызывать build_heap. достаточно только shift_up от нового элемента. У вас в программе отдельно этой функции нет, но она фактически реализована в decrease_key. Только нужно, опять же, проходится не по всей очереди, а только по отцам. В цикле надо делать не i--, а i = (i+1)/2-1.

И ошибка как раз в decrease_key, У вас цикл по i, а внутри все время используется k.

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

По коду есть комментарии:
1)

if ((valVAT == 10) || (valVAT == 18) || (valVAT == 20)) {
...

Тут у вас один большой мега-if в котором что-то делается. Гораздо проще для понимания и визуально читабельнее, если делать "ранний выход". Вместо if(a) { много кода } стоит писать:

if (!a) {
  continue; // или return; если это в функции.
}
// много кода.

У вас стоит сначала проверить, что valVAT == 0 и выйти из цикла через break в этом случае. Потом проверить, что valVat != 10 && valVAT != 18 && valVAT != 20 и вывести сообщение об ошибке и сделать continue. Дальше уже идет тело цикла с вычислениями.

2) Вместо if(chng == 1) {} else if (chng == 2) {}... стоит использовать конструкцию

switch (chng) {
case 0:
  // код
  break;
case 1:
  // код
  break;
case 2:
  // код
  break;
default:
  // сообщение об ошибке
  continue;
}

3)
sleep(1) после вывода сообщения об ошибке, на мой взгляд не нужен. Зачем это? Заставить пользователя прочитать сообщение об ошибке?