Wataru

На будущее: пишите вместе с задачей вашу идею решения.

Уберите ненужные переменные. Еще, зачем у вас там i % columns?

Похоже, надо в output.txt выводить, а не в stdout.

Еще, советую выводить перевод строки всегда, и не пропускать его на последней строке вывода.

Чтобы не было проблем с пробельными символами - читайте в двух вложенных циклах до rows и columns по одному char (а не string до eof). Это и ввод упростит и сделает его более безопасным ко всяким артефактам в тестах.

Можно попробовать вычислить корень быстрым алгоритмом. Но там сложно. Гуглите Karatsuba square root. Есть открытые реализации. Есть еще какой-то адский метод через быстрое преобразование Фурье, попробуйте погуглить и его.

Более простой в реализации, но менее быстрый метод вычисления корня - бинарный поиск. Храните l, r, l^2, r^2 и lr. По этим числам можно вычислить m=(l+r)/2, m^2, m*l, m*r без длинных умножений, а только складывая длинные числа и деля на 2. Вам надо поддерживать, чтобы l^2 <= n <= r^2. Изначально можно сделать l=1, r=10^51 (или больше - половина длины входного числа + немного, чтобы точно квадрат был больше n), потом делить отрезок пополам и отбрасывать ненужную половину.

Еще есть вероятностный метод через символ Лежандра/Якоби. Это будет самым быстрым методом.

Это как смотреть на последнюю цифру. Квадраты могут давать там 0, 1, 4, 9, 6, 5. Но нет ни одного квадрата, который оканчивался бы на 2. Т.е. если число заканчивается на 2, то можно сразу говорить, что это не квадрат. Это мы взяли остаток от деления на 10 (последняя цифра) и посмотрели, какие из них хорошие. Вот символ Лежандра - это такая проверка для модуля по любому простому числу (а не 10).

Если брать некоторое простое число p, то n может быть квадратом, только если символ Лежандра (n/p) - равен 1 или 0 (По научному: n - должно быть квадратичным вычетом).

Если брать небольшие (<64-битные) простые числа, то можно за линию считать n%p и потом вычислять символ Лежандра (n%p/p) по алгоритму через символ Якоби за O(log(p)^2). Когда подсчитали символ Лежандра и если он -1, то n - точно не корень.

Тут проблема в том, что это необходимый, но недостаточный критерий - если для какого-то p вы получили -1 - то это точно не квадрат. Но возможно можно подобрать такое число, что все ваши тесты дадут 1, а оно не квадрат. Поэтому надо брать много простых чисел. Скажем, 20. Желательно еще числа брать достаточно большими. Но их не надо искать каждый раз, можно захардкодить. Грубая прикидка говорит, что вероятность ошибки такого алгоритма 2^(-количество простых чисел).

Т.е. берете много простых чисел. Считаете для каждого n%p выполняя деление большого числа на короткое (один проход по массиву цифр). Потом считаете символ Лежандра. Если получили где-то -1 - то точно не квадрат. Иначе - скорее всего квадрат.

Можно совместить вероятностный тест и вычисление корня. Сначала проверьте парочку простых чисел на символ Лежандра для отсечения точно не квадратов. Еще проверку последней цифры можно сделать, это очень дешево. Если не отсеклись, то считайте корень. Так будет всегда работать правильно но будет быстрее работать в некоторых случаях.

Нет тут никаких алгоритмов. Тупо пройдитесь по изображению двумя циклами и заполните соответствующую ячейку нулем или еденицей.

На изображении квадратики размера 2x2, между ними один пиксель пустой. И по границам еще пустые пиксели. Если обрезать 1 пиксель справа и снизу, то получится, что каждой ячейке соответствует квадрат 3x3: или целиком белый, или с 4-мя черными пикселями в правом нижнем углу.

Соответственно, достаточно проверять пиксель с координатами 3*i+1, 3*j+1 для получения значения ячейки [i][j] (все индексы с 0).

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

Если изображение с артефактами сжатия, то можно брать среднее между 4-мя пикселями 3*i+x, 3*j+y (x,y=1..2) по всем трем компонентам (RGB) и смотреть, что оно сильно отличается от черного. Для этого делаете еще 2 вложенных цикла по x и y, там прибавляете значение цветов пикселя в переменную, потом делите на 12 и сравниваете, допустим, с 200. Если меньше - это черный квадрат, если больше - то белый.

Звучит, как бинарный поиск. Изначальный шаг - половина длины массива (128).
Следующий, половина от этого и так далее. Так будет максимум 8 проверок всего.

Если же надо делать обязательно +1 вторым шагом, то можно вычислить максимальное количество проверок, если первый шаг - X, а длина массива - N.

Первых проверок будет максимум - floor(N/X), вторых (с шагом +1) - X-1.

Можно примерно подсчитать в вещественных числах и попытаться минимизировать f(x) = N/X+X.

Можно найти производную f'(x) = 1-n/x^2. Ноль у этой производной при x=sqrt(n).

Отсюда получается, что примерно sqrt(256)=16 - искомая длина. Максимальное число проверок - 32.

Эйлеров цикл существует в графе, только если входная степень каждой вершины равна ее выходной степени.

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

Это элементарно доказать - путь в каждую вершину входит сколько-то раз и столько же раз выходит. Исключение - только начальная и конечная вершина, если они не совпадают.

Соответственно, вам надо подсчитать степени всех вершин, проверить что все хорошо (максимум одна с in==out+1 и одна с in==out-1) и запустить или от любой или от той, у которой исходящих ребер больше.

Вам нужен std::map или std::unordered_map. Самому писать структуру данных не надо.

Первое будет деревом поиска, второе - хештаблицей.
Дерево поиска гарантированно будет работать стабильно быстро. Хеш таблица будет работать быстрее, но если вам не повезет, то может работать очень долго. Но предпочтительнее, на мой взгляд, таблица.

В качестве ключа используйте пару {Тип транспорта, номер маршрута}. В качестве значения - счетчик остановок.

Еще вам нужен еще один map из тип транспорта-> std::set или std::unordered_set номеров маршрутов.

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

Для поиска ответа пройдитесь циклом по всем элементам set из второго map - это все маршруты. Смотрите в первом map'е сколько остановок у этого маршрута и выбирайте максимум.

Бинпоиск поддерживает текущий отрезок, в котором возможно есть искомый элемент. Смотрит на середину и отбрасывает одну из половин отрезка.

Вы же как-то пытаетесь реализовать это только лишь с переменной mid. Если надо идти влево, то вы делите mid пополам, как будто бы текущий отрезок от начала массива (Но это не всегда так: после первого же шага вправо начало массива будет уже выкинуто из расмотрения), Потом, при переходе вправо, у вас какой-то бред написан.
Math.floor((arr.length - mid) / 2) - это что вообще должно делать? Если mid=9, length = 10, вы вообще уйдете в начало массива, хотя должны идти вправо. Если вы хотели взять середину между mid и length, то там должен стоять "+" внутри.

Но так все-равно не получится сделать. Заведите 2 переменные l и r, как во всех реализациях бинпоиска, считайте mid как середину отрезка, и при выбрасывании одной из половин просто переписывайте l или r на mid+1 или mid-1 (потому что сам mid элемет вы уже рассмотрели и он точно не нужен).

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

Тут можно решать динамическим программированием. Пусть 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) времени.

(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))

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

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