Ответы пользователя по тегу Python
  • ValueError: invalid literal for int() with base 10: '', что делать?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вводите в переменную и выводите ее на экран, чтобы было видно, что с ней не так.

    Везде, где вы читаете из файла делайте:
    l = f.readline()
    print("The line is: \""+l+"\"")
    n = int(l)


    Тогда сразу станет очевидно, что не так с файлом или кодом.
    Ответ написан
    Комментировать
  • Как ускорить перебор элементов списка?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно в несколько раз с оптимизировать, переписав на C++ c векторизацией (SSE там всякие). Тогда сравнение двух строк будет 1-2 инструкции вместо 15. Еще можно распаралеллить вычисления. Но все эти оптимизации все равное не позволят вам быстро считать для 100000 строк. Что уж говорить, сама матрица будет занимать минимум 10 гигабайт, если аккуратно на C писать или типизированный numpy массивы использовать. А так она и все 20 и 40 гигабайт займет запросто.

    И ничего сильно более быстрого тут не получится, если вам нужна вся матрица - придется пару минут ее считать в лучшем случае. Вот если вы ее используете для каких-то еще вычислений (например, вы для каждой строки считаете, сколько близких к ней есть в списке), то можно принципиально ускорить решение не вычисляя матрицу, а считая искомое количество сразу.
    Ответ написан
    Комментировать
  • Компилятор сайта не понимает кодировку?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Кодировка исходного файла не та.

    Откройте исходник в блокноте - сохранить как - и выбирайте разную кодировку под именем файла. Если появились кракозябры, измените их на русские да/нет и сохраните файл. Повторите операцию для разных кодировок, пока не сайт не примет.
    Ответ написан
    Комментировать
  • Это правильная реализация бинарного поиска?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Работает медленно, потому что вы обрезаете входной массив каждый раз. Для этого приходится обходить и копировать всю нужную часть. Поэтому суммарное время работы будет O(n).

    Чтобы работало быстро вам надо не менять lst, а помнить индексы границ текущего куска.

    Ещё, вам надо останавливаться, когда рассматриваемый кусок станет пустым, чтобы решение не вылетало, если искомого числа в списке нет.

    И последнее, в питоне есть операция целочисленного деления - //. Используйте ее вместо приведения к int после деления.
    Ответ написан
    2 комментария
  • Как обрезать путь чтобы осталось только имя файла?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    for file in filename: переберет в file все символы строки filename.

    Вам надо просто передавать ваш filename в open.
    Ответ написан
    Комментировать
  • Python/numpy: как увеличить массив на одну строку без использования дополнительной памяти?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Нет.

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

    Это даже в C++ сделать нельзя, не говоря уже о питоне.

    Edit: Вообще говоря в C++ есть realloc, Но оно не гарантирует расширение существующей области памяти. Ибо она может быть занята чем-то еще.
    Ответ написан
    1 комментарий
  • Как посчитать БЖУ?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это задача о многомерном рюкзаке (multi-dimensional knapsack). Каких-то простых трюков, как с обычным одномерным рюкзаком тут нет. Только перебор с отсечениями.

    Еще можно свести задачу к целочисленному линейному программированию. Вводите переменные - сколько штук каждого пункта съели, составляете линейные уравнения. Потом можно это все скормить какому-нибудь решателю. Сейчас много библиотек и они довольно быстро такие задачи щелкают. Гуглите "integer linear programming solver".
    Ответ написан
  • Алгоритм поиска минимального количества ходов, требуемых для приведения всех элементов к одному числу (Python)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Во-первых, в вашем алгоритме цикл while вообще не нужен. Сколько нужно операций +1, чтобы из a получить a+12345? Ровно 12345. Вам надо просто вычесть одно число из другого.

    Далее, мысль должна быть такая: Вот вы знаете, сколько нужно операций, чтобы все числа в массиве привести к X. Вопрос: сколько операций вам понадобится для приведения всех чисел к X+1? (Подсказка - если число было меньше X, то теперь понадобится на 1 операцию больше. Если число было больше X - то понадобится на 1 операцию меньше).

    Теперь вам надо посмотреть, подумать и выбрать оптимальное X, которому вы будете приводить все числа. Ваш вариант с max/2 не оптимален.
    Ответ написан
    5 комментариев
  • Как решить задачу, используя одну формулу и не успользуя if, else, elif?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Бинарный поиск.
    Можно реализовать без if-ов вообще.
    Суть в том, что у вас есть текущий отрезок. Находите середину, спрашиваете про нее. Получаете ответ R = 0 или 1. Потом прибавляете половину отрезка к левой границе, умноженную на R и вычитаете ее из правой границы, умноженную на 1-R. Таким образом сдвинется только одна граница. Остается вопрос, что делать с выходом из цикла. Там же внутри if запрятан.

    Можно или скопировать код 7 раз (2^7 > 100), или иметь бесконечный цикл, который будет сравнивать границы и вызвать одну из двух функций в массиве на 2 элемента. Одна из функций выведет ответ и завершит работу программы через exit. Вторая - не будет делать ничего.
    Ответ написан
    Комментировать
  • Как решить данную задачу на python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Динамическое программирование.

    F(i,k) - максимальная сумма, которую можно получить из первых i троек, такая что ее остаток от деления на 4 равен k.

    База: F(0,0) = 0, F(0,k) = -infinity.
    Ответ: F(n, 0).

    Пересчет
    F(i,k) = max(F(i-1, ((k-a[i][0]-a[i][1])%4+4)%4)+a[i][0]+a[i][1], 
                 F(i-1, ((k-a[i][1]-a[i][2])%4+4)%4)+a[i][1]+a[i][2], 
                 F(i-1, ((k-a[i][0]-a[i][2])%4+4)%4)+a[i][0]+a[i][2])


    Только лучше вместо -infinity как-то отмечать, что позиция (i,k) недопустима (нельзя первыми i тройками набрать сумму с остатком k. И недопустимые варианты при выборе максимума выбирать ненадо.

    Еще, вместо перебора всех пар из трех элементов лучше брать сумму трех и вычитать один, который перебирается циклом.
    Ответ написан
  • Как создать n количество переменных?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Список/массив на n элементов.
    Ответ написан
    Комментировать
  • Python vs C. Какой из них быстрее?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Попробуйте сделать вывод в файл. Запускайте с "> output.txt". У меня си работает в несколько раз быстрее (меньше секунды), питон - пару секунд.

    Вывод в консоль тормозит, потому что при компиляции через mingw идет как бы эмуляция линуксовой консоли, которая преобразуется в виндовую. Питон же наверняка работает нативно. Если вы интерпретатор питона из исходников на mingw соберете, то будет работать столько же. В этом примере вы разницу не намеряете, потому что тут вы в основном тестируете скорость вывода в консоль. Замените вывод на вычисления, или что-то другое полезное, и у си будет в разы быстрее питона.
    Ответ написан
  • Как правильно решить задачу про кузнечика путём динамического программирования?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы поняли, что это динамическое программирование. Опишите, что у вас за функция ДП, дайте формулу пересчета, базу и где ответ.
    Ответ написан
  • Как реализовать такую функцию где надо используя аргументы (+ - / *) вставляя между цифрами получить заданное чисто. Как вывести все результататы?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Только перебор всех возможных вариантов.
    Ответ написан
    Комментировать
  • Как оптимизировать алгоритм подсчёта остатка на складе по системе LIFO (последний пришел первый ушел)?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Надо сделать по нормальному, без таблиц, с использованием стека, который можно сделать просто тупо списком.

    Обрабатывайте все записи в хронологическом порядке.

    При приходе in, вы добавляете в стек (через append у list-а) пару (цена, количество).

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

    Что-то вроде такого (сам не питонист, возможно придется переписать немного)

    def getOstatokLIFO(df):
      stack = [];
      for index, row in df.iterrows():
        if row.operation == "in":
          stack.append([row.price, row.quantity])
          continue
        left = row.quantity
        while left > 0:
          if left >= stack[-1][1]:
            left -= stack[-1][1]
            stack.pop()
          else:
            stack[-1][1] -= left
            left = 0
            
      return stack


    Но вообще, DataFrame очень медленно работет при такой последовательной обработке, поэтому я бы посоветовал вам не создавать pandas dataframe изначально, и получить ваши данные в виде списка словарей, touples или объектов. А алгоритм расчета предполагает последовательную обработку.
    Ответ написан
    Комментировать
  • Как посчитать сумму цикла?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Ну, вот вы числа вывели. Теперь вместо вывода прибавляйте их к переменной сумме, которая 0 перед циклом.
    Ответ написан
    Комментировать
  • Как заставить нейронку на Python подгонять коэффициенты уравнений?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Тут не нейронка нужна, а регрессия. Ну или тупо система линейных уравнений.
    Ответ написан
  • Как найти Среднее арифметическое элементов массива через рекурсию?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Подумайте, как можно рекурсивно считать сумму. Далее, среднее арифметическое элементарно выражается через сумму, а сумма - через среднее арифметическое. Вот и получается формула:

    Avg(a1,a2,...an) = (Avg(a2,...an)*(n-1)+a1)/n
    Ответ написан
    Комментировать
  • Какую ошибку допустила в цикле?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Зачем там while True?

    Почему сравнение с 1 в условии? Вроде как результат сравнения будет True или False.

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

    Ну и, последнее. В условии натральные значения x и y, а у вас циклы перебирают и отрицательные значения.
    Ответ написан
  • Что требуется в задаче Python?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Перечитайте условие медленно. Посмотрите пример.

    В первой задаче надо выбрать какие-то числа, в числах выбрать какие-то цифры (всего не более k цифр) и заменить их другими цифрами так, чтобы сумма увеличилась как можно больше. Очевидно, что заменять надо старшие цифры и всегда на 9. Поэтому можно сразу сказать, что если мы в числе 128694 заменяем 3 цифры - то это "128" и получится 999694.

    Особый случай тут, если число содержит девятки - их надо пропустить.

    Теперь задача немного упрощается. Надо распределить k цифр по числам, чтобы получить максимум профита, т.е. увеличить максимально сумму чисел.

    Можно еще немного порисовать тесты на бумажке и понять, что каждое число можно рассматривать как набор цифр. Каждая цифра отдельна. Ибо замена одной цифры увеличит сумму на (9-цифра)*10^(разряд цифры) независимо от остальных цифр. Т.е. задача еще преобразуется - есть куча цифр каждая с известным профитом, если ее заменить. Надо не более k из них взять, так что бы сумма изменения была максимальна.

    Теперь понятно, что задача решается сортировкой. Считатете для каждой цифры сумму профита, все это складываете в массив (длины максимум 10*n). Сортируете по убыванию и берете сумму первых k значений.

    Вотрая задача - опять же медленно читайте. Я не могу за вас понять. Объяснить как-то проще условие тоже не могу. Попробуйте порисовать тесты в виде пронумерованных точек, от которых стрелочки идут к значению a[i] - кому они дают подарки. Вам надо ровно одну стрелочку переместить так, что бы все стрелочки замкнулись в один круг.

    Для решения надо понять, а что будет, если не менять ни одно число? Путь из точки 1 будет или циклом или чем-то вроде цифры "6". Сначала какой-то хвост, который зацикливается где-то на середине.

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

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