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

Автор dnazirzhanov05, история, 5 лет назад, По-русски

ИНТЕРЕСНЫЕ ЧИСЛА. Назовём натуральное число X (X > 9) "интересным", если цифры в его десятичной записи ненулевые, попарно взаимно простые и их попарные суммы — простые числа. Например, число 114 является интересным, а числа 115, 124 — нет.
Найдите N-ое (1 <= N <= 2018) интересное число. Пример: 3 -> 14

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

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

Напишем простой перебор, который покажет все интересные числа до $$$10^7$$$. Заметим, что все интересные числа либо двузначные, либо удовлетворяют регулярному выражению 1*[1246]1*. Скорее всего, это можно строго доказать, но мне лень(

Руками выкинем все двузначные. Из общего вида интересных чисел следует, что количество интересных чисел длины $$$n$$$ Равно $$$3 \cdot n + 1$$$. Из этой информации вы можете получить длину числа. В вашем случае сработает простой линейный перебор, однако для больших ограничений можно было бы использовать бинпоиск, или даже придумать явную формулу.

Затем осталось понять, какое именно у вас число, если известна его длина. Вы можете его явно перебрать, однако опять же, при больших ограничениях работал бы бинпоиск или явная формула.

Асимптотика решения: $$$O(n)$$$ если все просто перебирать, $$$O(\log{n})$$$, если придумать бинпоиск и $$$O(1)$$$, если придумать формулу.

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

    Строгое доказательство такое. Пусть есть интересное число, в котором больше одной не единичной цифры. Заметим, что если выкидывать цифры из числа, то это на интересность никак не влияет — она не может исчезнуть, только появиться. Будем выкидывать единицы либо пока они есть, либо пока число не станет трехзначным. Если кончились единицы, то будем выкидывать что угодно, пока число не останется трехзначным. Итого мы получили трехзначное интересное число, в котором хотя бы две не единичные цифры, а наш перебор показал, что таких чисел нет, противоречие.

    Аналогичное рассуждение работает, если предположить, что в числе оказалась цифра не из множества $$$[1246]$$$.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      Спасибо большое за вашу помощь.

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

        Я то могу, но какой в этом смысл? Для меня обучающей ценности эта задача не несет — я уже легко умею реализовывать подобное. Если я дам вам свой код, то вы, скорее всего, просто его сдадите в систему, возможно предварительно прочитав, но ничего не запомнив из этого полотна кода.

        Гораздо лучше будет, если вы сами его напишете. Во-первых, я не потрачу свое бесценное время на простую задачу, а во-вторых, вы научитесь ее решать. Поверьте, так будет эффективней.

        Если хотите, могу скинуть код моего перебора. Вот он:

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

          Огромное спасибо! Можете объяснить

          vector p = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};

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

            $$$p[i] = 0$$$, если число $$$i$$$ составное; $$$p[i] = 1$$$, если $$$i$$$ простое.

            UPD. Ошибся, разумеется $$$0$$$ и $$$1$$$ не являются составными числами.

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

              Формально говоря, не так. $$$p[i] = 1$$$, если $$$i$$$ простое, и $$$p[i] = 0$$$ если $$$i$$$ не простое.

              Вообще мне нужна была таблица простых чисел до $$$20$$$, но было очень лень реализовывать Эратосфена, поэтому я ее руками вбил.

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

Можно ссылку на задачу?