Wataru

У вас 7 неизвестных и 3 уравнения. Так что однозначно вы найти значения переменных никак не сможете. Но и найти вам надо какую-то сумму. Есть шанс, что как-то комбинируя, складывая, вычитая и домножая левые части этих уравнений можно получить искомую сумму. Иными словами, вам надо вектор (16, 25..100) представить в виде линейной комбинации векторов (1, 2..49), (4, 9..64) и (9, 16..81). Обратите внимание, что там везде получаются суммы трех квадратов равны следующему.

Вам надо подобрать такие 3 коэффициента, что x*n^2 + y(n+1)^2+z(n+2)^2 = (n+3)^2. Для n=1..7. У вас тут квадратные многочлены от n получаются, равны они в 7 точках, так что они должны быть равны вообще при любых n. Значит, вам надо раскрыть скобки, сгрупировать степени n и приравнять к 0 все коэффициенты.

Так вы получите 3 уравнения на 3 переменные x, y, z.
x+y+z=1
2y+4z=6
y+4z=9

Отсюда получается x=1 y=-3 z=3

В итоге получаете 1*1-3*12+3*123 - это ваш ответ.

Зависит от длины n. Если n маленькое то можно прикладывать маску. Байт x содержит 3 ноля в последних битах, если ~x &0x7 == 0x7. Аналогично, сдвигая маску из трех единиц (0x7) можно приложить ко всем позициям.

Если n большое, то надо чтобы было много нулевых байт в массиве подряд. Тут можно использовать SSE инструкции для массового сравнения байт с нулями.

Потом, можно еще распараллелить поиск в несколько потоков. Каждый поток ищет последовательность, начинающаюся в отдельном куске массива.

Ну ведь тут массив же отсортирован. Хоть и с приколом: он сдвинут. Можно тем же бинарным поиском найти, где там "разрыв" происходит, а после у вас 2 отсортированных куска. Или сразу модифицировать бинпоиск.
Представьте, что у вас массив, где сначала идут 1, а потом 0. Можете найти в нем, где 1 переходит в 0?

Или смотрите так: ищите вы x. Взяли значение a[m]. Можете, посмотрев на a[l], a[m], a[r] и x понять, в какой половине лежит x?

Edit: ах, тут числа могут быть одинаковыми. Тогда бинпоиск тут не работает. Ибо может быть тест {1,1,1,2,1,1} - и тут можно 2 в любую позицию поставить. И, если вам надо эту 2 найти, то вам придется просмотреть все числа, иначе вы ее не найдете. Бинпоиск возможен, если первое и последнее числа разные.

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

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

Если же у вас ожидаются интервалы побольше 100, то тут возможно лучше будет вот такое решение:
У вас будет одна глобальная структура-индекс, где вы будете хранить статус буфера (о ней позже). Потоки будут к ней обращатся и просить у нее выделить потоку кусок.
Внутри этой структуры, похоже, придется сделать один глобальный мьютекс.
В качестве самой структуры хорошо подойдет дерево отрезков с отложенным добавлением. Пусть оно будет считать сумму на отрезке. При запросе на выделение вы смотрите, равна ли сумма на запрошенном отрезке 0. Если да, то прибавляете на отрезке 1. Если нет, то возвращаете неудачу и поток должен будет опять обратиться к структуре. При освобождении интервала прибавляйте -1.

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

Как сделать это без спинлоков с деревом отрезков - я не придумал.

Вы правильно поняли, что у вас вершинами в гарфе являются клетка+направление, по которому пришли.
Но раз у вас вот это вершины, то вам и пометки о песещении вершины надо делать в трехмерном массиве. А начальных и финальных вершин у вас по 4 штуки: клетка x 4 направления (на самом деле, начинать достаточно только с 2 направлений, но неважно).

Ага, ДП тут отлично входит. F(n) - ответ на задачу для префикса длины n. Там перебираете длину последней группы x и берете в качесвте ответа max(a[n-x]..a[n-1]) - min(a[n-x]..a[n-1]) + F(n-x). По всем l<=x<=r выбераете максимум. Если n < l, то ответ - минус бесконечность.

Это будет решение за O(n^2). Что-нибудь за O(n log n) я так сходу придумать не могу.

Минимизируйте стоимость строительства самой дорогой построенной предложенной линии.

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

1 2 (2) и 2 3 (1) - максимальная стоимость 2 (max(1,2)).

1 3 (3) - максимальная стоимость 3 max(3). 3 больше 2, значит ответ выше лучше.

Так задача легче, чем с суммой.

Справится. Поиск по словарю с несколькими тысячами слов займет миллисекунду.

int masInt[3][5] - вот такие массивы c фиксированными размерами на самом деле хранятся одним куском и индексацию компилятор вычисляет сам. Это не int**, а int[][5]. Только этот тип нельзя вернуть из функции.

Что бы вернуть именно указатель на указатель, вам надо его так и завести и не забыть выделить по строкам:

int** masInt = new int* [3];
for (int i = 0; i < 3; ++i) {
  masInt[i] = new int[5];
}

Не забудьте только потом удалить все это добро через delete[]:

for (int i = 0; i < 3; ++i) {
  delete[] array[i];
}
delete[] array;

Но вообще, лучше не парить себе мозги и возвращать std::vector<std::array<int,5>>.

Тут не надо никакой многопоточности. Все такие симуляции выполняются в один поток с очередью событий.

Вот в 0 секунд у вас I1..I5 сгенерировали заявки, они пападают в накапители и сразу же из них в каналы. В 3 секунды K1 обработал заявку и свободен. Взял одну из накопителя. В 4 секунды K2 освободился, взял заявку из накопителя. В 5 секунд источники снова сгенерировали заявки... и т.д. Это можно просимулировать.

Реализуется это с помощью приоритетной очереди событий. В нее вы складываете новые события, а в основном цикле достаете оттуда событие с минимальным временем. На c++ это будет что-то вроде:

std::priority_queue<pair<int, Event>, std::vector, std::greater> queue

.

Еще вам надо написать классы для источника, накопителя, блокиратора с условиями (не понял, что это) и накопителя.

Например, источник в момент создания кладет в очередь событие "в 0 секунд я создам заявку". При выполнении этого события, во-первых, создается и кладется в очередь новое событие "в t+5 секунд я создам заявку". Во-вторых, надо посмотреть, куда заявки из этого источника попадают. Если это накопитель, то заявка пихается в него.

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

Класс канала при получении заявки создает событие во время t+время обработки заявки, что он освободится. При вы полнении этого события канал смотрит, к чему он подключен и если там не пустой накопитель, то забирает оттуда первую заявку.

Класс Event должен как-то запоминать какой объект это событие выполняет. А основной цикл должен этот код вызывать (и передавать туда время события).

Есть. Называется python + модуль itertools.

import itertools
import string

def generate_strings(length):
    chars = string.ascii_letters + string.digits
    for item in itertools.product(chars, repeat=length):
        yield "".join(item)

for string in generate_strings(3):
    print(string)

Для 8 символов поменяйте 3 в коде на 8.