Ответы пользователя по тегу Python
  • Как построить граф по его граням?

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

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

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Это получается задача квадратичного программирования. Ищите специализированный метод в scipy. Может вот это сработает.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Посмотрите на ограничения в задаче. Введите вашей программе максимальный тест: 15 монеток и сумму примерно в 1000000000. Ваша программа попробует съесть дюжину гигабайт памяти и упадет.
    Ответ написан
  • Почему 3 секунд не хватает для выполнения кода?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас решениe за O(n^3), ибо у вас там 2 вложенных цикла до n, а внутри еще и постоянно вызываются min/max, которые проходятся по всему массиву.

    Ограничения же в задаче n<10^5. С такими ограничениями максимум O(n log n) решение уложится в 3 секунды.

    Подумайте, как его можно изменить, чтобы работало сильно быстрее? Подсказка: сначала вы берете 1 минимальный элемент, потом 2 самых маленьких, потом 3, и т.д. На второй итерации вам уже как бы не надо искать минимум- вы его уже знаете. Вас интересуют только оставшиеся числа. На третьей итерации у вас уже 2 числа раньше найдены. Надо как-то переиспользовать предыдущие вычисления.

    Что можно сделать с входным массивом, чтобы можно было получать несколько самых маленьких элементов быстро? Помните, что вам надо уложиться в O(n log n).
    Ответ написан
    Комментировать
  • Как сделать, что бы скрипт искал только фиксированное количество слагаемых?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    У вас все равно полный перебор, можно через itertools.combinations перебирать сочетания из заданного количества имеющихся чисел, считать их сумму и, если совпало, выводить. Там всего один цикл, буквально 4 строчки будет решение.

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

    Более хитрые и быстрые варианты: динамическое программирование типа задачи о рюкзаке, где вы считаете количество способов набрать такую-то сумму стольки-то слагаемыми из стольки-то первых чисел. А потом используя это в рекурсивном переборе можно отрубать его тупиковые ветви: если ДП говорит, что там 0 наборов, то можно туда не идти в рекурсии. Или, если вам не сами наборы, а из количество нужно, то даже рекурсивного перебора не надо. Но это работает, только если target не очень большое.

    Второй более быстрый вариант: получить хоть бы и вашим перебором все варианты собрать все суммы среди первых n/2 чисел и отдельно среди оставшихся. Их надо распихать по разным массивам, в зависимости от количества слагаемых. Отсортировать по сумме. Потом перебрать, сколько чисел берем из первой половины, тогда понятно, сколько берем из второй. А потом двумя указателями, идущими навстречу в этих двух упорядоченных массивах можно за один проход найти все способы скомбинировать пару чисел из двух массивов, дающую искомую сумму.
    Ответ написан
  • Удалить из ряда элементы ,как?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Например, вот так:
    def GenerateAll(source, rep):
      for comb in itertools.combinations(range(len(source)), len(source)-len(rep)):
        s = list()
        prev = 0
        for (i, j) in enumerate(comb):
          s.append(source[j]);
        yield "".join(s)


    Обратите внимание, перебираем не сочетания из удаляемых позиций, а из 22 оставляемых (кстати, у вас числа не бьются, 48+22 = 60 != 64). Тут порядок в ответе будет обратный (первая строка будет "xxxxxx...xxxx12..." а не "12..xxx..xx". Если нужен тот же порядок, то будет чуть сложнее:
    def GenerateAll(source, rep):
      for comb in itertools.combinations(range(len(source)), len(rep)):
        s = list()
        prev = 0
        last = 0
        for (i, j) in enumerate(comb):
          while (last < j):
              s.append(source[last]);
              last += 1
          last += 1
        while (last < len(source)):
              s.append(source[last]);
              last += 1
        yield "".join(s)


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

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Все индивидуально. Чего этот sleep в коде ждет?
    Может, тут он ждет отклика от сервера, и там действительно надо 200мс ждать. И просто заменой time sleep на что-то вы ничего не исправите. Или это анимация чего-то на экране, и тут можно в 0 все убирать.

    Но вообще гуглите simulated time python.
    Посмотрите, может simpy вам тут поможет.
    Ответ написан
    1 комментарий
  • Логика игры "Пятнашки" на Python?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Надо, чтобы "четность" перестановки совпадала с четностью финального поля (1).
    Занумеруйте все 16 позиций слева направо сверху вниз.
    чтобы подсчитать четность, рассматривайте каждую пару заполненных позиций (15\*14/2=105 пар) - если числа идут не в том порядке (большее число на позиции с меньшим номером) - то прибавьте 1 к ответу. В конце возьмите ответ по модулю 2. Это и будет четность перестановки.

    Чтобы получить поле, которое можно собрать, сгенерируйте любую перестановку (случайно перемешайте 15 чисел), а потом посчитайте ee четность. Если четность плохая, то поменйте местами любые 2 соседних элемента (выберите случайно, или меняйте первые 2 всегда - на вероятности всех возможных полей это не влияет).

    Edit: Но вы это почти все итак знатете, ибо функция is_solvable в вашем коде как раз инверсии уже считает.
    Значит, Но вы знаете, что плохое поле от хорошего отличается лишь четностью, значит, если поле плохое - меняйте местами 2 соседних по порядку элемента. Например верхний левый со вторым в верхней строке.
    Ответ написан
    Комментировать
  • Как правильно реализовать алгоритм Дейкстры в Python с применением ООП?

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

    Я бы действительно не вводил сущность ребро. И просто в вершинах хранил список соседних вершин (оно еще называется список смежности). Так экономнее, быстрее и проще.

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

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ваш алгоритм работает за O(n^2). Вы для каждого числа в массиве считатете, сколько раз оно туда входит проходя по массиву через nums.count(i). Оптимальное же решение работает O(n). Надо в хеш-таблице подсчитать, сколько раз каждое число встречается, потом через алгоритм QuickSelect выбрать k-ый c конца элемент.

    Ну, или можно за O(n log n) отсортировать массив и потом за один проход подсчитать сколько раз каждое число встречается. Дальше можно второй раз отсортировать по количеству вхождений и выдать k-ый элемент. Это решение тоже пройдет.
    Ответ написан
  • Поиск кратчайшего пути в ориентированном графе с цветными вершинами и дугами?

    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.
    Ответ написан