1

Дан отсортированный массив A длины n (n <= 10) с цифрами, число B (B <= 9), и число C (C <= INT_MAX). Необходимо выяснить, сколько чисел длины B можно составить из цифр массива A таких, что эти числа меньше C.

Например:

A = {0, 1, 4, 7, 8}
B = 2
C = 42

Ответ: 7 (10, 11, 14, 17, 18, 40, 41}

Можно перебирать за O(n^B), но нужно решение с дп, насколько я понимаю.

5
  • Судя по вашему примеру - без повторов? 0 ведущим быть не может?
    – Harry
    15 июл 2017 в 7:16
  • @Harry в числах цифры могут повторяться, в массиве - нет. Т.е. если в массиве указана цифра 1, то мы можем использовать в числах её много раз
    – user258786
    15 июл 2017 в 7:17
  • @Harry 0 ведущим не может
    – user258786
    15 июл 2017 в 7:19
  • 1
    В условии сказано "Необходимо выяснить, сколько...". В ответе примера вдруг приведено не только количество, но ни с того ни с сего вдруг и сами числа перечислены. Так что же надо сделать-то? Определить сколько или вывести все числа? 15 июл 2017 в 9:48
  • Не вижу необходимости для ДП. Для чисел короче C (по количеству разрядов) ответ ясен сразу - там ничего отсеивать не надо и другого алгоритма существовать не может. Для чисел, равных C по количеству разрядов делаем перебор с отсеиванием. Понятно, что и этот перебор не должен быть "тупым" - нет смысла перебирать числа, чей префикс уже заведомо говорит, что они больше C (собственно в этом и заключается отсев). Вот и все. 15 июл 2017 в 9:51

1 ответ 1

3
  • Если B меньше, чем длина C, то ответ задачи вычисляется напрямую: либо n^B, либо (n-1) * n^(B-1) в зависимости от значения A[0] (не ноль или ноль).

    unsigned shorter_length_numbers(const unsigned A[], unsigned n_A, unsigned B)
    {
      unsigned n_numbers = A[0] > 0 ? n_A : n_A - 1;
      n_numbers *= power(n_A, B - 1);
      return n_numbers;
    }
    
  • Если B равно длине C, то задача решается перебором чисел длины B из цифр A. Составляем числа в направлении от старших разрядов к младшим, сразу же отсекая перебор, когда промежуточное число больше или равно C.

    unsigned same_length_numbers(unsigned number, const unsigned A[], unsigned n_A, unsigned n, unsigned C)
    {
      if (n == 0)
        return 1;
    
      unsigned weight = power(10, n - 1);
    
      unsigned n_numbers = 0;
    
      for (unsigned i_A = number > 0 || A[0] > 0 ? 0 : 1; i_A < n_A; ++i_A)
      {
        unsigned next_number = number + weight * A[i_A];
        if (next_number >= C)
          break;
    
        n_numbers += same_length_numbers(next_number, A, n_A, n - 1, C);
      }
    
      return n_numbers;     
    }
    
    unsigned same_length_numbers(const unsigned A[], unsigned n_A, unsigned C)
    {
      return same_length_numbers(0, A, n_A, log10_up(C), C);
    }
    

    Семантика функций log10_up и power, надеюсь, понятна и так.

  • Если B больше, чем длина C, то ответ - 0.

Тот факт, что массив A отсортирован дает нам возможность проверять наличие нуля путем проверки A[0], а также позволяет нам отсекать перебор всех остальных элементов массива в ситуации, когда значение C превышено.

http://coliru.stacked-crooked.com/a/436993e02829c71c

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.