Я не уверен, можно ли решить эту задачу, если документ состоит из 97 девяток.
Ещё одна девятка будет в левом столбце таблицы. Какая-нибудь из цифр от 0 до 8 вряд ли встретится 9 раз. Так что девяток будет 98+ число девяток в последней клетке таблицы. Вот и получается:
Если в последней клетке 0 девяток, то в ней число 98+0=98
Если в ней одна девятка, то в ней 98+1=99
Если в ней две девятки, то в ней 98+2=100
Во всех случаях получаем противоречие.
UPD. Задача решается довольно просто.
Пусть у нас уже собрана статистика о числе разных цифр в теле документа (B[0] нулей, B[1] единиц...)
Сразу прибавим к этим числам по единичке, чтобы учесть левый столбик.
Оценим сверху число цифр в правой части таблицы. Например, как S=10*(log_10(B[0]+..+B[9])+2).
Каждая цифра в полном документе встретится не более B[n]+S раз, значит, в правой части таблицы для неё будет число, лежащее от D0[n]=B[n] до D1[n]=B[n]+S.
Прооптимизируем диапазоны D0..D1. Для этого для каждой цифры переберём все числа от D0[n] до D1[n], посмотрим количество разных цифр в каждом из этих чисел, возьмём минимальное и максимальное значение вхождений. Например, если D0[n]=997, D1[n]=1013, то в клетке, соответствующей n, 0,1 и 9 могут встретиться от 0 до 3 раз, а остальные цифры - 0 или 1 раз.
Просуммируем полученные диапазоны по всем n - получим новую таблицу диапазонов D0n,D1n. Пересечём их с D0,D1.
Есть 3 варианта.
Все полученные диапазоны совпали с D0..D1. Выходим из цикла.
Один из новых диапазонов пуст. В этой ветке решений нет, возвращаемся из функции.
Какой-то диапазон изменился. Продолжаем оптимизировать.
После того, как диапазоны стабилизировались, смотрим их длины. Если все они длины 1 (т.е. D0=D1), то мы нашли решение. Если нет - то берём самый короткий диапазон длины больше 1, перебираем все его значения D0[n]<=u<=D1[n], подставляем каждое из них в копию таблицы диапазонов (D0n[n]=D1[n]=u) и рекурсивно вызываем функцию оптимизации.
Перебор оказывается небольшим, вот примеры (ncall - число рекурсивных вызовов):
For 1 2 3 4 5 6 7 8 9 10
0->5 1->7 2->5 3->5 4->6 5->10 6->9 7->10 8->10 9->12
ncall=696
For 1 1 1 0 0 0 0 0 0 0
0->2 1->7 2->5 3->1 4->1 5->2 6->1 7->2 8->1 9->1
ncall=486
For 0 0 0 0 0 0 1 0 0 0
ncall=464
For 0 0 0 0 0 0 0 1 0 0
0->1 1->7 2->2 3->3 4->1 5->1 6->1 7->3 8->1 9->1
0->1 1->6 2->3 3->3 4->1 5->1 6->2 7->2 8->1 9->1
0->1 1->6 2->4 3->1 4->2 5->1 6->2 7->2 8->1 9->1
ncall=482
For 3997 19995 5677 998 799996 392 7 94 8998 99985
0->4014 1->20000 2->5679 3->1000 4->800001 5->394 6->10 7->96 8->9000 9->99994
0->4013 1->20001 2->5679 3->1001 4->800000 5->394 6->10 7->96 8->9000 9->99994
ncall=47356
