Wataru

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

Немного оффтоп. Для каждого фиксированного i не надо перебирать все j, в поисках того, где i*j=n. Достаточно проверить, что n делится на i без остатка: if (n%i == 0). Тогда j = n/i. Не будет никакого переполнения, которое, как вам longclaps уже ответил(а) привеодит к неверным результатам.

Еще вариант - можно гнать оба цикла до ceil(sqrt(n)). И выводить сразу 2 пары (i,j) и (j,i), если i!=j. потому что из двух множителей хотя бы один не больше корня n, иначе бы перемножение было бы больше n. И еще отдельно надо вывести варианты (1, n) И (n, 1).

Надо для каждой вершины хранить предыдущую. Запишите это значение, когда кладете вершину в очередь. Для вершины (row, col) у вас в коде предыдущая (pt.x, pt.y).

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

Обычная динамическое программирование работает для повторяющихся чисел, тут не должно быть проблем. Отрицательные числа решаются просто - считаете все возможные суммы только положительных чисел стандартной динамикой и отдельно только для отрицательных чисел (опустив знак). Потом одним циклом перебираете сумму положительных чисел x>=S и смотрите, если x-S можно набрать отрицательными числами. На общую сложность этот цикл не влияет.

Так же как со временной сложностью - количеством операций. Только считайте количество используемых байт.

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

Получаете какую-то формулу типа 10*n+16*m+n*m/2 + 100500*log n. Дальше применяете ассимптотический анализ.

Например, алгоритм DFS. есть граф с n вершинами и m ребрами. Пусть задан в виде списков инцидентности.

Тогда у вас есть n списков, которые все вместе содержат m элементов. Т.е. ваши входные данные занимают n*8+m(4+8) байт. n указателей на начало списка и m элементов - каждый содержит значение и указатель. Но не надо так считать досканально каждый байт, можно просто прикинуть n+m.

Сам алгоритм еще требует массива для пометок пройденных вершин: +n к потреблению памяти.

Функция требует сколько-то локальных переменных и параметров. Их несколько и от n или m это не зависит. В рекурсии функция может выть вызвана n раз, если вы все вершины пройдете вглубь. Итого на стеке эти функции съедят n*C, где С - какая-то константа.

Суммарная пространственная сложность n+m+n*C. Или O(n+m).

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

Доказательство по индукции. Для одной или двух вершин всегда будет 1 в D.

Пусть degree(v) - количество вершин, инцидентных v.
Лемма: В турнире с n вершинами будет хотя бы одна с degree() >= (n-1)/2. Иначе, просуммируем все degree().
С одной стороны, сумма будет равна количеству ребер, т.е. n(n-1)/2. С другой, эта сумма < n*(n-1)/2 по предполоджению. Противоречие, значит существует v: degree(v) >= (n-1)/2

Теперь докажем основное утверждение.
Рассмотрим турнир с n>2 вершинами. Там есть хотя бы одна v: degree(v) >= (n-1)/2. Включим ее в D. и удалим из графа ее и все, которым она инцедентна. Мы удалили из графа не меньше 1+(n-1)/2 вершин, фактически уполовинив количество вершин в графе. По индукционному предположению там надо log(n/2) вершин в доминирующем множестве. Иы добавили к ней 1. Поэтому в итоге нам надо log(n) вершин и для этого графа.

Это же доказательство можно использовать для построения D - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.

Динамическое программирование:
F(a,b,r) = может ли число составленное из a едениц и b нулей давать остаток r при делении на N.
База: F(0,0,0) = true, F(0,0,r) = false.

Пересчет: Итеративный пересчет такой - F(a,b,r) => то F(a+1,b,(2*r+1) % N) и F(a,b+1,(2*r+1) % N) Тут мы знаем, что есть число, дающее остаток r из a едениц и b нулей. Если мы к нему припишем в конец 1, то остаток будет (2*r+1)%N, а единиц будет на одну больше. Также почти можно приписать 0.

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

Теперь можно найти x такое, что 2x = 1 (mod N) - обратное к 2 по модулю N. Смотрите расширенный алгоритм Эвклида для этого.

Дальше можно вычислять так (N - нечетное):
F(a,b,r) = F(a-1,b, (r-1)*x % N) || F(a, b-1, r*x % N).

Объяснение тут тоже простое - число или оканчивается на 0 или на 1. Попробуем оба варианта и сотрем последнюю цифру. Оставшееся число должно давать остаток (r-1)*x % N или r*x % N соответственно.

Ответ: Если F(A,B,0) - true, то число делящееся на N есть. Для нахождения числа надо дополнительно запоминать, какие цифры приписывались к чисам при рассчетах выше.

Нужно реализовать алгоритм разбиения плоскости на области.
1) Представить стены в виде графа, где вершины - углы и пересечения стен, а ребра - самы стены.
2) Каждое ребро превратить в 2 ориентированных ребра в обе стороны. При этом надо для каждого ребра сохранить ссылку на обратное ребро.
3) В каждой вершине упорядочить все ребра по углу наклона (допустим, по часовой стрелке) и для каждого ребра хранить ссылку на следующее (зацикленно, т.е. для последнего ребра храним ссылку на первое).
4) Теперь будем выделять замкнутые области. Для этого возьмем любое необработанное пока ориентированное ребро. Потом будем от него переходить к следующему ребру в границе области. Для этого сначала получаем обратное к данному ребру. Потом переходим к следующему по углу наклона ребру, исходящему из той же вершины. Помечаем это ребро обработанным. Продалжаем, пока не вернемся к изначальному ребру (обязательно вернемся к нему). Фактически тут мы идем вдоль ребер и каждый раз в вершине максимально поворачиваем по часовой стрелке (или против, зависит от того, как сортировать ребра в вершинах).

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

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

2 варианта:
1) сделать новый массив с pair, записать туда элементы с двух массивов, отсортировать.
2) завести новый массив, забить его числами от 0 до n-1. Передать sort свою функцию сортировки, которая сравнивает не переданные числа a и b, а элементы перовго массива по этим индексам (array1[a] и array1[b]). После полученый набор индексов использовать для вывода второго массива (если сортировали массив indices, то выводите array2[indices[i]], для i от 0 до n-1).

Во первых, определите, что линии лежат на одной плоскости и не паралельны.
Обозначим точки первой прямой как A1 и B1, а второй - A2 и B2.

Введем вектора D1 = B1-A1 и D2 = B2-A2. Введем векторное уравнение.

D1*t + D2*r + (A1-A2) = 0.

Тут 2 неизвестные t и r, 3 уравнения (расписать по x, y и z).

Если система уравнений решается, то точка пересечения A1+D1*t или A2 - D2*r.

Тут правда предется повозиться со случаями. Надо попробовать решить систуму только для x, y, потом проверить в z. Если не получилось, то еще надо попробовать решить в x, z, потом поробовать подставить полученные r и t в у.

В коде ошибка. Прибавлять к sum надо делитель а не 1 каждый раз (sum=sum+i, а не +1).
Во вторых, можно цикл гнать до n/2 (включительно) а не до n. В блок-схеме у вас так и написано, но в коде не так.

Еще совет - начните if с новой строки после цикла. То как у вас if на той же строке что и закрывающая скобка от for - очень путает. И заодно, добавьте отступы внутри if внутри for (строка с прибавлением к sum).

Вот пример такого хеша:

int hash(string s) {
  return 42;
}

Можно вместо 42 возвращать другое число, но обязательно, всегда одно и то же.
Это все потому, что множества слов с ошибками перекрываются. Например, строки "aaaa" и "aabb" должны давать одинаковый хеш. Но точно так же сроки "bbbb" и "aabb" должны давать одинаковый хеш. В итоге получается, что все возможные строки должны давать одинаковый хеш.

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

Или можно сравнивать строки парами, считая сколько нужно ошибок, чтоб получить из одной строки другую. Это стандартное динамическое программирование. Гуглите дистанцию редактирования.

Ограничения небольшие - проще всего тупо перебрать все числа до 23 миллионов, перевести каждое в число и проверить на соответствие условию. Можно чуть ускорить проверки, если считать сумму цифр и количество '5' в подстроке быстро с помощью частичных сумм (считаете, сумму и количество цифр 5 в каждом префиксе строки. Потом вычитаете из значений для одного префикса значения более короткого - остаются значения для подстроки).

Ну, массив строиться очень просто - сначала ставите туда N1 значений s1, потом N2 Значений s2 и т.д.
Что-то вроде такого:

vector<int> a(100);
for (int i = 0, cur = 0; i < k; ++i ) {
  for (int j = 0; j < n[i]; j++) {
    a[cur++] = i;
  }
}

Правда он будет вида {'s1', 's1', 's1', ... 's2', 's2',...]. Если это недопустимо, массив можно перемешать:

for (int i = 1; i < 100; i++) {
   int j = rand() % (i+1);
   swap(a[i], a[j]);
}