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

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

Как и обещал, привожу ответ на первую задачу.

1. Царь построил своих чиновников в колонну (лицом к затылку следующего), надел по колпаку одного из цветов — красного или белого.. и сказал поочереди назвать цвет своего колпака. Кто не угадает — смерть. Первый отвечал тот кто видит всех и т.д. попорядку.. Вопрос: о чем должны договориться чиновники чтобы минимизировать кол-во смертей.

Исходим из предположения, что колпаки одеты случайным образом, а колонна достаточно длинная.

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

Если каждый нечетный по счету чиновник (1-й, 3-й, 5-й и т.д.) будет называть цвет колпака, находящегося перед ним, а каждый четный повторять названный цвет, то выживут все четные чиновники и половина нечетных. Это становится легко понятным если расписать возможные комбинации пар (Б – белый, К – красный):

БК – 1-й убит
ББ – 1-й жив
КК – 1-й жив
КБ – 1-й убит

Т.е. выживут 75% чиновников.

Обновлено: это решение оказалось не оптимальным, вот более правильное решение.

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

  • Stranger

    Всё хорошо за исключением утверждения:
    > “Т.е. выживут 75% чиновников”.
    Можно говорить толькоо математическом ожидании для достаточно длинной очереди.
    Предлагаю рассмотреть два варианта:

    1) ББББББББББ…(100%)
    2) БКБКБКБКБК…(50%)

  • Anonymous

    Да, это верное замечание, но я в ответе исходил именно из этих условий:

    >Исходим из предположения, что колпаки одеты случайным образом, а колонна достаточно длинная.

  • Stranger

    1. Думаю, что предложенный алгоритм является наилучшим. Нужно только точно сказать, что чиновникам (при использовании этого алгоритма) гарантируется то, что выживут:
    от 50% до 100%,
    а не
    75%.
    А то ведь в случае, например, 70%, уцелевшие владельцы колпаков могут предъявить претензии:).

    2. Не могу согласиться с утверждением:
    >”Как выяснилось, мое решение оказалось неоптимальным”.

    Думаю, что это решение оптимально.

  • Nirel

    Бред полный. Это, простите, блог программиста, я не ошибся?
    Самый последний (который видит всех) должен назвать нечетный цвет. При таком алгоритме вероятность выживания последнего 50%, все остальные – будут живы.
    Данный алгоритм так же работает для бесконечно длинной цепочки.
    Удачи :)

  • Anonymous

    2Nirel

    Да, это блог программиста, который любит решать логические задачи (и еще много чего любит).

    Не совсем понятно, как выживут все остальные. Возможно, имеется в виду вот это решение:
    http://developerguru.net/archive/2006/10/18/Interview-test-ABBYY-Software-Answer-1-_2800_continue_2900_.aspx ?

    Ну и для бесконечно длинной цепочки оно все же не работает.

    P.S. Я бы мог этот свой пост просто заменить более верным решением, но это решение – первое пришедшее мне в голову, оно правильное, хотя и неоптимальное.

  • Stranger

    2Nirel
    1.>Бред полный.
    По-видимому, это реакция на новые слова, такие как “математическое ожидание”? :)
    2.>”…должен назвать нечетный цвет…”
    А что такое “нечётный цвет”? Наверное, сиреневый… :)
    3. Данный алгоритм так же работает для бесконечно длинной цепочки…
    А как? Если можно, поясните…:(

    Думаю, что у программиста с логикой должно быть всё в порядке! => Предлагаю логический тест:
    Какие из приведённых ниже утверждений являются истинными?
    1. Незнакомые слова => бред
    (а если их больше одного, то – полный бред!)
    2. Могут существовать незнакомые термины, не являющиеся бредом.

    Удачи:)!

    Stranger

  • Arman

    Дааа, вижу давно тут никто не бывал :) предлогаю еще один вариант при котором 75% выживут:

    Тот кто отвечает первым называет цвет последнего, второй называет цвет предпоследнего, третий – цвет третьего с другого конца и тд… К середине опроса 50% первой половины опрашиваемыx будут живы а отальая половина будет знать точный ответ: 50+25 = 75%, есть :)

  • Timpsonn

    СИЛЬНО

  • Iceman

    Это неправильный ответ. Выжить могут все, либо без 1.

    Приравняем Красный колпак к 1, а Белый – к 0.
    Последний должен посчитать и сказать, если сумма нечетная Красный, если четная – Белый.
    Тогда следующий посчитав по тому же принципу сумму цветов колпаков стоящих впереди него сможет точно сказать, какой на нем колпак. Итд.

    Пример. Ряд КБКБКККБКККБККБК последний видит впереди 10 красных и пять белых, сумма 10, Ччтная, называет Белый. Не угадал.

    Следующий, Белый, видит впереди себя 10 красных и четыре белых. Сумма 10. Четная. Тот, что стоял сзади и видел его колпак тоже сказал Белый = Четная. Значит, его колпак не меняет четность. То есть 0=Белый. Прав. Жив.

    Следующий, Красный, видит впереди 9 красных и 4 белых. Сумма 9. Нечетная. Предыдущий сказал Белый. То есть четная. И перед ним была четная. Значит его колпак меняет нечетность. То есть – Красный. Прав, жив.

    Следующий, Красный, видит 8 красных и 4 белых. Сумма 8. Четная. Самый первый сказал Белый. Четный. Потом был опять белый, не поменялась четность. Потом был красный, поменялась. Сумма считая его колпак должна быть Нечетной. Он видит Четную. Значит его колпак – Красный. Прав. Жив.

    Следующий, Белый, после высказывания предыдущего понимает по тому же принципу, что считая его колпак сумма должна быть Четной. Видит он 8 красных и 3 белых. Четную. Значит и он белый.
    Итд.
    Выживают все, кроме последнего – 100%. Последний – 50 на 50. Если повезет и сумма окажется по “четности” равна его колпаку.

  • art

    ВЫ ТУТ НЕСЕТЕ БРЕД. Решение у этой задачи есть и очень простое. Nirel дал правильный ответ.
    В этом случае выживают все, кроме последнего с вероятностью 100%
    Последний выживает с вероятностью 50%