Предлагаю порешать в кругу прекрасных дам-программистов традиционную новогоднюю задачу про 2016 год. Надо расставить знаки и скобки, чтобы получилось любое число от 1 до 100.
Например
20*(-1+6)=100

Или
2+0-1^6=1

Факториалы и степени милостиво допускаются.

Комментарии (68)


  1. OlegFX
    31.12.2015 22:15
    +3

    Чёрт, сначала порешал, а только потом заметил, что:

    прекрасных дам-программистов


  1. Hellsy22
    31.12.2015 22:23
    +1

    Я не дама-программист, но все равно с удовольствием потягаюсь с кем-нибудь.
    Шаг первый — набросал простенькую программку в двадцать строк — получил 151 ответ даже без скобок и факториалов.

    -2-0-1+6 == 3
    -2-0+1+6 == 5
    -2-0+1*6 == 4
    -2-0**1+6 == 4
    +2-0/1/6 == 2
    +20/1+6 == 26
    201/6 == 33.5
    +2/01*6 == 12

    и т.д. Кто даст больше?


    1. PatientZero
      31.12.2015 23:07
      -1

      33.5 не проходит условия


      1. Hellsy22
        31.12.2015 23:15
        +6

        33.5 это число лежащее в пределах 1 — 100. В условии ничего не сказано про целые числа.


        1. Keyten
          01.01.2016 03:07
          +1

          любое число от 1 до 100

          Как насчёт длины полукруга радиусом 1?


          1. hacklex
            01.01.2016 11:47
            +12

            Я, конечно, понимаю, что совсем всё, скорее всего, и не получится, но…
            image


            1. hacklex
              01.01.2016 11:59
              +14

              Или, для любителей комплексных чисел,
              image


            1. ooprizrakoo
              01.01.2016 18:58
              +1

              можно использовать спец.символы :)
              ? = arctg(2°) * v16 — это можно скопировать мышкой 8)

              просто к слову: пять лет назад я здесь на хабре написал, как сделал charmap.ru — онлайновую таблицу специальных символов :)


            1. mihaild
              01.01.2016 21:02
              +4

              Всё очевидно не получится. Т.к. алфавит конечен, то формул не более чем счетно. А чисел континуум)


              1. hacklex
                01.01.2016 21:33
                -1

                del


              1. ankh1989
                02.01.2016 10:06

                И вправду. Поэтому разумно потребовать в задаче найти все рациональные числа.


                1. hacklex
                  02.01.2016 11:21

                  Учитывая, что все рациональные числа – это все дроби с целым числителем и натуральным знаменателем, и что ниже для всех целых решение уже нашлось, все рациональные тоже могут и найтись… было бы весело.


              1. SkidanovAlex
                02.01.2016 23:25
                -1

                Это не доказательство, потому что вкладывать буквенные функции можно бесконечно много.


                1. Mrrl
                  03.01.2016 00:03
                  +1

                  У каждой конкретной формулы длина конечна. И глубина вложенности конечна. Поэтому общее количество формул счётно.


                  1. SkidanovAlex
                    03.01.2016 03:37

                    Я потому что читал очень внимательно, и подумал, что речь идет о целых числах.


    1. PapaBubaDiop
      31.12.2015 23:34

      11 как получилось?


      1. jzha
        01.01.2016 10:47
        +2

        Забавная задача, спасибо!
        Для 11 можно так (2 + 0!)! -1 + 6


        1. hacklex
          01.01.2016 11:37
          +1

          Или так:
          image


          1. jzha
            01.01.2016 13:07
            +1

            Хм, а почему можно использовать степень 0.5 вне числа 2016?
            Иначе голову ломать нечего — ясно, что для любого числа N > 0 всегда найдется x: (2016)^x = N.


            1. hacklex
              01.01.2016 15:50
              +3

              Потому что радикал можно использовать без явного указания степени. Я честно расставил только значки, не прибегая к цифрам. Задача-то на перебор на синтаксическом уровне, семантику не затрагивает. Есть унарная операция sqrt? Отлично, берём.

              А если уж решать совсем в кругу программистов, то можно и до читерства с побитовыми операциями дойти. В постановке задачи, к сожалению, не прозвучал конкретный, исчерпывающий базис допустимых операций. В результате можно спорить о допустимости радикалов, о том, общепринято ли ~ в качестве bitwise not, и так далее.


              1. jzha
                01.01.2016 18:51
                +2

                Ясно. Да, базис допустимых операций не задан.
                Для меня sqrt скорее функция одного аргумента, а не унарная операция. В таком контексте можно не ограничивать полет фантазии :)
                Например, добавление к вашим замечательным примерам 2016 -> пи для поклонников Гаусса и Эйлера


            1. khim
              01.01.2016 17:18
              +3

              Этим задачкам больше лет, чем мне. Раньше «Наука и Жизнь» их каждый год публиковала. Корень в этих задачах обычно использовать допускается. Равно как и целую часть. А вот условие «любое число от 1 до 100» как раз новое и странное: обычно требовалось порождать все целые числа по порядку и победителем становился тот, кто добирался до наибольшего числа. В обзорах обычно «каверзные числа» потом публиковались, на которых «застряли» большинство участников.

              Понятно что появление мощных компьютеров свело ценность этой задачи к нулю. Как задачка для собеседования — она ещё годится, но на конкурс — уже нет. Где-то в начале XXI века конкурс прекратили…


              1. Mrrl
                01.01.2016 17:58

                Про целую часть не помню. Комбинациями корня, факториала и целой части можно, вероятно, из одной тройки получить любое число (хотя придётся слишком долго считать). А вот десятичная и девятеричная точки точно были.


                1. PapaBubaDiop
                  01.01.2016 21:26

                  Целая часть и радикал допускались. Условие было решить все года до текущего.


    1. eduard93
      01.01.2016 11:48

      2^0-1+6 == 6
      2*0+1+6 == 7
      2+0*1+6 == 8
      2+0+1+6 == 9
      2*(0+1)*6 == 12
      -2+0+16 == 14
      -(2^0)+16 == 15
      2*0+16 == 16
      2^0+16 == 17
      2+0+16 == 18
      (2*(0+1))^6 == 64


    1. saboteur_kiev
      01.01.2016 13:37

      -2+0-1+6=3
      -2+0+1+6=5
      2+0-1+6=7
      2+0+1*6=8
      2+0+1+6=9
      20-1*6=14
      20+1-6=15
      20-1+6=25
      20+1*6=26
      20+1+6=27

      В общем тут пару сотен чисел набрать можно.


  1. PapaBubaDiop
    31.12.2015 23:33

    Я легко сделал 11


  1. caveeagle
    01.01.2016 11:19

    Без факториала 11 сделать невозможно.


    1. PapaBubaDiop
      01.01.2016 12:02

      Можно. Разрешается использовать операции x o b m


      1. Mrrl
        01.01.2016 17:49

        А кто это такие? xor, or и кто ещё?


        1. encyclopedist
          01.01.2016 18:31
          +1

          Либо шестнадцатеричные, восьмеричные, двоичные и ???


          1. Mrrl
            01.01.2016 18:32

            видимо, троичные уравновешенные. Правда, толку от них немного.


          1. PapaBubaDiop
            01.01.2016 21:30

            Да и м- модуль от системы счисления. В восьмеричной и шестеричной легко получить 11)


            1. Mrrl
              01.01.2016 23:15
              +1

              То есть, o20+1-6 и (20-1) m 6? Или они применяются как-то по-другому?


              1. PapaBubaDiop
                02.01.2016 00:03

                В точку.


    1. PapaBubaDiop
      02.01.2016 12:23
      +4

      Нашел еще решение для 11 практически на одних плюсах.

      image


      1. caveeagle
        02.01.2016 14:11
        +3

        Тогда я за строгую постановку задачи! =)
        А то набросал скрипт на Питоне, для перебора всех не-читерских вариантов (скобки, базовые операторы, но без факториала). А там числа 11 нет.
        И да, в новогоднюю ночь, в два часа ночи — кодить задачу, за которую даже не заплатят… Мне кажется, со мной что-то не так, доктор =) Всем хорошего Нового года!


  1. Mrrl
    01.01.2016 17:51

    А десятичная точка и периодическая дробь допускается? Например, .2^(0-1)+6?


    1. PapaBubaDiop
      01.01.2016 21:32

      Точка допускается, но в школьном варианте. То есть 0.2 легитимно. А Ваши программисткие Читы вне закона.


      1. Mrrl
        01.01.2016 23:20

        0.(1) считается школьным вариантом? 29=2+sqrt(sqrt(0.(1)^(-6)))


        1. khim
          01.01.2016 23:36

          Периодическая дробь точно не допускалась (не помню точно почему), .2 не допускалось (всё-таки задачка родом из СССР, а не США), какие-то ещё ограничения были (чтобы пресечь «регулярные» решения, порождающие все числа формулами одинаковой структуры).

          По-хорошему надо бы добраться до подшивки и посмотреть на оригинальную формулировку…


          1. Mrrl
            02.01.2016 00:00

            Я помню там точку слева (.2) и точку сверху (эквивалент .(2)). Конечно, это могла быть другая серия задач с похожей формулировкой, но я, опять же, не помню, чтобы такие были.


  1. ooprizrakoo
    01.01.2016 18:26
    -1

    20-v16 = v16


    1. ooprizrakoo
      01.01.2016 18:45

      2^0^16 = 1
      2+(0*16) = 2
      -2+0+(-1+6) =3
      20-16 = 4
      2*0+(-1+6) = 5
      2*0*1 + 6 = 6
      2*0+1 + 6 = 7
      2+0*1+6 = 8
      2+0+1+6 = 9
      v(20*(-1+6)) = 10


      1. PapaBubaDiop
        01.01.2016 21:28
        +1

        2*(0-1+6)=10


  1. Lockal
    01.01.2016 22:22
    +2

    Для примера установим, что 01 = 1, 016 = 16. Берём операции + ? * / fct (факториал) и pwr (возведение в степень) и полным перебором получаем ответы для 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 20, 21, 24, 25, 26, 27, 32, 36, 62, 64, 66, 100

    Ответы
    0: (2 * (0 * (1 + 6)))
    1: (2 + -(pwr(1, 6)))
    2: (2 * (pwr(1, 6)))
    3: (-(2 + 1) + 6)
    4: (20 + (-16))
    5: -(2 + -(1 + 6))
    6: ((2 + (-1)) * 6)
    7: (2 + ((-1) + 6))
    8: (2 + (1 * 6))
    9: (2 + (1 + 6))
    10: (2 * ((-1) + 6))
    12: (2 * (1 * 6))
    13: (20 + -(1 + 6))
    14: ((-2) + 16)
    15: -(-(20 + 1) + 6)
    16: (2 * (fct(0) + (1 + 6)))
    18: (2 + 16)
    19: (20 + -(pwr(1, 6)))
    20: (20 * (pwr(1, 6)))
    21: (20 + (pwr(1, 6)))
    24: ((2 + (fct(0) + 1)) * 6)
    25: (20 + ((-1) + 6))
    26: (20 + (1 * 6))
    27: (20 + (1 + 6))
    32: (2 * 16)
    36: (20 + 16)
    62: -(2 + -(pwr((fct(0) + 1), 6)))
    64: (pwr((2 * 1), 6))
    66: (2 + (pwr((fct(0) + 1), 6)))
    100: (20 * ((-1) + 6))


    1. Lockal
      01.01.2016 22:59

      В частности, 82 можно получить как -ceil(factorial((-2+0) * (~1)) / tan(6)), где tan возвращает тангенс в радианах. Сомнительное достижение.


    1. Mrrl
      01.01.2016 23:24

      sqrt отличается тем, что его можно общепринятым способом написать в линейной формуле, не используя букв и цифр — знаком радикала. Число сочетаний так уже не запишешь — придётся писать в два этажа, либо использовать букву C.


    1. mezastel
      01.01.2016 23:40

      Вообще-то, раз уж вы разрешаете факториалы, могли бы получить 29 (и 27 по аналогии) как 29 = -20 + 1 + 6!!


      1. Mrrl
        02.01.2016 00:03

        Двойного факториала, к сожалению, в списке нет. Как и других комбинаторных штучек.


        1. mezastel
          02.01.2016 00:06

          Под «факториал», мне кажется, подходят двойные факториалы и субфакториалы.


          1. Lockal
            02.01.2016 13:07
            +1

            С бинарными +, *, /, pwr(возведение в степень) и унарными -, fct (факториал), sfct (субфакториал), dfct (двойной факториал) получается ряд для [0 — 30], 32, 35, 36, 38, [41 — 57], [62 — 69], 72, 85, 88, 90, 92, [94 — 100].

            Ответы
            0: (2 * (0 * (1 + 6)))
            1: dfct(2 + (-16))
            2: (2 * (pwr(1, 6)))
            3: (-(2 + 1) + 6)
            4: (20 + (-16))
            5: -(2 + -(1 + 6))
            6: ((2 + (-1)) * 6)
            7: (2 + ((-1) + 6))
            8: (2 + (1 * 6))
            9: (2 + (1 + 6))
            10: (2 * ((-1) + 6))
            11: (2 + sfct(-(fct(0) + 1) + 6))
            12: (2 * (1 * 6))
            13: (20 + -(1 + 6))
            14: ((-2) + 16)
            15: -(-(20 + 1) + 6)
            16: (sfct(2) * 16)
            17: (sfct(2) + 16)
            18: (2 + 16)
            19: (20 + -(pwr(1, 6)))
            20: (20 * (pwr(1, 6)))
            21: (20 + (pwr(1, 6)))
            22: ((-2) + fct(-(fct(0) + 1) + 6))
            24: fct(20 + (-16))
            25: (20 + ((-1) + 6))
            26: (20 + (1 * 6))
            27: (20 + (1 + 6))
            28: (-(20 * 1) + dfct(6))
            29: -(20 + -(1 + dfct(6)))
            30: (2 * dfct((-1) + 6))
            32: (2 * 16)
            35: (20 + dfct((-1) + 6))
            36: (20 + 16)
            38: (sfct(fct(2 + fct(0)) + (-1)) + (-6))
            41: (-(2 + fct(0)) + sfct((-1) + 6))
            42: ((-2) + sfct((-1) + 6))
            43: (-(pwr(2, 0)) + sfct((-1) + 6))
            44: sfct((-2) + (1 + 6))
            45: (-(2 + 1) + dfct(6))
            46: (-(2 * 1) + dfct(6))
            47: -(2 + -(1 + dfct(6)))
            48: dfct((2 + (-1)) * 6)
            49: (2 + ((-1) + dfct(6)))
            50: (2 + dfct(1 * 6))
            51: (2 + (1 + dfct(6)))
            52: (2 + (fct(0) + (1 + dfct(6))))
            53: (fct(2 + fct(0)) + ((-1) + dfct(6)))
            54: (fct(2 + 1) + dfct(6))
            55: (fct(2 + fct(0)) + (1 + dfct(6)))
            56: (dfct(2 + (fct(0) + 1)) + dfct(6))
            57: (sfct(2 + (fct(0) + 1)) + dfct(6))
            62: -(2 + -(pwr((fct(0) + 1), 6)))
            63: -(sfct(2) + -(pwr((fct(0) + 1), 6)))
            64: (pwr((2 * 1), 6))
            65: (sfct(2) + (pwr((fct(0) + 1), 6)))
            66: (2 + (pwr((fct(0) + 1), 6)))
            67: (20 + ((-1) + dfct(6)))
            68: (20 + dfct(1 * 6))
            69: (20 + (1 + dfct(6)))
            72: (fct(2 + (fct(0) + 1)) + dfct(6))
            85: ((-20) + dfct(1 + 6))
            88: (2 * sfct((-1) + 6))
            90: (2 * (fct(0) + sfct((-1) + 6)))
            92: (2 * (-(fct(0) + 1) + dfct(6)))
            94: (2 * ((-1) + dfct(6)))
            95: -(sfct(2) + -((fct(0) + 1) * dfct(6)))
            96: (2 * dfct(1 * 6))
            97: (sfct(2) + ((fct(0) + 1) * dfct(6)))
            98: (2 * (1 + dfct(6)))
            99: (dfct(fct(2 + fct(0)) + 1) + (-6))
            100: (20 * ((-1) + 6))


            1. mezastel
              02.01.2016 13:42

              Простите, но 1: dfct(2 + (-16)) это неверно… двойной факториал от -8 это «комплексная бесконечность», но никак не 1. Да и решение слишком сложное, что мешало 1: pow(2, 0*16)?


      1. Lockal
        02.01.2016 00:30

        Если трактовать задачу как «записать числа от 0 до 200, используя в формулах только цифры 2, 0, 1, 6 в этом порядке и знаки препинания, в том числе с повторением», то можно выйти на любое целое число через «~-» и «-~». -~2016 = 2017, ~-2016 = 2015, ~-~-2016 = 2014 и т. д.


        1. mezastel
          02.01.2016 00:34

          Боюсь такого в задаче нет. Зато есть

          Факториалы и степени милостиво допускаются.


    1. ooprizrakoo
      01.01.2016 23:47

      имхо 80 лаконичнее написать как 20*v16


  1. Mrrl
    01.01.2016 23:32

    С использованием x20 первой дыркой пока получилось 35.


  1. OLS
    02.01.2016 00:36
    +1

    а может в сторону универсальной формулы посмотреть?
    если вдруг кто придумает как от второго логарифма избавиться…:
    -log2(log2(0+vvvvvv...vvvv16))
    где корень повторяется 3, 4, 5,… и т.д. раз для получения чисел 1, 2, 3,… соответственно


    1. OLS
      02.01.2016 01:14
      +4

      UPD:
      -log2(ln(0+1^6*vvvvvv...vvvve))
      где корень повторяется 1, 2, 3, … и т.д. раз для получения чисел 1, 2, 3, … соответственно

      путь, конечно, экстенсивный, да и цифры «0», «1», «6» — лишние,
      но по формальным признакам — условию задачи соответствует


      1. withkittens
        02.01.2016 01:33

        По формальным признакам оба варианта не подходят: в первом случае у вас задействована лишняя двойка, во втором — лишнее e.


        1. hacklex
          02.01.2016 02:32
          +3

          Лишнее е – это не цифра. Буковки логарифма иначе тоже «лишние», и плохо въезжают в авторское «знаки и скобки». Если же проблема именно в константе – да пожалуйста:
          image

          Не ошибся вроде?


          1. hacklex
            02.01.2016 02:38

            Угу, не ошибся. Сижу, любуюсь. OLS однозначный победитель. Красиво и в общем виде. Для всех целых сразу. Для всех отрицательных, очевидно, достаточно убрать минус. Решение – пушка.


            1. jzha
              02.01.2016 09:50

              Да, OLS здорово придумал. Хотя, наверное, log и прочие функции не поразумевалось использовать, его решение лучшее. Да еще и без изменений на несколько последующих лет распространяется.


              1. hacklex
                02.01.2016 11:00
                +2

                Ну, раз пошла такая пьянка – остаётся вспомнить про функцию sign и закрыть проблему. С её помощью двойка получается из любых двух первых цифр (image либо image для image).

                Единица, нужная для image, получается из любых оставшихся цифр image (как минимум две) перемножением image, если нулей нет, либо суммой двух произведений, в одном из которых нуль есть. Если остались одни нули – пользуемся тем, что 0! = 1.

                Теперь решение распространяется на решительно все последующие годы.

                … фух…


                1. PapaBubaDiop
                  02.01.2016 12:15

                  Предлагаю это решение назвать hack-lex-close-by-sign.


          1. Mrrl
            03.01.2016 01:25
            +2

            Тогда можно попробовать так:

            n/k = logln(vvv...vexp(20))(ln(vvv...vexp(16)))

            Ведь логарифм по основанию, меньшему 1, не запрещён?


            1. hacklex
              03.01.2016 07:06

              Вовсе нет!

              Вот и получилось решение для всех рациональных чисел. А если с сигнумами – так ещё и не зависящее от года, достаточно, чтобы цифр было более одной.

              Да, кстати, множество алгебраических чисел же вроде тоже счётно?)


    1. vmarunin
      02.01.2016 02:26

      Ну если можно использовать функцию Эйлера, то 2=2 2=0!+1 2=phi(6) и готовы 2 двойки image
      Если вдруг картинка не вставится, то вот ссылка

      PS А может есть способ сделать из 0 и 1 шестёрку? Тоже сработает