Вторая задача с YaC2013. Perla negra.

27.12.2013

Марина Лебедева

Итак, пришло время для написания статьи с задачами с YaC 2013. Эта задача третья по списку со стенда ШАД и вторая, которую мы расписываем в нашем блоге (первая). И она посвящается пирату.

Почему мы выбрали следующей её? Именно из-за главного героя. Он же пират! Кто из нас в детстве не хотел стать пиратом, бороздить моря, океаны, пить ром и носить на плече говорящего попугая? Хм, что-то отошёл от темы…

Задача следующая, называется «Perla negra»:

Слепой пират захватил 20 корзин с жемчугом. В 19 корзинах жемчуг белый, а в одной чёрный. Черная жемчужина весит в 2 раза тяжелее белой. У пирата есть чашечные весы без гирь, которые издают щелчок в момент, когда весы приходят в равновесие. Пират никому не показывает свой трофей, а хочет сам найти корзину с черным жемчугом. Как ему это сделать за одно уравновешивание весов?

На самом деле, решение кроется в самом задании.

Один из ключевых пунктов этой задачи — одно уравновешивание, то есть взвешивать можно сколько хотите раз, но только до тех пор пока весы не уравновесятся.

Совсем недавно задал эту задачу своим знакомым и обнаружил, что они идут сразу же по неверному пути, говорят:

«Мы возьмём из первой корзины одну жемчужину, положим на одну чашу весов, из второй — так же одну и отправим на вторую чашу весов. Затем оставим содержимое первой чаши весов неизменной, а жемчужины второй чаши будем менять на жемчужины из других корзин».

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

Вчитаемся снова в текст задачи. В ней решение. Увидели цифру в задаче? Отлично! Это тот второй ключ, который даёт решение. Чёрная жемчужина в 2 раза тяжелее белой.

Вот оно и решение:

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

Мы отыщем корзину с чёрным жемчугом при любом исходе:

1. Когда у нас весы уравновесятся. Корзина жемчужина из которой находится на второй чаше полна чёрного жемчуга.

2. Когда у нас весы не уравновесятся после прогноза по всем корзинам. Таким образом, первая корзина — корзина с чёрным жемчугом.

  • Общее

Комментарии

Добавить комментарий

Вы вернулись, чтобы дочитать статью? Кликните на меня, я найду то место, где вы остановились.