Wataru

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

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

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

Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.

Пальцем в небо... Но вы обращаетесь через std::ofstream или используете using namespace std;?

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

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

Проблема не в коде, а в алгоритме. Долго строить всю строку и считать в ней нули.

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

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

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

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

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

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

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

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

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

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

У вас операция присвоения лежит вне функции. Компилятор ждет там декларации переменных, функций, типов, вот это вот все, а у вас там операция. Перенесите присвоение в main().

Если вы хотите структуру инициализировать, то можно пользоваться списком инициализации:

struct {
        int debug;
} config = {1};

Прочитать бинарно не можете? Есть функция 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.

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

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

Вот построили вы автомат. Теперь задача состоит в том, чтобы найти вероятность, что случайный путь в этом автомате длины 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) по вермени и по памяти.

Замкнутой формулы, как в задаче в моей статье я тут не вижу. Может, если бы вероятности всех символов были бы одинаковы, то что-то можно было бы сократить.

Вам просто надо пересечь 3 окружности на плоскости. По "формула пересечения окружностей" гуглится, например, это или это.

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

Алгоритм Ахо-Корасика.

Все ваши ключи складываете в бор, как описано по ссылке. Потом для каждого кортежа выполняйте поиск в строке i[1], если нашли, то добавляйте ваш id в ответ.

Вы очищаете msg_buf в цикле же. На второй итерации у вас msg_buf уже очищен и вы его передаете в realloc и все падает.

Попробуйте после free присвоить msg_buf = NULL.

Это комбинаторика.

Если бы не было ограничения на то, что первый символ не 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.