• Python массивы не пашет нужна помощь, что делать?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    У вас массив интов создается:
    massive = array('i', [])

    А пихаете вы туда символ:
    massive.append(random.choice(string.ascii_letters))


    О чем вам интерпретатор и говорит:
    TypeError: an integer is required (got type str)
    Ответ написан
  • Что это такое в решении предела (lim)?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Это они просто вынесли за скобки максимальную степень x отдельно в числителе и знаменателе.
    Ответ написан
  • Как работают классы в Python?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    https://docs.python.org/3/tutorial/classes.html#cl... - инструкции внутри class выполняются один раз.
    Обычно там пишут определения методов и членов класса. Точно так же, как у вас в коде ниже написано определение функции test_def. Определение всегда выполняется.
    Ответ написан
  • Как решить задачу по комбинаторике (объекты не стояли рядом)?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Что значит, "остальные попарно разные"? Если интерпретировать эту задачу так, что есть 3 кубика первого цвета, а остальные 9 имеют цвета со второго по десятый (все различные), то получается задача подсчитать, сколько способов не поставить 3 первых кубика рядом. Тут работает формула включения исключения.

    Сначала считаем вообще все способы расстановки - это 12!/3! (сначала ставим все 12 кубиков как получится, но порядок у трех одинаковых не важен, поэтому делим на 3!).

    Потом, что если 2 кубика стоят рядом? Из можно "слить" в один новый кубик. Будет 11!/2! вариантов. Это надо вычесть.

    Но вариант с тремя кубиками подряд мы вычли 2 раза. Прибавляем 10! назад.
    Ответ написан
  • Как составить массив из чётных элементов матрицы на Python?

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

    edit:
    А еще у вас при обходе матрицы только один цикл. А надо так же как при вводе делать двумя вложенными циклами.
    Ответ написан
  • Как максимально оптимизировать код Python?

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

    Есть вот такая формула. Для каждого простого числа можно опредерить степень просто деля n (не факториал!) на это простое число нацело, пока не получится 0 и суммировать все результаты.

    Но это работет только для простых чисел. Т.е. чтобы узнать, в какой степени число 10 входит в N! (или сколько нулей на конце в деситичной записи) надо узнать, сколько раз 2 и 5 входят в N! и взять минимум.

    Т.е. надо разложить k на простые множители, для каждого простого множителя подсчитать, сколько раз он входит в n! по формле выше. Потом поделить это на степень простого числа в k, и по всем делителям k взять минимум.
    Ответ написан
  • Как разложить полигон на дерево вершин?

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

    В случае с трассировкой лучей, за логарифм нет реализации вообще - ибо у невыпуклого многоугольника может быть O(n) пересечений с лучем (представьте себе пилу).

    В случае с ближайшей точкой - если и есть структура, то это то-то вроде trapezoidal map - это такая мозговыносящая штука, что не советую о ней даже думать. Нужно разбить пространство на области, ближайшие к каждой стороне.

    За логарифм есть решение через бинарный поиск.
    Разбейте пространство на вертикальные колонны всеми x координатами всех вершин многоугольника. Внутри каждой из них будет проходить четное количество сторон. Составьте для каждой стороны уравнение и отсортируйте их по высоте.

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

    Проблема этого метода, что он требует O(n^2) памяти в худшем случае и такую же предобработку.
    Но, для выпуклых многоугольников, прямых в каждой колонне будет всего две. Вот описание метода с реализацией для этого упрощенного случая.
    Ответ написан
  • Как разложить число на множители(си)?

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


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

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Возьмите для каждого товара набор точек {день, показатель} за сколько-то последних дней. Постройте линейную регрессию. Наклон прямой (т.е. коэффициент перед номером дня) и будет этим показателем динамики.
    Ответ написан
  • Не компилируется код?

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

    Если вы хотите структуру инициализировать, то можно пользоваться списком инициализации:
    struct {
            int debug;
    } config = {1};
    Ответ написан
  • Как найти полусумму 32-битных знаковых чисел?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Прочитать бинарно не можете? Есть функция read.

    Читайте ей по 4 байта 2 раза в char buf[4].

    little-endian означает, что сначала идут самые минимальные байты. Т.е. buf[0] - это младшие 8 бит числа, buf[3] - старшие. Для собирания числа воедино смотрите на операцию сдвига. (int)buf[3] << 24 | (int)buf[2] << 16 поставит на место 2 старших байта (младшие додумайте сами).

    Тип 64-х битных чисел - long long. Вам в условии посоветовали им пользоваться.

    Сложить 2 числа сами сможете?

    Бинарный вывод делается, внезапно функцией write.

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

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Тут надо построить конечный автомат, который принимает строки, которые кончаются на заданную строку. Посмотрите эту статью, там в начале расписан этот автомат (секции перфикс функция - атомат КМП).

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

    Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины n пройдет через конечное состояние ровно один раз. Для этого подсчитайте 2 вероятности: что путь из начала длины k дойдет до конечного состояния один раз, и что путь из конечного состояния длины n-k не вернется в него.

    Обе эти вероятности можно подсчитать динамическим программированием:
    P1(i, k) - вероятность того, что путь начиная с состояния i (i < n) за k шагов дойдет до состояния n первый раз. Это просто сумма по всем возможным переходам:

    P1(i, k) = sum_{c - все символы} P1(next(i, c), k-1) * p(c)

    База:
    P1(m, 0) = 1
    P1(m, k>0) = 0
    P1(i < m, 0) = 0


    Вторая вероятность: сделать k шаговиз состояния i и ни разу не войти в конечное состояние:
    P2(i, k) = sum_{c - все символы, next(i,c) < m} P2(next(i, c), k-1) * p(c)


    База:
    P1(i, 0) = 1

    Ответ к задаче - сумма по всем возможным длинам первой части пути:
    sum_{k=m..n} P1(0, k) * P2(m, n-k)

    Это решение через динамическое программирование будет O(n*m) по вермени и по памяти.

    Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.
    Ответ написан
  • Как получить координаты точки, если известны координаты трёх других точек и расстояние от этих точек до искомой точки?

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

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

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

    Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.
    Ответ написан
  • Как построить функцию декодирования классического кода Элиаса, если прямое кодирование работает правильно?

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

    И читайте это:
    1) подсчитайте сколько нулей идет в начале строки.
    2) Это сколько бит надо прочитать дальше и перевести в десятичную систему счисления.
    3) Это столько бит, сколько нужно прочитать дальше и перевести в десятичную систему, чтобы раскодировать число.
    Ответ написан
  • Как сортировать массив с рандомными значениями?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    for(d=0; d < n; d++)
      x[i] = rand();
     printf("%d", x[i]);


    Цикл по d а присваивание в x[i]. Еще скобок нет, printf выполнится только один раз после цикла.

    Еще вы не выводите массив после сортировки, как вы вообще собираетесь понимать, что ваша программа работает?

    В самой сортировке (циклы по i и j), вроде, ошибок нет.
    Ответ написан
  • Почему после очистки строки программа падает?

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

    Попробуйте после free присвоить msg_buf = NULL.
    Ответ написан
  • Как найти количество перестановок числа?

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

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

    Еще, в вашей формуле направшивается добавить пустое число ("") в ответ. Давайте разрешим его и вычтем в конце 1.

    Еще, очевидно, результат зависит только от количества каждой цифры в исходном числе, но не от их порядка.

    Поэтому пусть f(a0,a1,...a9) - сколько есть способов расставить некторые из a0 нулей, a1 единиц, a2 двоек, и т.д. (ноль может идти в начале, число может быть пустым).

    Ответ к задаче f(a0,a1,...a9)-1-min(a0,1)*f(a0-1,a1,...a9). Последнее слагаемое считает варианты, начинающиеся с нуля. Оно не вычитается, если нулей в числе нет. -1 посередине вычитает пустое число из ответа (но ее нет в последнем слагаемом, ведь мы там еще 0 в начале приписываем и пустое число надо считать).

    Теперь самое интересное, формула для f(a0,a1,...a9). Замкнутой формулы я не нашел, но придумал, как считать алгоритмом.

    Можно все варинаты разделить по количеству символов в числе (n), от 0 до суммы a0...a9. Давайте подумаем, где могуть быть девятки? i <= a9 из них попадут в ответ. Они могут быть на C(n, i) позициях. Останется разместить остальные цифры на n-i позиций.

    Вырисовывается следующее динамическое программирование:

    F(i, n) - сколько способов разместить первые i цифр на n позициях (возможно, беря не все цифры).

    F(i,n) = sum (j=0..min(a[i-1], n)) F(i-1, n-j)*C(n, j)
    F(0, n>0) = 0
    F(i,0) = 1.
    Ответ - sum(k=0..a0+...+a9) F(9, k)

    У функции как бы неявный параметр массив a[] количеств всех цифр, но я его не включаю в параметры динамики, потому что по нему не надо мемоизировать.

    Не забудьте, что для подсчета второй динамики, для f(a0-1,...a9) надо будет полностью отчистить мемеоизацию, потому что массив a поменялся же.

    Этот алгоритм работает за O(9*n), где n - длина входного числа.

    Вот пример для входного числа 112: все цифры, которых в числе нет можно выкинуть из рассмотрения и работать с массивом a={2,1} (для всех десяти цифр слишком много писать).

    F(0,0) = 1
    F(0,1) = 0
    F(0,2) = 0
    F(0,3) = 0
    F(1, 0) = 1
    F(1,1) = F(0, 1)*C(1,0) + F(0,0)*C(1,1) = 1
    F(1,2) = F(0,2)*C(2, 0)+ F(0,1)*C(2,1) + F(0,0)*C(2,2) = 1
    F(1,3) = F(0,3)*C(3, 0)+ F(0,2)*C(3,1) + F(0,1)*C(3,2) = 0
    F(2,0) = 1
    F(2,1) = F(1,1)*C(1, 0) + F(1,0)*C(1,1) = 2
    F(2,2) = F(1,2)*C(2, 0) + F(1,1)*C(2,1) = 3
    F(2,3) = F(1,3)*C(3, 0) + F(1,2)*C(3,1) = 3

    Ответ F(2,3)+F(2,2)+F(2,1)+F(2,0) = 3+3+2+1= 9.

    Вычитаем 1 (пустое число) и получаем 8 чисел, как у вас в примере для 112.
    Ответ написан
  • Правильноли решена данная задача?

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

    Почему у вас в ответе перемешаны C и A? Какой физический смысл?

    Ответ C(2,20)*C(3,18)*c(3,15)*c(3,12)*...*C(3,3)/6!

    Смысл - берем 2 любых вопроса, которые не попадают в 18 из билетов. Потом берем три из 18, которые идут в первый билет, потом 3 из оставшихся 15, которые идут во второй билет... и так далее. В конце делим на 6!, потому что порядок билетов, похоже, не имеет значения.
    Ответ написан
  • Как объяснит задачу по комбинаторике?

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

    Потом, все варианты различаются тем, какие 2 студента эту тему выучат. Это множитель С(2,6).

    Далее, эти 2 студента должны выучить еще по одной теме. Это выбрать 2 темы из оставшихся 10-ти. Но тут порядок важен, ведь это разные темы у разных студентов. Это множитель A(10,2).

    Что осталось? 8 не выученных тем и 4 студента. Тут есть известная формула обобщенных сочетаний или сочетаний из нескольких цветов (не помню точное название). Всего таких комбинаций будет 8!/(2!*2!*2!*2!). Эту же формулу можно получить если последовательно выбирать по 2 темы для каждого из четырех студентов. Первый может взять темы C(2,8) вариантами. Второй из оставшихся 6-ти тем C(2,6) вариантами и аналогично для третьего и четвертого студентов (C(2,4) и C(2,2)).
    Ответ написан