Блог пользователя josdas

Автор josdas, 10 лет назад, По-русски

Дан массив натуральных чисел а ( MAX_A <= 105 ) длинны n ( n  <  =  30). Необходимо ответить для какого количества натуральных С невозможно подобрать набор t являющийся решением уравнения , где ti целое число и ti >= 0. Гарантируется что ответ конечный.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если в массиве А есть два взаимно простых числа m и n, то для любого числа z, большего чем mn существуют такие неотрицательные x, y, что z = xm + yn. Таким образом, можно считать, что если в А есть два взаимно простых, то все числа, большие 1010 представимы таким образом. Ну а для меньших как-то перебрать по-умному надо:)

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    С перебором проблема. Рюкзак очевидно не зайдет, а что то другое не могу придумать.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Двух взаимно простых может и не быть. Пример {2 * 3, 2 * 5, 5 * 3}. Не могу для такого случая понять оценку на количество непредставимых.

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      6 + 10 = 16, теперь есть взаимно простые 16 и 15

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

Пусть дано число C и требуется проверить можно ли его представить.

Можно устроить проверку так: выбрать любое ai (например, a0) и проверить, можно ли из C вычитать остальные числа так, чтобы получился 0 по модулю a0. Понятно, что ответ зависит от остатка C при делении на a0, при этом надо, чтобы при вычитании не получилось в конце концов отрицательного числа. Таким образом, можно посчитать такую динамику: dp[x] — какое минимальную комбинацию ai-х можно вычесть из числа, у которого остаток x по модулю a0, так, чтобы получился 0 по модулю a0.

Проверка будет выглядеть так: [0  ≤  C — dp[C % a0 ]].

Таким образом, можно для каждого остатка найти минимальное число, начиная с которого числа с таким остатком представимы.

Стресс до 105: http://www.everfall.com/paste/id.php?0hnbvd2rto20