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 that you have read and understand our privacy policy and code of conduct.

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