Тройка, семерка, джокер — разбор решения задач из буклета GridGain на конференции Joker 2017

    Две недели назад мы были на Java-конференции в Питере — Joker 2017. Уже традиционно пришли туда не с пустыми руками, а с веселыми и сложными задачами, над которыми можно посмеяться и/или поломать голову. Спасибо всем, кто в эти два дня решал задачи, задавал вопросы и предлагал свои оригинальные решения. Поздравляем победителей!

    Все задачи верно решили целых три человека:

    — Рюрик Крылов (который к тому же сдал корешок из буклета с верными ответами самым первым)
    — Евгений Крутень
    — Василий Бригинец

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



    Задача №1




    Решение
    t — длительность происходящего действия в минутах,
    r — количество написанных строк кода за время t,
    k — количество кивков за время t.

    $t < 60$
    $r = 100$
    $k = 243$
    $f(x) = r / t$
    $x = k / t$

    $r / t = 1 + sqrt(k / t)$

    Произведем замену $1 / t = y$
    $ry = 1 + sqrt(ky)$
    $ry - 1 =sqrt(ky)$
    $r^2 * y^2 - 2ry +1 = ky$
    $r^2 * y^2 - (2r +k)y +1=0$

    Решаем обычное квадратное уравнение: дискриминант, корень, два возможных решения:
    $D = (2r + k)^2 – 4r^2 = 156249$
    $sqrt(D) = 395,2834426$
    $y = ((2r + k) ± sqrt(D)) / 2r^2$

    $y1 = 0,041914172$
    $y2 = 0,002385828$

    Производим обратную замену:
    $t1 = 23,8582787$
    $t2 = 419,1417213$

    и выбираем один корень, удовлетворяющий условию t1 < 60, который подставляем в уравнение:
    $x = k / t1 = 10,18514383$

    Ответ: 10,185

    Задача №2




    Решение
    Имеем систему счисления с основанием 10 + 33 = 43



    Приводим кириллические числа к десятичному представлению:

    ПОСТ = {26, 25, 28, 29} = (((26 * 43) + 25) * 43 + 28) * 43 + 29 = 2114640

    Аналогично:

    ПОКАЙСЯ = {26, 25, 21, 10, 20, 28, 42} = 168103278466
    МОЛИТВА = {23, 25, 22, 19, 29, 12, 10} = 149143339604

    ПОКАЙСЯ + МОЛИТВА * ПОСТ = 315384639763481026

    Приводим десятичный результат к кириллическому представлению, для этого ищем первый старший разряд, который будет нулевым:

    $43^{11} = 929293739471222707 > 315384639763481026$
    $43^{10} = 21611482313284249 < 315384639763481026$

    Последовательно делим остаток на 43 в степени от 10 до 0:

    $315384639763481026 / 43^{10 }= 14$
    $12823887377501540 / 43^9 = 25$
    $259072079080465 / 43^8 = 22$
    $1931672973243 / 43^7 = 7$
    $28942695494 / 43^6 = 4$
    $3657243298 / 43^5 = 24$
    $129040666 / 43^4 = 37$
    $2545029 / 43^3 = 32$
    $805 / 43^2 = 0$
    $805 / 43^1 = 18$
    $31 / 43^0 = 31$

    {14, 25, 22, 7, 4, 24, 37, 32, 0, 18, 31} = ДОЛ74НЪХ0ЗФ

    Ответ: ДОЛ74НЪХ0ЗФ

    Задача №3




    Решение
    С учетом начальных условий подсчитаем количество возможных сочетаний:

    Герман: 2 туза из 4 = $С^2_4$ = 6.
    Старуха: 2 пики из 9 числовых = $С^2_9$ = 36.
    Флоп: 3 карты из оставшихся 48 в колоде = $С^3_{48}$ = 17296.
    Всего подходят 6 * 36 * 17296 = 3735936 комбинаций.

    Теперь рассмотрим подходящие варианты.

    У Германа во всех вариантах также: 2 туза из 4 = $С^2_4$ = 6.
    Варианты с рукой старухи:
    1) нет 3 и 7 в руке, остается 2 из 7 = $С^2_7$ = 21.
    2) одна 3 или 7 в руке, это 2 * 7 сочетаний = 14.
    3) и 3 и 7 в руке = 1.

    Проверяем, что мы рассмотрели все комбинации 21 + 14 + 1 = 36.

    Теперь находим количество подходящих сочетаний для флопа:

    1) в колоде осталось 2 туза, 4 тройки и 4 семерки = 2 * 4 * 4 = 32 сочетания.
    2) в колоде осталось 2 туза, 3 карты одного числа и 4 другой = 2 * 3 * 4 = 24 сочетания.
    3) в колоде осталось 2 туза, 3 тройки и 3 семерки = 2 * 3 * 3 = 18 сочетаний.

    Общее количество подходящих сочетаний:
    6 * 21 * 32 + 6 * 14 * 24 + 6 * 1 * 18 = 6156

    Искомая вероятность 6156 / 3735936 = 0,00164777983348751156336725254394

    Ответ: 0,00165 или 0,165 %

    Пока ждем появления на канале конференции видео с докладом Вовы Озерова про сериализацию, можно скачать слайды или посмотреть интервью Якова Жданова про то, зачем GridGain поддерживать открытый код, и кто придумывает нам задачи.
    GridGain 109,27
    Компания
    Поделиться публикацией
    Комментарии 19
    • –1
      Зачем тексты задач картинками?
      • +1
        Теплые, ламповые, как в буклете — для напоминания о конфе. В прошлый раз так же делали. Уже можно считать традицией.
        • 0

          Тот же вопрос задавали в прошлый раз: https://habrahabr.ru/company/gridgain/blog/327732/


          Хотя я согласен, что картинкой не очень хорошо, не индексируется поисковиками, не скопировать.

          • 0
            Если убрали под кат решение, могли бы туда же и оригинал текста для нуждающихся
            • +1
              А в чем конкретно нуждаются трудящиеся, что нужен копируемый текст?
              • +2
                Если спросил человек в теме, и в похожей теме были вопросы — похоже, потребность есть.
                Зачем — не знаю. Если бы нужно было мне — я бы просто распознал текст=)
        • +1
          <зануда>
          по моему не совсем корректное решение (либо формулировка) первой задачи:
          в вопросе формулировку "чтобы до конца дня было написано 100 строк кода" — можно трактовать как не менее 100 строк (т.е. если написано 101 строка значит и 100 написано)
          соответственно в начальных условиях изменяется f(x) >= 100 строк / 60 минут
          и решение сводится к двум неравенствам:
          f(x) >= 100/60 — чтобы скорость позволяла написать 100 строк за 1 час
          243/x = t <= 60 — чтобы за час сделать успеть сделать 243 кивка
          из первого: 1+sqrt(x) >=5/3 | x >= 4/9 (~ 0,4444)
          из второго: 243/60 <= x | x >= 81/20 ( 4,05 )
          получаем x >= 4,05
          Т.е. при любой частоте выше 4,05 (кивка в минуту) условия выполняются
          </зануда>
          • +1
            Предположим следующее условие: от светофора до светофора машина проехала 100 метров. С какой средней скоростью ехала машина, если от момента включения разрешающего сигнала первого светофора до остановки на запрещающий сигнал светофора прошло ровно 10 секунд.

            В данном случае в тоже посчитаете, что здесь может быть 101 метр или больше? )))

            ИМХО, если в условии написано что было столько то, то «по-умолчанию» это означает «ровно».
            • 0
              в задаче смутило незаконченное действие "… чтобы до конца дня было ..." (привет английским временам))
              в вашем примере есть утверждение «проехала 100 метров», что воспринимается по другому. А вот если переформулировать задачу как: "с какой средней скоростью должна ехать машина чтобы остановится (или например "не остановиться") на следующем светофоре, который расположен через 100 метров, при условии что запрещающий сигнал светофора загорится через 10 секунд", ответ измениться ?))
              возвращаясь к исходной задаче, с контекстом «равно» вопрос лучше бы ассоциировался в утвердительной форме, например "С какой частотой одобрительно кивала Моника, если в конце рабочего дня было написано 100 строк кода и сделано 243 одобрительных кивка"
              вышеописанное ИМХО, и видимо из серии «у каждой задачи есть простое, красивое, легко-понимаемое, но неправильное решение».
          • +2
            Я на конференции тоже поучаствовал в решении этих задач, в результате у меня была зачтена только одна задача — вторая. Выглядели все задачи довольно просто, поэтому, признаться, хотелось понять, в чём подвох.

            Как решал я:

            1. В первой задаче меня смутила слабая обратная зависимость (Моники от Билла) и смутное понимание, чем она будет заниматься в кабинете остаток рабочего дня, если Билл уйдёт раньше. Я для гарантии решил ужесточить условие, поскольку задача это позволяла и стал искать решение, чтобы 243-й кивок завершился ровно в момент окончания рабочего дня и точно в этот же момент Билл должен написать сотую строку кода. Понятно, что для достижения такого результата Моника не могла кивать весь час с постоянной частотой, но по условию задачи такого ограничения не стояло. Таким образом, в качестве ответа нужно предложить такую функцию кивания Моники x(t), чтобы
            — интегрирование функции x(t) от 0 до 60 давало 243 и при этом
            — интеграл f(t) = 1 + sqrt(x(t)) от 0 до 60 дал бы 100.

            Очевидно, существует бесконечное множество подходящих функций и мы свободны в их выборе. Я пошёл простейшим путём и выбрал ступенчатую функцию
            x(t) = { 0 при t < T; X = const при t > T }.
            Т.е. Моника сначала не делает ничего, а потом начинает кивать с постоянной частотой так, чтобы Билл закончил точно к концу рабочего дня.

            Введем T’ = 60 — T — это продолжительность кивания Моники и получается несложная система

            T’ * X = 243
            T’ * sqrt(X) = 40 (поскольку остальные 60 строк Билл напишет за этот час без помощи Моники)

            Отсюда X = (243/40)2 ~= 36,9 кивков в минуту, T’ = 402 / 243 ~= 6,58 минут.

            Получается, Моника начинает ободрять Билла в конце рабочего дня с частотой примерно раз в две секунды и тогда Билл за шесть минут справляется с условиями задачи. Такие величины настолько рифмуются с антуражем задачей, что я подумал, что числа условия подобрали в расчете именно на такую форму функцию частоты.

            Однако мой ответ не зачли, хотя он отлично подходит, как и множество других.

            2. Вторую задачу, как я сказал, зачли — ответ совпал. Хотя я беспокоился из-за слов условия
            “…по аналогии с 16-ричной системой, только помимо цифр будут использоваться…”.
            Дело в том, что a, b, c, d, e, f в 16-ричной системе вполне цифры (в системе счисления нет “букв”) и я не был уверен, брать ли мне помимо кириллицы десять цифр или шестнадцать. Взял десять и угадал.

            3. Про третью задачу я думал, что допустил ошибку из-за неправильного понимания, что такое “флоп” (я, увы, незнаком с правилами покера) и в игре происходило что-то другое. Но оказалось, причина куда проще. Я дал ответ 171 / 103776. Несложно заметить, что это та же самая дробь 6156 / 3735936. Кстати, тогда я не заметил, что дробь можно сократить ещё на 3, до 57 / 34592. В любом случае, в этой задаче мой ответ тоже был правильными.

            На мой взгляд, есть некоторые проблемы с однозначностью условий задач и поверхностной проверкой ответов. В любом случае спасибо за этот пост, он развеял мистику.
            • +2
              vltksk давайте сделаем так, мы сейчас найдем ваш квиток с решениями и внимательнее его посмотрим. Если была ошибка с нашей стороны в ходе проверки (ну всякое бывает), с нас причитается. Имя-фамилию в профиле вижу, проблем быть не должно.
              • 0
                vltksk нашли ваши решения. Вторая задача решена верно, первая и третья — нет.

                Если говорить о первой задаче, нам казалось, что условие задачи достаточно точно подразумевает, что частота кивков Моники является константой. В следующий раз будем использовать более полную формулировку. Далее цитирую коллег из R&D:

                Если расширять область допустимых решений на не константные функции, то очевидно, что решений будет бесконечно много. В общем случае, если частота кивков Моники зависит от времени как функция x=x(t) и x(t) интегрируема на [0, 60], то количество строк кода, написанное Биллом за час будет (формула 1) и x(t) можно искать как решение интегрального уравнения (формула 2).
                Так, можно найти одно из решений, если частоту кивкнов Моники искать в виде x(t) = k * t^2. В этом случае интеграл берется и коэффициент k легко вычисляется.
                При такой интерпретации Ваше решение не полное, и именно поэтому мы не засчитали его как правильное.


                Но, у нас есть для вас утешительный приз за активность — отправила письмо на mail, указанный в квитке. Давайте продолжим там.
                • 0
                  К сожалению, я должен написать ещё один, очень надеюсь, что последний, комментарий на эту тему. У меня правда, как это сейчас говорят, “подгорает”, куда сильнее, чем проблема этого заслуживает и мне теперь придётся с этим как-то жить.

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

                  По первой задаче:

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

                  мне заявили, что в случае, если решений бесконечное количество, никакое частное решение не может быть засчитано.
                  Это не так, поскольку частное решение остаётся решением, но спорить об этом, действительно, больше не стоит.

                  По третьей задаче:

                  Я писал в первом же комментарии, что я указал решение 171 / 103776.
                  В присланном фото квитка действительно указан ответ 171 / 103776.
                  В посте правильным ответом указано 6156 / 3735936.

                  Итак, поскольку состоялась повторная внимательная проверка, то ничего не остается, как считать эти дроби разными. Например, сходу видно, что в “6156 / 3735936” больше символов, чем “171 / 103776” и начинается одна с “6”, а другая с “1”.
                  С третьей, пожалуй, тоже закончили.
            • +1
              Интересная интерпретация условия первой задачи. Ты полностью оперся на формулу f(x) = 1 + sqrt(x). Вроде бы, можно принять x = 0 и тогда f(x) = 1 — const. Но условие состоит не только из одной формулы, у нее есть текст, который нельзя игнорировать.

              В буклете слова «парным программированием» даже цветом выделены. Это означает, что Билл пишет код только тогда, когда Моника «помогает» ему )))
              • +3
                Ты полностью оперся на формулу f(x) = 1 + sqrt(x).

                Нет, я полностью оперся на условие.

                ...«парным программированием» даже цветом выделены. Это означает, что Билл пишет код только тогда, когда Моника «помогает» ему


                Я не вижу ни малейших оснований так считать. Во-первых, в парном программировании код пишут не в четыре руки; в любой момент времени минимально обязательная цель второго — наблюдать, что решается просто присутствием Моники. Во-вторых, «выделение цветом» не несёт никакой смысловой нагрузки хотя бы потому, что тем же цветом выделены имена персонажей. В-третьих, мне у стенда подтвердили, что Билл и без Моники написал бы свои 60 строк, что идёт из формулы функции частоты.

                Я как раз очень дотошно подошёл к тексту условия. Поэтому у меня не было уверенности, что Моника вообще перестанет кивать после ухода Билла, это я и имел в виду под отсутствием обозначенной связи поведения Моники от поведения Билла. И если дать ответ в виде числа, то получилось бы, что Моника будет кивать весь час, проигнорировав уход Билла, и кивнёт более 243 раз. Поэтому я стал в явном виде синхронизироваться на точке окончания рабочего дня.
              • 0
                В условии «написано 100 строк кода», но ты трактуешь, что может и больше.
                В условии «до конца рабочего дня», но ты трактуешь, что именно в конце рабочего дня.

                По моему у тебя неверная трактовка условий.
                • 0
                  В условии «до конца рабочего дня», но ты трактуешь, что именно в конце рабочего дня.

                  Судя по всему, это адресовано мне. Тогда я хотел бы на всякий случай обратить внимание, что я про превышение ста строк ничего не писал, ты путаешь меня с другим комментатором.

                  Далее, «именно в конце рабочего дня» является строгим подмножеством условия «до конца рабочего дня». Это более сильное условие, именно поэтому я написал в изначальном комментарии, что для гарантии решил ужесточить условие (а не изменить его), убрав неоднозначность, которую я достаточно подробно описал.
                • 0

                  А поясните по второй задаче — почему 10+33, а не 33+6? Ведь говорится, что заменены будут цифры на буквы, а не латинские буквы на буквы русского алфавита

                  • 0
                    «По аналогии с шестнадцатеричной системой»
                    0123456789ABCDEF

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

                  Самое читаемое