22.11.2017 08:35
kefirr 19 4500 Источник
Две недели назад мы были на 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 поддерживать открытый код, и кто придумывает нам задачи.

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


  1. redmanmale
    22.11.2017 13:10
    #10532630

    Зачем тексты задач картинками?


    1. kseniya_ro
      22.11.2017 13:21
      #10532668

      Теплые, ламповые, как в буклете — для напоминания о конфе. В прошлый раз так же делали. Уже можно считать традицией.


    1. kefirr Автор
      22.11.2017 13:22
      #10532682

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


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


      1. InstaHeat
        22.11.2017 13:41
        #10532744

        Если убрали под кат решение, могли бы туда же и оригинал текста для нуждающихся


        1. kseniya_ro
          22.11.2017 14:09
          #10532810
          +1

          А в чем конкретно нуждаются трудящиеся, что нужен копируемый текст?


          1. InstaHeat
            22.11.2017 16:36
            #10533240

            Если спросил человек в теме, и в похожей теме были вопросы — похоже, потребность есть.
            Зачем — не знаю. Если бы нужно было мне — я бы просто распознал текст=)


  1. Suslikovich
    23.11.2017 09:38
    #10534286

    <зануда>
    по моему не совсем корректное решение (либо формулировка) первой задачи:
    в вопросе формулировку "чтобы до конца дня было написано 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. TheEin
      23.11.2017 11:07
      #10534486

      Предположим следующее условие: от светофора до светофора машина проехала 100 метров. С какой средней скоростью ехала машина, если от момента включения разрешающего сигнала первого светофора до остановки на запрещающий сигнал светофора прошло ровно 10 секунд.

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

      ИМХО, если в условии написано что было столько то, то «по-умолчанию» это означает «ровно».


      1. Suslikovich
        24.11.2017 11:36
        #10536098

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


  1. vltksk
    23.11.2017 09:38
    #10534288

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

    Как решал я:

    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. В любом случае, в этой задаче мой ответ тоже был правильными.

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


    1. kseniya_ro
      23.11.2017 15:11
      #10534998

      vltksk давайте сделаем так, мы сейчас найдем ваш квиток с решениями и внимательнее его посмотрим. Если была ошибка с нашей стороны в ходе проверки (ну всякое бывает), с нас причитается. Имя-фамилию в профиле вижу, проблем быть не должно.


      1. kseniya_ro
        23.11.2017 16:13
        #10535116

        vltksk нашли ваши решения. Вторая задача решена верно, первая и третья — нет. В первой задаче, если поставить указанную вами частоту, у Моники отвалится голова :) плюс она слишком заинтересована в результате, чтобы простаивать час. Но, у нас есть для вас утешительный приз за активность — отправила письмо на mail, указанный в квитке. Давайте продолжим там.


        1. vltksk
          23.11.2017 23:48
          #10535764

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

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

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

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

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

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

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

          Итак, поскольку состоялась повторная внимательная проверка, то ничего не остается, как считать эти дроби разными. Например, сходу видно, что в “6156 / 3735936” больше символов, чем “171 / 103776” и начинается одна с “6”, а другая с “1”.
          С третьей, пожалуй, тоже закончили.


  1. TheEin
    23.11.2017 11:19
    #10534522

    Интересная интерпретация условия первой задачи. Ты полностью оперся на формулу f(x) = 1 + sqrt(x). Вроде бы, можно принять x = 0 и тогда f(x) = 1 — const. Но условие состоит не только из одной формулы, у нее есть текст, который нельзя игнорировать.

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


    1. vltksk
      23.11.2017 11:38
      #10534574

      Ты полностью оперся на формулу f(x) = 1 + sqrt(x).

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

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


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

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


  1. TheEin
    23.11.2017 14:12
    #10534864

    В условии «написано 100 строк кода», но ты трактуешь, что может и больше.
    В условии «до конца рабочего дня», но ты трактуешь, что именно в конце рабочего дня.

    По моему у тебя неверная трактовка условий.


    1. vltksk
      23.11.2017 14:58
      #10534974

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

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

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


  1. Borz
    24.11.2017 09:08
    #10535952

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


    1. kseniya_ro
      24.11.2017 13:01
      #10536250

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