Решение задачи о количестве клеток с суммой цифр координат меньше заданного числа / Comments / Habr

nezhi Sep 6 at 20:25

Вкратце алгоритм такой:

Рассчитываются все возможные варианты области 10*10 с координатами (0;0)-(9;9)

Потом из этих кирпичиков рассчитываются все возможные варианты для области 100*100

И так далее каждый раз увеличивая размер области в 10*10 раз

Dimonogen Sep 7 at 05:49

Вот интересно, если рисунок и узор повторяется, нельзя ли вывести аналитическую формулу?

nezhi Sep 7 at 08:35

Можно попробовать. Но мне кажется будет сложно. Если бы чистая область была больше, было бы проще. Тогда можно было бы обсчитывать недоступные клетки на краю. Проблема в том, что при N=1800 например, при максимально доступной координате из двухсот девяток недоступные клетки будут начинаться в квадрате со стороной в сто девяток, что на сто порядков меньше максимальной координаты и помощи от внутренней пустой области нет.

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

lightln2 Sep 7 at 15:11

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

lightln2 Sep 7 at 15:42

Спасибо, интересная задача!
Я немного подумал над ней, но в комментариях хабра мало места, чтобы подробно написать. Примерно так получилось (рассуждения, в принципе, повторяют ваши, но только в более привычных обозначениях):
Во-первых, возьмем основание системы счисления произвольное b вместо 10, мне так формулы легче воспринимаются. Для положительных x обозначим сумму цифр
Теперь сначала рассмотрим одномерный случай: посчитаем количество таких x, что $d(y, b) \le n$ для всех $0 \le y \le abs(x)$ , будем называть такие числа достижимыми (из нуля).
Для этого введем две функции: - количество достижимых чисел в отрезке и , равная единице, если сумма цифр последнего числа в отрезке не превосходит n, иначе нулю. То есть, она говорит, можем ли мы продолжать смотреть следующие отрезки, или надо остановиться.
Тогда f и q можно выразить такими формулами:

$q(n, k) = 1 \ if \ n \ge k(b-1) \ else \ 0$ $f(n, k) = f(n, k-1) + \sum_{x=1}^{b-1} f(n-x, k-1) q(n-x+1, k-1)$

Теперь точно так же рассмотрим двумерный случай. Удивительно, что условие на то, надо ли нам рассматривать следующий квадрат или нет, сводится к той же самой функции q (не зависящей от размерности!). Я строго не смог доказать это, но там должны быть примерно ваши рассуждения. Для двумерной f формула почти такая же:

$f(n, k) = f(n, k-1) + \sum_{1 \le x, y < b-1 , (x,y) \ne (0,0)} f(n-x-y, k-1)q(n-x-y+1, k-1)$

Или можно ее сократить до одной суммы, если взять diag(t) равной количеству пар x, y в квадрате bxb, в сумме не превосходящих t:

$f(n, k) = f(n, k-1) + \sum_{t=1}^{2b-1} diag(t) f(n-t, k-1) q(n-t+1, k-1)$

Теперь, имея одномерную и двумерную функции, можно получить ответ по принципу inclusion-exclusion.
Что касается кода, то проверить правильность результата можно обычным поиском (в глубину или ширину, неважно): код на питоне

Вычислить сразу все решения до заданного n можно по этой рекуррентной формуле: код на питоне, вроде бы результаты совпадают с вашими c b=10, N=900.

Сложность алгоритма O(n^2 * b), так как надо итерировать f до значений k=O(n).

lightln2 Sep 8 at 02:03

Это, конечно, баловство, но я уместил решение в восемь строчек на питоне! Тут смысла не очень много, это просто формальное преобразование ранее полученных формул с целью уменьшения количества кода.

def cnt(N, b):
    f1, f2 = [1]*N, [1]*N
    for k in range(1, N//(b-1) + 2):
        for n in reversed(range(N)):
            f1[n] += sum(f1[n - min(b-1, n, n+1-(k-1)*(b-1)) : n])
            for t in range(1, min(2*b-1, n+1, n+2-(k-1)*(b-1))):
                f2[n] += (b - abs(b-1-t))*f2[n-t]
    return [f2[i] * 4 - f1[i] * 4 + 1 for i in range(N)]

Решение задачи о количестве клеток с суммой цифр координат меньше заданного числа

Comments 6

Articles