Wataru

Контрпример - это тот, который опровергает утверждение.
Утверждение - каждый связный граф имеет хотя бы одну вершину степени 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) после вывода сообщения об ошибке, на мой взгляд не нужен. Зачем это? Заставить пользователя прочитать сообщение об ошибке?

Вы не копируете '\0' на конце. Поэтому после приписывания идет мусор. И так получается, что у вас в памяти там мусор "v\0".

Вторая проблема, вы пишите в строку s, не меняя ее размер.
char s[] = "abc"; выделяет ровно столько памяти, сколько нужно для "abc", да еще и на стеке, раз у вас переменные локальные.

Вы при дописывании чего-то к строке затираете другие переменные. Так у вас совпало, что после name идет surname на стеке. Поэтому вы переписываете память второй строки (но без первого символа, который занял место '\0' в name. Именно поэтому мусор в конце - это неперезаписанный конец surname "v\0". Если поменять местами переменные, то вы может стек перепишите и у вас программа вообще упадет.

Вам надо строки выделять с запасом: char name[1000] = "Ivan";

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

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

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

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

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

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

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

Допустим, 19 = 2+2+5+5+5. Но можно же переставлять карты местами. Ведь диллеру могли прийти 5, потом вторая 5, потом 2, потом 2, потом 5. Да и сами пятерки могли прийти 3! способами. Однако, вы не можете поставить 2 последней, потому что сумма четырех первых карт уже 17. Диллер бы не тянул эту последнюю двойку.

Но 19=3+3+4+4+5 уже можно выбрать всеми 5! разными способами. Поэтому эти 2 комбинации, хоть и дают одну и ту же сумму и содержат одинаковое количество карт, можно получить с разной вероятностью.

Правильное решение с применением динамического программирования:

Во-первых, переберите, какая карта будет вытянута последней. Найдите вероятности всех сумм с учетом этой карты (так, что она переваливает сумму за 17, но не пердыдущая). Потом просуммируйте по всем таким картам.

Исключите эту последнюю карту из колоды. Теперь надо найти сколько наборов карт заданной длины дают каждую сумму < 17. При этом при подсчете вероятности можно переставлять все эти карты как угодно. Поэтому имеет значение, сколько карт мы использовали для суммы.

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

При подсчете у вас есть 2 варианта - последняя из k карт или входит, или нет в сумму (допустим массив a[] хранит веса карт).
Т.е. F(n,k,s) = F(n,k-1,s)+F(n-1,k-1,s-a[k]).

База:
F(0, k, s) = 1 если s==0; 0 иначе
F(n,0,s) = 1 если n==0 и s==0; 0 иначе.
F(n, k, s<0) = 0

Можно сэкономить на памяти и считать в двумерном массиве с конца в начало, выкинув k (второй параметр).

Потом искомая вероятность набрать сумму x c последней картой l, если осталось в колоде max_k карт (если x<17+l, x>=17, иначе - вероятность 0):

P(x) = sum_{n=1..max_k} f(n, max_k, x-l) * n! * (max_k-n)! / (max_k+1)!

Тут перебор по всем возможным количествам карт у диллера. Дальше берем количество способов набрать нужную сумму из ДП. Потом домножаем на n!, потому что эти карты в руке у диллера могли прийти в любом порядке. Дальше домножаем на вероятность вытянуть конкретные n+1 карт (считая последнюю) из колоды с max_k+1 картами. Это 1/(max_k+1)/max_k/,,,/(max_k-n+1) = (max_k-n)!/(max_k+1)!

Этот множитель после f() можно пересчитывать за одно домножение и деление
при увеличении n.

Напоминаю, это надо просуммировать по всем возможным картам взятым за l, заново прогоняя ДП.