Wataru

Я, правда, не понимаю, почему нельзя просто объединить все массивы в один (будет просто список уникальных элементов). Возможно вам нужно максимальное количество массивов.

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

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

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

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

Потом пройдитесь по всем элементам каждого входного массива и объединяйте его множество с множеством предыдущего элемента в том же массиве. Попутно, можете считать количество объединений, которые выполнились (множества были различными до выполнения операции union_sets). Так вы можете подсчитать, сколько массивов будет в ответе. В итоге все элементы для каждого массива в ответе будут в одном и том же множестве. Теперь, чтобы вывести ответ заведите массив списков с известным количеством элементов. Используйте ассоциативный массив, чтобы назначить каждому множеству один из списков в ответе. Пройдитесь по всем элементам и дописывайте их в соответствующий список.

Не школьник, но вроде все просто.
У вас есть y = B^x/A
Дано y, отсюда x= log_B(A*y) = ln(A*y) / ln(B).

Надо будет округлить. Формула может давать сбои на мелких числах.

Ответ - количество сочетаний по n-1 из (n+m-2), или сколько способов выбрать n-1 объект из n+m-2.

Это потому что нужно обязательно сделать n-1 шагов вниз и m-1 шагов вправо. Вопрос только, в каком порядке их делать. Всего будет сделано n-1+m-1 шагов и из них надо выбрать какие-то n-1 вниз, остальные будут шаги вправо. Вот и получаются сочетания.

Можно считать треугольником Паскаля, получится в точности то же, что описал poznavaka,
можно считать по формуле факториалов: (n+m-2)! / (n-1)! / (m-1)!

Для вашего примера, где N=3 и M=4 ответ будет 5!/2!/3! = 120/2/6 = 10.

Ваш алгоритм надо лишь немного доработать.

1) найти ближайший сверху (слева/снизу/справа) из тех, которые имеют перекрытие.
2) повторить операцию, найдя следующий сверху. Расстояние между ними взять за d.
3) продолжить идти вверх. Если следующий ближайший тоже на расстоянии d - нарисовать промежуток. Если нет, то остановится.
4) Зная ближайший прямоугольник из пункта 1) и расстояние d - можно его отступить вниз и у вас есть точка примагничивания.

Можно ускорить алгоритм немного. Сначала за один проход выделите все прямоугольники, которые выше данного, но пересекаются с ним по оси X. Отсортируйте их снизу вверх по нижней границе. Теперь в пунктах 1,2,3 надо рассматривать только один следующий прямоугольник из списка.

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

Что бы ускорить еще больше, когда у вас очень много прямоугольников на экране, можно хранить их в quad tree и из него вытаскивать прямоугольники, которые перекрываются с заданным и выше его уже в правильном порядке. Но скорее всего просто пройтись по списку всех прямоугольников будет достаточно.

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