Максимально непрерывное достижимое число

Ответ 1

Сбросьте количество цифр для цифр от 0 до m-1. Хешируйте числа, превышающие m, которые состоят из одной повторяющейся цифры.

MCAN привязан наименьшим значением digit, для которого нельзя комбинировать все комбинации этой цифры для заданного digit count (например, X000, X00X, X0XX, XX0X, XXX0, XXXX) или (digit count - 1) в случай нуля (например, для всех комбинаций из четырех цифр, комбинации необходимы только для трех нулей, при нулевом отсчете нуля MCAN равен нулю). Цифры подсчитываются в порядке возрастания.

Примеры:

1. MCAN (10, {4, 1, 5, 2, 0})
   3 is the smallest digit for which a digit-count of one cannot be constructed.
   MCAN = 2

2. MCAN (10, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11})
   2 is the smallest digit for which a digit-count of two cannot be constructed.
   MCAN = 21

3. (from Alma Do Mundo comment below) MCAN (2, {0,0,0,1,1,1})
   1 is the smallest digit for which all combinations for a digit-count of four
   cannot be constructed.
   MCAN = 1110

4. (example from No One in Particular answer) 
   MCAN (2, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111})
   1 is the smallest digit for which all combinations for a digit-count of five
   cannot be constructed.
   MCAN = 10101

Ответ 2

Рекурсивные шаги, которые я сделал:

• Если строка цифр доступна в вашем алфавите, отметьте ее и немедленно верните.
• Если строка цифр имеет длину 1, возвращает отказ
• Разделите строку пополам и попробуйте каждую часть

Это мой код:

$u = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11];

echo ncan($u), "\n"; // 21

// the functions

function satisfy($n, array $u)
{
        if (!empty($u[$n])) { // step 1
                --$u[$n];
                return $u;
        } elseif (strlen($n) == 1) { // step 2
                return false;
        }

        // step 3
        for ($i = 1; $i < strlen($n); ++$i) {
                $u2 = satisfy(substr($n, 0, $i), $u);
                if ($u2 && satisfy(substr($n, $i), $u2)) {
                        return true;
                }
        }

        return false;
}

function is_can($n, $u)
{
        return satisfy($n, $u) !== false;
}

function ncan($u)
{
        $umap = array_reduce($u, function(&$result, $item) {
                @$result[$item]++;
                return $result;
        }, []);
        $i = -1;

        while (is_can($i + 1, $umap)) {
                ++$i;
        }

        return $i;
}

Ответ 3

Вот еще один подход:

1) Постановим множество U относительно обычного численного упорядочения для базы M.
2) Если есть символ между 0 и (M-1), который отсутствует, то это первое число, которое НЕ является MCAN.
3) Найдите первый символ, который имеет наименьшее количество записей в множестве U. Из этого мы имеем верхнюю границу первого числа, которое не является MCAN. Это число будет {xxxx} N раз. Например, если M = 4 и U = {0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3}, то число 333 не является MCAN. Это дает нам нашу верхнюю границу.
4) Итак, если первый элемент множества U, который имеет небольшое число вхождений, является x и имеет C-вхождения, то мы можем четко представлять любое число с C-цифрами. (Так как каждый элемент имеет не менее C записей). 5) Теперь мы спрашиваем, существует ли какое-либо число меньше (C + 1) x, которое не может быть MCAN? Ну, любой (C + 1) цифровой номер может иметь либо (C + 1) того же символа, либо только самое большее (C) того же символа. Поскольку x является минимальным с этапа 3, (C + 1) y для y < x может быть выполнено, и (C) a + b может быть выполнено для любых отдельных a, b, так как они имеют (C) копии по крайней мере.

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

U = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1111,11111111}

Определить c (A, B) = число символов "A" длины "B".

Итак, для нашего примера c (0,1) = 15, c (0,2) = 0, c (0,3) = 0, c (0,4) = 0,... c (1,1) = 3, c (1,2) = 0, c (1,3) = 0, c (1,4) = 1, c (0,5) = 0,..., c (1,8) = 1

Максимальная строка 0, которую мы не можем сделать, равна 16. Максимальная 1 строка, которую мы не можем сделать, также равна 16.
1 = 1
11 = 1 + 1
111 = 1 + 1 + 1
1111 = 1111
11111 = 1 + 1111
111111 = 1 + 1 + 1111
1111111 = 1 + 1 + 1 + 1111
11111111 = 11111111
111111111 = 1 + 11111111
1111111111 = 1 + 1 + 11111111
11111111111 = 1 + 1 + 1 + 11111111
111111111111 = 1111 + 11111111
1111111111111 = 1 + 1111 + 11111111
11111111111111 = 1 + 1 + 1111 + 11111111
111111111111111 = 1 + 1 + 1 + 1111 + 11111111

Но можем ли мы сделать строку 11111101111? Мы не можем, потому что для последней 1 строки (1111) нужен единственный набор из 1 с 4 в строке. Как только мы это сделаем, мы не сможем сделать первую 1 строку (111111), потому что у нас есть только 8 (слишком большой) или 3 1 длины, которые слишком малы.

Итак, для мультисимволов нам нужен другой подход.

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

Теперь нам нужно запустить 1 и подсчитать в базе M. Для каждого номера мы запишем его в базу M, а затем определим, можем ли мы сделать это из нашего множества U. Мы делаем это, используя тот же подход используется в проблеме смены монет: динамическое программирование. (См., Например, http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ для алгоритма.) Единственное отличие состоит в том, что в нашем случае мы имеем только конечное число каждого элемента, а не бесконечное снабжение.

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