Комментарии
анонимно
developers.org.ua решили опубликовать замечательный цикл “Трудные вопросы на собеседовании” на русском языке. Каждую неделю будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую мы преследуем этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений. Итак!..
Задача #1
Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого.
У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.
Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).
Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов?
Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?
Источник http://www.developers.org.ua
← Вернуться к журналу «CHaos»
подумал:) что если в моем решение ошибется хотя бы один гном) то такие потери будут:)
Не люблю я такие задачки))) Мозгов не хватает на их решение) Или просто лениво)
з.ы. А меня в тупик поставил вопрос: "А какие у вас в университете были любимые предметы?" Тупил страшно)))
ЖЗ-)
ну как я понял здесь смысл в том что этим вопросом на собеседовании определяется склад ума человека - матиматический, аналитический там, хренанический итд... важен не результат, а способ решения. а вариантов решения здеся туева хуча.
а для меня самым сложным вопросом был "почему вы решили работать именно в нашей компании?" не навижу подобные вопросы.
Прочитав задание, я подумала только об одном: слава богам, меня на собеседование нужно убдет просто принести портфолио с проектами!
О_о
сегодня не мой день.. а так с удовольствием поломала бы голову над ответом..
бред...)) Может, и красиво, но вариант с шифрованной подсказкой нижестоящему проще и эффективнее, на мой взгляд)) и никого считать не надо)) если кто-то ещё что-то против имеет - переписывайте условие задачи так, чтобы исключить возможность такого решения (например, напишите в условии, что можно говорить только два слова "чёрный" и "белый" - там про это ни слова нет, тем более что розовых или серо-буро-козявчатых шляп тоже нет, чтобы думать, что значит "не белый" или "не чёрный"), ибо этот вариант вполне возможен и приходит на ум первым, и при этом тоже является верным)))
- какая разница, у него решение красивее твоего )
Саш, забыл дописать: "ЕЩЕ ОДИН правильный ответ"))))))))
- красивое решение, да
- Правильный ответ:
Один гном который называет цвет шляпы первым умрет с вероятностью 50%, остальные выживут, если будут придерживаться правильной стратегии. Первому нужно посчитать четность одного из видов шляп (договориться изначально какого и какой цвет сказанный первым что будет означать - четное количество или нечетное). Все слышат ответ. Первого гнома убивают (или не убивают, если случайно цвет означающий четность оказался цветом его шляпы). Теперь остальные гномы знают четное количество шляп, допустим, белого цвета или нет. Допустим количество четное. Следующий гном смотрит вперед, если количество все еще четное - он говорит что на нем черная шляпа. На следующем гноме шляпа белая. Он видит что впереди нечетное количество белых шляп и поэтому знает что на нем именно белая шляпа. Все последующие гномы теперь знают что количество белых шляп стало нечетным. Ну и так далее. Короче, при этой стратегии выживают в лучшем случае все, в худшем - одного первого гнома убивают.
- Ну какбэ правильный ответ в студию!
- Блин, а при чём тут "не красный"? У нас в логических уравнениях (свожу всю задачу на буквы) только две переменные - A и B, отвечающие за два цвета, и 4 варианта представления этих двух цветов - A, B, (not A), (not B)... Вопрос, нафига нам третья переменная C, отвечающая за отсутствующий цвет? Тогда ведь вся структура нарушается... Да и вообще, думаю, маги не настолько глупые, чтобы прослушать, как все гномы хором произнесут "Не Красный" - тогда смертность точно будет 100% )))))
- Тим, дай шоколадку лучше Саше, а то он перетрудился и не понимает просто того, что ему пишут..)
Шоколад полезен для мозговой активности
- Саш, ты что???)))) заработался совсем??)))
"не красный" - это неверный ответ просто по логике вещей.. во-превых, при чеме тут красный!!??)))
*я вот щас точно Афигею от этого всего*
во-вторых, представь, что гном слышит, что предыдущий сказал "не красный" (а шапки эти только 2 цветов: черные и белые).. Как тогда эту инфу он должен вопринимать??)) от этого ответа он что, получит информацию про свой цвет??)) Блин, а еще говорят, что у женщин нет логики...))
Не Белый или не черный в моем решении, это просто способ передать верный ответ следующему гному, намекнув на его цвет, при этом не выдав свой..))
Ты точно заработался.. я тебе во всех комментах это объясняю, а ты опять мне про этот красный..)))
- верный, да. а теперь сделай вхдох выдох десять раз и произнеси это вслух. по слогам. =)
- Было бы оно верное я бы согласился!
"Не красный" тоже верный тогда ответ...
- Мне интересно, долго ли Кеос будет отрицать верность Пушаниного ответа...)) Теперь ещё и к англицкому придираться будем... он тут ни при чём))) Это чистой воды логика, информатика, любой абитуриент, прошедший курсы по информатике ответ найдёт по этому пути))) Так что язык тут ни при чём)))
Оль, от Саши ты шоколадки, как я вижу, не дождёшься))) Давай я тебя угощу ;)))
- Точно) я придираюсь) слово девчОнка пишется через О)
- да меня как-то не тревожит факт моего знания или незнания решения. мне пушаню жалко, девченка права, а ты придираешься =)
кусок солюшна с оригинала:
There is a less mathematical but equally valid way for the dwarves to convey what they see to the next in line, which is to simply encode it in the response (alternating the pitch of the response, the pause before the response, the length of the response, etc. according to coded values for black v. white) - without saying anything but their response to the Question. This is basically just a different way than the parity solution of conveying information to the next dwarf.(с)everything2.com
а вообще я хотел сказать что-нибудь типа "а вот и не подеретесь", но захотелось повыпендриваться.
- Оля, ты мне объясняешь как маленькому мальчику, спорить больше с тобой не буду, но решение твое в корне не правильное.