Задать вопрос
Ответы пользователя по тегу Python
  • Поиск кратчайшего пути в ориентированном графе с цветными вершинами и дугами?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Тут надо сделать из графа на N вершин граф на N^2 вершин. Граф-то совсем маленький. Каждая вершина нового графа соответствует паре вершин изначалного графа (x, y) и обозначает, что фишки стоят в вершинах x и y соответственно. Переходы в новом графе делаются из переходов в изначальном: из (x, y) можно перейти в (x, z), если в изначальном графе есть дуга y->z и ее цвет совпадает с вершиной x. Аналогично из (x,y) можно перейти в (z,y), если есть дуга x->z и ее цвет совпадает с y.

    В этом графе уже можно любым известным вам способом искать путь. Только тут конечных вершин будет сразу много: это все пары (x,y), где x или у - конечная вершина в графе. Можно или добавить новую конечную вершину и соединить с ней все вот эти вот, или прямо в алгоритме исправить условие останова.

    Можно граф не хранить явно. Если у вас BFS, то храние в очереди сразу пару чисел. Внутри перебирайте переходы из первой а потом из второй вершины и делайте их только если условие на совпадение цвета выполняется. Ну и, все массивы хранящие расстояние и т.п. в алгоритме будут уже двумерные.
    Ответ написан
    Комментировать
  • Как перемешать между собой слова создав новые?

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

    Стандартный алгоритм перемешивания таков:
    for i in range(len(a)):
      j = random.randint(0, i);
      a[i], a[j] = a[j], a[i]


    Тут поддерживается инвариант, что первые i элементов равномерно и случайно перемешаны. На каждой итерации выбирается случайная позиция для нового элемента (возможно последняя и элемент никуда не переместится). Дальше достаточно только лишь поменять новый элемент со стоящим на его месте. Ведь по инварианту все остальные элементы уже случайно перемешаны и в итоге случайно перемешанными оказываются N+1 элементов.
    Ответ написан
  • Как считать длинные числа в Python?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    В питоне большие целые числа встроенные. Но только целые.
    Если вы хотите соранить всю точность, то вам нельзя использовать числа с плавающей точкой. В вашем коде у вас деление на 100, которое и приводит к преобразованию в float и потерю точности. Замените деление на целочисленное и ответ будет точным.

    i - i * p // 100 посчитает точно, но там окргуление при делении будет вниз. Чтобы округлить вверх, можно воспользоваться хитростью - прибавть в числитель знаменатель -1: (i * p + 99) // 100 округлит вверх.
    Ответ написан
    Комментировать
  • Как оптимизировать данный код?

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

    Это известная, очень сложная (NP-сложная) задача об упаковке.

    Для сотен тысяч входных списков вы оптимальное по количеству кусков в ответе решение не найдете за все время до тепловой смерти вселенной. Всякие аппроксимации, вроде вашего жадного алгоритма, могут найти лишь какое-то хорошее, но не лучшее разбиение. В частности, у вас используется Next-Fit аппроксимация - вы в итоге можете выдать в 2 раза больше кусков в ответе, чем можно было бы. Есть более сложные алгоритмы, которые, например, гарантируют ухудшение максимум в 1.7 раза.

    Соглашусь с Dr. Bacon, через yield код вашего решения может быть чуть красивее, но я не совсем понимаю, что в вашей реализации вам так "не красиво". Хотя я не питонист.

    Далее, вы упоминули, что ключи во входных данных - это номера домов, а числа в списках - номера квартир. Вы как-то объединяете дома с ограничением на количество квартир. Не знаю, что у вас за задача на самом деле, но мне кажется логичным, что вам надо бы объединять дома только рядом. С одной улицы, или вообще идущие подряд. Ведь если в одной группе идут квартиры из домов в разных концах города, то какая вообще разница, что квартиры из одного дома могут быть в разных группах? Если такое ограничение ввести, то задача упрощается и ваше решение будет оптимальным.
    Ответ написан
    3 комментария
  • Как реализовать Алгоритм Решето Эратосфена от определенного числа, до данного?

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

    const int BE = 900000000;
    const int N = 1000000000;
    
    std::vector<int> small_primes;
    
    bool DivisibleBySmallPrimes(int x) {
    	for (int i = 0; i < (int)small_primes.size() && small_primes[i]*small_primes[i] <= x; ++i) {
    		if (x % small_primes[i] == 0) return true;
    	}
    	return false;
    }
    
    void ComputeSmallPrimes() {
    	int n = sqrt(N);
    	for (int i = 2; i <= n; ++i) {
    		if (!DivisibleBySmallPrimes(i)) {
    			small_primes.push_back(i);
    		}
    	}
    }
    
    void ComputeSieve() {
    	ComputeSmallPrimes()
    	std::vector<bool> sieve(N-BE+1);
    	std::vector<int> primes;
    	for (auto &x : small_primes) {
    		int i = (BE-1) - (BE-1) % x + x;
    		while (i <= N) {
    			sieve[i-BE] = true;
    			i += x;
    		}
    	}
    	for (int i = BE; i <= N; ++i) {
    		if(!sieve[i-BE]) {
    			primes.push_back(i);
    		}
    	}
    }


    upd:
    ComputeSmallPrimes можно переписать простым решетом - будет еще быстрее.
    Ответ написан
    Комментировать
  • Как перевести с python на c++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это копирование массива. На C++, если используете vector, то можно присвоение использовать. Там произойдет копия.
    Ответ написан
    Комментировать
  • Как расширить вычисление до 2^120?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Код в вопросе найдет такое i, что result станет равен 1, если цикл сделать до N. Для любых дельта и гамма. (но там цикл не нужен вообще).

    И наоборот. Какие бы вы дельта и гамма не взяли, может прийти такой Input, что result станет 1, только для очень большого i.

    Во-первых, вам цикл не нужен. Вычисления ваши можно упростить.
    result = (input / delta) / (i / gamma) = input * (gamma / delta) / i

    Если result = 1, то получается i = input * (gamma / delta) (естественно, умножение и деление по модулю N).
    Цикла не надо. Можно сразу вычислить искомое i.
    Решение единственно (если N простое. А если оно не простое, то делить по модулю нельзя).

    И это самое i может оказаться очень большим. Не всегда N-1, потому что у вас ограничение на Input есть дополнительное, Но даже в самом лучшем случае подбора гамма и дельта (обе по 1), вам может прийти input такой, что i будет равно 2^120.

    Ну и, во-вторых, вам не нужны две константы дельта и гамма. Тут есть ровно одна степень свободы - значение gamma / delta. Это должна быть единственная константа в вашем коде. В итоге оно все упрощается до:
    beta = 0x42
    i = beta * input % N
    result = 1


    И вообще тут, очевидно, проблема XY. У вас есть какая-то задача X, вы придумали какую-то фигню, как-то сформулировали вот эту вот задачу в вопросе (У), но вы ошиблись. Решение вот этой фигни в вопросе вам никак не поможет решить вашу изначальную задачу, пототму что вам не хватает знаний (теории групп, например, да и математики в целом). Вы задаете практически бессмысленные вопросы (уже не первый раз). Если хотите, чтобы вам тут действительно помогли - давайте вашу изначальную задачу. Я подозреваю, что это взлом криптографии и вам тут популярно объяснят, что вы зря тратите время.
    Ответ написан
  • Как правильно определить, какое число итераций необходимо?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Можно завести флаг "менялись ли элементы в цикле". Перед циклом его сбросить, при перестановке двух элементов - установить. А сам внешний цикл можно сделать while.

    Заранее определить, сколько будет итераций - очень сложно.
    Ответ написан
    Комментировать
  • Как вычислить правильно в скрипте python?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Я так понял, надо подобрать константы a,b,c,d?
    Вообще, можно a, b1, c считать равными 1 и менять только d.

    Но у вас там умножение и деление по модулю. Так что все очень сложно.

    Вообще, ваша задача не имеет решения.

    Модуль у вас в вопросе порядка 10^78. А X может быть 10^119-10^120. Если x взять по модулю N, то там может получится вообще любой остаток (потому что 10^120-10^119 = 9*10^119 > N)

    А дальше, умножая эти числа на константу, если N простое (а оно должно быть простым, иначе деление по модулю не определено), то можно получить любой остаток до N. Не только до 2^60 - 2^70.
    Ответ написан
  • Статическая типизация на питоне, почему не работает?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Интерпретатор Python не осуществляет проверку типов:
    The Python runtime does not enforce function and variable type annotations. They can be used by third party tools such as type checkers, IDEs, linters, etc.


    Надо использовать mypy или еще какой-то другой инструмент.
    Ответ написан
  • Почему leetcode не принимает правильно решенные задачи на python?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если одна и та же программа работает у вас локально, но падает с ошибкой интерпетации на сервере, то, скорее всего, дело в версии питона. Python 2 и python 3 довольно сильно отличаются. Сравните версии.
    Ответ написан
    1 комментарий
  • Как сделать чтобы нейросеть поняла входные данные?

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

    print(model.predict([image,image2]))

    Втавьте вот в этот код выше перед вызовом predict вывод размеров image и image2.

    Сдается мне, что вы одну картинку как-то на 2 куска порезали и так и скормили сети. Если это не ваш код, то он возможно ожидает на вход картинку 128x64.
    Ответ написан
  • Как оптимизировать код?

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

    Смотрите на ограничания - n и m до 100000. Обычно такой порядок чисел означает, что вам нужно решение за O(n+m) или что-то вроде O(n+m log (n+m)). У вас же решение "в лоб" за O(nm), что никак не ускорить принципиально. Даже переписыванием на си со всякими хитростями вы ускорите его в 10, ну в 100 раз. А вам надо ускорить его в 10000 раз.

    Могу дать подсказки:
    Во-первых, если и там и там есть положительные элементы, то взяв максимальные в двух массивах вы точно получите элемент больше всех a и b. То же, если и там и там есть отрицательные элементы - надо взять два минимальных.

    Остался случай - что если один массив целиком отрицателен, а второй - целиком положителен. Пусть a положителен, а b отрицателен. Что будет, если взять минимальные по модулю элементы и там и там? Посмотрите внимательно - вам дано, что ни одно из чисел не 0. Это поможет.
    Ответ написан
  • Как решить задачу по комбинаторике?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам нужна формула размещений. От использованной формулы сочетаний отличается отсутствием k! в знаменателе.
    Ответ написан
    Комментировать
  • Можно ли изменить массив (объединить слова в нём) до и после определенного слова?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Можно. Для этого можно, например, пройтись циклом по словам формируя список-ответ. Если текущее слово не содержит символ параграфа, то его надо или добавить к списку ответа, или добавить к последнему слову там. Или проще может быть поддерживать переменную с текущим объединением слов. Если слово в списке не соедржит парагафа - добавляйте к переменной. Если встретили прагараф, то добавляйте в ответ переменную и слово с параграфом и отчищайте переменную.
    Ответ написан
    Комментировать
  • Почему неправильно выводит максимальное число?

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

    Можете строчка за строчкой объяснить, что происходит в коде? Я начал, вы дополните в остальных строчках. Сразу должно стать понятно, где ошибка в логике:

    numbers = input().split()               # получаем в numbers массив из отдельных слов в введенной строке
    flag = 0                                # инициализируем счетчик нулем
    for i in range(len(numbers)):           # проходимся по всей длине массива (по всем словам)
        if numbers[i].isdigit() == True:    # Если текущее слово состоит только из цифр (т.е. оно число)
            flag += 1                       # Увеличиваем счетчик
    if flag == len(numbers):                # если все слова в строке - числа
        for i in range(len(numbers)-1):     # ???
            print(numbers[i], numbers[i+1]) # ???
            if numbers[i] < numbers[i+1]:   # ???
                mx = numbers[i+1]           # ???
    print(mx)
    Ответ написан
  • Как ускорить код на Python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Я предполагаю, что условие вашей задачи такое - дано куча запросов вида <начало отрезка, конец, значение>. Все ячейки в этом отрезке заполняются заданным значением, если они меньше его. Надо найти сумму всех ячеек в конце.

    Тут есть два решения. Первое - через дерево отрезков с отложенным изменением. Само дерево немного странное получается, потому что оно ничего не считает в промежуточных вершинах, а будет только хранить отложенное изменение. Физический смысл отложенного изменения - "все ячейки в этом поддереве должны быть не меньше этого значения". Релаксация (спуск вниз) отложенного изменения происходит так: отложенное изменение в детях заменяется на максимум из того, что там лежит и отложенного значения в родителе. Значение в родителе заменяется на 0. При запросе спускайтесь рекурсивно по дереву, релаксируя изменения, пока текущее поддерево не будет целиком лежать в запросе. Тогда перезаписывайте отложенное значение в текущей вершине, если оно меньше. В конце обработки запросов релаксируйте все вершины сверху вниз и просуммируйте значения в листьях.

    Второе решение - через метод сканирующей прямой может быть проще в реализации из-за наличия встроенных структур данных. Я думаю, в питоне должна быть структура, которая умеет быстро добавлять число, удалять число и брать максимум из всех чисел. В C++ есть std::set или std::priority_queue.
    Для каждого отрезка-запроса создайте два события вида <координата, отрезок открылся/закрылся, значение> (разберитесь, где там +-1 поставить так, чтобы длина отрезка по координатам равнялась количеству покрытых ячеек). Засуньте их все в один массив и отсортируйте по координате. Потом проходитесь слева-на-право. Применяйте текущее событие - или добавляйте число в вашу структуру данных, или удаляйте оттуда. Между текущим и следующим событием по координатам все ячейки покрыты одним и тем же множеством отрезков, поэтому можно их все быстро посчитать, ведь ваша структура умеет брать максимум. Добавляйте к ответу разность координат между текущим и следующим событиями, умноженную на значение максимума из структуры. Все.
    Ответ написан
    Комментировать
  • Как решить задачу по математике с помощью python?

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

    Сначала решите уравнение, при какой величине вклада X доход от бумаги и от банковского вклада будет одинаков?

    1.1X+2000 = 1.12X

    До этой суммы выгоднее брать бумагу - после - вклад.
    Далее надо 4 раза взять одно из двух, сравнивая текущую сумму с пороговым значением выше.

    От питона вам надо уметь выполнять действие 4 раза:
    for i in range(0, 4):

    Сравнивать 2 значения и делать в зависимости от этого разные действия.
    if a < b:
      foo
    else:
      bar


    Ну, вряд ли вы не знаете, еще надо уметь присваивать переменные и выполнять арифметику - умножение и сложение.
    Ответ написан
    Комментировать
  • Как называются алгоритмы, который показывает пошаговые изменения в слове?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это про теорию графов и кратчайшие пути. Вам надо найти путь в графе из слов, где ребра есть между словами с одним изменением.
    Ответ написан
    5 комментариев
  • Что определяется в переменной stack в Python3 в случае такой записи stack = [(src, [src])]?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Вам поможет встроенная функция type(). Она описывает тип передаваемого объекта.

    Посмотрите, что выводит type(stack). Потом можно удалять уже понятные части, чтобы смотреть что там внутри.
    Ответ написан
    Комментировать