Home » Работа и карьера » Тесты при приеме на работу в ABBYY Software – Ответы 1 (продолжение)

Тесты при приеме на работу в ABBYY Software – Ответы 1 (продолжение)

Снова вынуждет вернуться к ответу на первую задачу. Как выяснилось, мое решение оказалось неоптимальным. Вот более правильное решение.

Пусть красный цвет соответствует 0, а белый – 1. Тогда, чиновник, который отвечает первым и видит цвета всех остальных, подсчитывает сумму по модулю 2 и называет получившийся цвет. С вероятностью 50% результат совпадет с его цветом. Далее, следующий чиновник, подсчитав сумму по модулю 2 всех, кто стоит перед ним, и зная ответ предыдущего, стопроцентно правильно называет свой цвет. И так по цепочке. Таким образом, действуя по этому алгоритму, стопроцентно выживут все, кроме первого (его вероятность выжить 50%).

  • jonny3D

    Им всего-то и нужно было договориться называть цвет колпака впереди стоящего… :-/

    Первый мрёт с 50% гарантией давая 100% шанс выжить остальным..

  • Anonymous

    >Им всего-то и нужно было договориться называть цвет колпака впереди стоящего…

    Нет, так не получится. Например:
    БКБКБКБК

    Тогда по этому алгоритму все умрут.

  • Anonymous

    Это очень интересное решение, но работает оно только в случае, если каждый чиновник действительно может видеть всю очередь впереди себя, а не только непосредственно того, кто перед ним.
    Так как если задача на классическую логику, и чиновники смотрят в затылок впередистоящего – они наверное не должны выглядывать сбоку на всю очередь, как и поворачиваться назад, как и говорить лишние слова.
    Лучший вариат – дать два варианта ответа :)

  • Anonymous

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

  • Anonymous

    2Ravlyk:
    В условии задачи сказано: “… Первым отвечал тот кто видит всех …”, т.е. чиновники видят всех впереди стоящих.
    А на собеседовании нужно задавать наводящие вопросы, если что-то непонятно и рассуждать вслух. Тогда можно получить подсказки.

    2jonny3D: со всеми бывает :-)

  • Stranger

    “более правильное решение” просто неверно

  • Anonymous

    2Stranger:
    А почему это оно неверно? Какие аргументы?

  • Stranger

    Чтобы дать точный ответ, сначала нужно получить точный алгоритм решения. Здесь вместо алгоритма сказано:
    “…И так по цепочке…”
    Вопрос:”Каким правилом,называя цвет, руководствуются те, кто относится к этой цепочке?”.

  • Anonymous

    2Stranger:

    Давайте рассмотрим на примере:
    0 – красный, 1 – белый
    Возьмем такую последовательность:
    [1]101000110
    Начинать будем слева, т.е. чиновник в белом колпаке (самая левая единица в квадратных скобках) видит всех впереди и подсчитывает сумму по модулю 2, которая равна в данном примере 0. Он называет соответствующий цвет и будет убит, т.к. названный цвет не совпадает с его собственным.

    Остается такая цепочка:
    [1]01000110
    Причем, все знают ответ первого чиновника и алгоритм.
    Следующий чиновник подсчитывает сумму по модулю 2 всех, которые перед ним, получается 1. Т.к. у предыдущего чиновника получилось 0, следовательно его цвет должен быть 1. Что он и называет.

    Остается такая цепочка:
    [0]1000110
    Сумма по модулю 2 = 1
    предыдущий цвет = 1
    в сумме имеем 0, чтобы общая сумма была равно 0, цвет текущего колпака должен быть 0.

    [1]000110
    (+) = 0
    (+) предыдущих ответов = 0(+)1(+)0 = 1
    ответ = 1

    [0]00110
    (+) = 0
    (+) предыдущих ответов = 0(+)1(+)0(+)1 = 0
    ответ = 0

    [0]0110
    (+) = 0
    (+) предыдущих ответов = 0
    ответ = 0

    [0]110
    (+) = 0
    (+) предыдущих ответов = 0
    ответ = 0

    [1]10
    (+) = 1
    (+) предыдущих ответов = 0
    ответ = 1

    [1]0
    (+) = 0
    (+) предыдущих ответов = 1
    ответ = 1

    [0]
    (+) = 0
    (+) предыдущих ответов = 0
    ответ = 0

  • Stranger

    Хм. Не знаю с чего и начать…
    Предыдущее пояснение было весьма подробным, поэтому не буду экономить буквы, но заранее извиняюсь за многословие. Начну издалека. Предлагается такая игра:
    Пусть имеется группа участников, каждый из которых имеет 100 руб. и согласился участвовать в следующей игре-лотерее. Ведущий говорит: “Вас 1000 человек. Для удобства я вас пронумерую числами от 1 до 1000. Правила игры. Выбирается случайным образом один из вас (пусть его номер будет М>1) и я бросаю монету. Если выпадет герб, то участнику с предыдущим номером я выплачиваю 500 рублей, а если герб не выпадает, то его 100 руб. переходят ко мне. Играем один раз”. Толпа гудит: “Не тяни время, начинай!!!”
    Начинается игра. Первому же из участников под довольно большим номером М “не повезло” – герб не выпал. Ведущий говорит:” Прошу всех предыдущих участников с номерами от 1 до М-1 отдать мне свои 100 руб. Все свободны до следующей игры!”…
    Некоторые из этих М-1 участников немного недовольны: “Как же так? Ведь речь шла только об участнике с предыдущим номером?”
    Ведущий, собирая денежки в большой мешок, объясняет: “Нет, дорогие! Я имел в виду всех участников с предыдущими номерами! Не надо придираться по мелочам!!!”… Толпа снова гудит… :)
    А теперь по существу. Вспомним, что обсуждалось следующее решение: (цитата)
    >”…чиновник, который отвечает первым и видит цвета всех остальных, подсчитывает сумму по модулю 2 и называет получившийся цвет. С вероятностью 50% результат совпадет с его цветом. Далее, следующий чиновник, подсчитав сумму по модулю 2 всех, кто стоит перед ним, и ЗНАЯ ОТВЕТ ПРЕДЫДУЩЕГО (выделено мною, Stranger), стопроцентно правильно называет свой цвет. И так по цепочке…”
    Здесь вроде бы всё верно. Но очередной следующий чиновник не сможет “стопроцентно правильно назвать свой цвет” , используя информацию: “сумму по модулю 2 всех, кто стоит перед ним, и ЗНАЯ ОТВЕТ ПРЕДЫДУЩЕГО”.
    В подробно разобранном примере приводится решение на основе совершенно другого алгоритма (вот цитата):
    > ” (+) предыдущих ответов = 0 (+) 1 (+) 0 (+) 1 . ..”
    Здесь, как видим, уже используются ВСЕ предыдущие ответы, т.е. совершается плавный переход от использования одного предыдущего ответа (что прозвучало в алгоритме решения) к использованию всех предыдущих ответов. НО это СОВЕРШЕННО ДРУГОЕ РЕШЕНИЕ. Те, кто с этим не согласен, наверное, уже пошли участвовать в повторной игре с упомянутым выше ведущим, который уже ждёт их со своим большим мешком:) .
    Принципиально важный момент: сколько прозвучавших ответов может использовать чиновник с номером М (нумерация с хвоста):
    – один ответ (стоящего непосредственно за ним) => задача А;
    – все прозвучавшие ответы => задача В.
    Согласитесь, что это всё-таки разные задачи, различны и алгоритмы их решения.
    Какую же задачу решаем мы?
    1. В УСЛОВИИ задачи сказано, что чиновник, дающий ответ, видит цвета всех колпаков впереди, но не сказано, что он слышит все прозвучавшие ответы. А ведь если “ОЧЕРЕДЬ ДОСТАТОЧНО ДЛИННАЯ”, то вряд ли БЕЗ ОСОБЫХ НА ТО ОСНОВАНИЙ можно предполагать, что чиновники, стоящие в начале колонны, могут слышать ВСЕ ответы. Например, если сказано, что вы сможете, оглянувшись, увидеть цвет колпаков идущих за вами достаточно далеко прохожих, то вряд ли ОТСЮДА СЛЕДУЕТ, что вы сможете услышать их беседу! Вот если наоборот…
    Можно изготовить колпаки и пригласить прохожих для участия в таком эксперименте:).
    Итак, мы имеем, что в условии задачи оговорена возможность видеть все колпаки впереди, но не оговорена аналогичная (и не менее существенная!) возможность слышать все ответы, прозвучавшие за спиной чиновника.
    2. В РЕШЕНИИ сказано: ” следующий чиновник, … ЗНАЯ ОТВЕТ ПРЕДЫДУЩЕГО…”.
    Отсюда делаем вывод, что решается задача А. К этому случаю и относится мой комментарий. Для этого случая я назвал решение, которое привёл Sergiy Oliynyk, оптимальным.
    Если же решается задача В, то, на мой взгляд, обсуждаемый алгоритм решения лучше сформулировать несколько иначе – в виде одного правила:
    – каждый чиновник подсчитывает и называет сумму по модулю 2 цветов всех колпаков впереди и всех прозвучавших ответов.
    Конец алгоритма.
    В этом случае:
    – формулировка алгоритма более компактна.
    – сразу ясно, о какой задаче идёт речь и т.д.
    Из этого алгоритма вытекает следующее решение задачи.
    ВОПРОС :о чём нужно договориться чиновникам?
    ОТВЕТ: каждый чиновник подсчитывает сумму по модулю два цветов колпаков впереди и получает исходное число S (которое может принять только одно из двух значений: 0 или 1). Теперь он слушает ответы. Если слышит 1 – меняет число S , а если 0 – то не меняет. Это число S он и называет, когда придёт его очередь.

    ЗЫ 1. Возможно, что либо условие задачи, либо её решение, либо и то и другое были пересказаны неточно (или неполно). Если условие пересказано точно, то, наверное, количество слышимых ответов нужно было уточнить. Здесь я согласен с рекомендацией: “А на собеседовании нужно задавать наводящие (уточняющие – Stranger) вопросы, если что-то непонятно…”

    ЗЫ 2. По ходу записи этого ответа возникло предложение рассмотреть вот такой (возможно, неинтересный) вариант обсуждаемой задачи:
    будем считать, что
    1. в колонне N чиновников
    2. в зону слышимости попадают К соседей сзади. Т.е. если номер очередного чиновника больше, чем К, то он слышит только К последних прозвучавших ответов. Если номер чиновника меньше, чем К+1, то он слышит все прозвучавшие ответы.
    Какой оптимальной стратегии должны придерживаться чиновники? Для достаточно большой очереди: чему равно в этом случае математическое ожидание количества уцелевших чиновников?
    Случаи К=0, К=1 и К=N -1, кажется, разобраны?

  • Anonymous

    2Stranger:

    ОК, признаю, что сформулировал ответ не совсем точно, хотя имелось в виду именно то, что разобрано в примере, замечания принимаю.

    Кроме того, мое собственное решение было направлено на вариант с бесконечным числом чиновников. Это решение было высказано на форуме и работает для конечного числа с определенными условиями “слышимости”.

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

  • Stranger

    2Sergiy Oliynyk. Спасибо за взаимоинтересный диалог. А о каком форуме речь?
    >” Это решение было высказано на форуме…”

  • Anonymous
  • Stranger

    2Sergiy Oliynyk. Спасибо.

  • shma

    Если решаем задача А:
    Когда чиновник знает только один ответ (стоящего непосредственно за ним) => ;
    Решение можно модифицировать так:
    Просто уходим от двоичной системы исчесления.
    Кажадый чиновник называет следующим Разницу между колпаками одного цвета.
    Напрмиер, Красных больше чем синих на три.
    Соответсвенно зная предудущую озвученую разницу и разницу чиновников перед ним. Он одназночно может определить какой у него цвет.

  • Stranger

    2shma
    И что это даст?

  • zhenechka

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

  • oligarh

    а если в колпаке нету дырок для глаз, что тогда скажете??

    • Лиля

      Решения все интересные, но вдруг чиновников действительно очень много? Да и такие факторы как волнение(им грозит смерть как никак), ошибки в подсчётах…и сбой всей системы. А может им стоит договориться о более простом решении? Например, если цвет колпака красный, произносить свой цвет быстро, а белый – разбить на 2 слога (им же никто этого не запрещал, может у людей манера речи такая, кто-то быстро говорит, а кто с расстоновочкой). Ну, у первого, бедняги, конечно 50% выжить.
      Например, 9 человек, КББКККБББ:
      Давайте в нашем примере спасём 1-го,он случайно говорит: КРАС–НЫЙ(если конечно не питает огромной ненависти к впередистоящему, иначе, злобно произнесёт слово быстро), следующий: БЕ–ЛЫЙ, третий: “БЕЛЫЙ!”, четвёртый: “КРАСНЫЙ!”, пятый: ” КРАСНЫЙ!”, шестой: КРАС–НЫЙ”, седьмой:””БЕ–ЛЫЙ”, восьмой: “БЕ–ЛЫЙ”, ну и последнему абсолютно всё-равно как произнести свой цвет, и он уже с радостью говорит “”Белый”. 
      Также можно делать модуляции с интонацией, например, имитировать акцент и т.п.. По идее, если нет ни одного “заподлиста” в очереди выживут все, ну…кроме первого, его судьба 50 на 50.

  • Дмитрий

    А зачем что-то считать? Они должны договориться, что если цвет колпака второго совпадает с цветом, который хочет сказать первый, то просто произносится цвет, а если не совпадает, то первый произносит цвет с каким-нибудь акцентом или оттягивает буквы или с какой-то интонацией или глотает буквы…(крАсный, красный, билый…). Поэтому, если чиновники честны и ничего не перепутают, то только у первого шанс 50/50, что он угадает свой цвет, а все остальные должны выжить.