Комментарии
анонимно
developers.org.ua решили опубликовать замечательный цикл “Трудные вопросы на собеседовании” на русском языке. Каждую неделю будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую мы преследуем этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений. Итак!..
Задача #1
Есть две деревни: деревня магов и деревня гномов. Раз в год маги проходят по деревне гномов и выстраивают их по росту в возрастающем порядке, так что каждый гном может видеть только тех, кто ниже его самого.
У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.
Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).
Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов?
Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии?
Источник http://www.developers.org.ua
← Вернуться к журналу «CHaos»
Саш, и GITS тебе пишет не про то, что там надо или не надо. а про то, на чем мое решение построено))))
- Саш, ты опять не то говоришь.. Где ты видел, чтобы в моем решении проскальзывала какя-то неопределенность?))
(это я про "да, нет, наверное").... Даж поражаюсь.. ты между строк такое находишь?)))
По моему решению был четкий ответ.. Или я где-то писала, что один из гномов должен опустить глазки, поковыряться ножкой в песочке и так скромно протянуть: "Да навееееерное.."))))))))
С точки зрения логики, Орион правильно написал... про операцию отрицания.. На этом построено множество программ и задач.. и в них нет, знаешь-ли, никакой неопределенности типо "наверное-не знаю.."
Аж смешно говорить про такие очевидные вещи))
Кстати, Данила, а ты правильный ответ знаешь? судя по "верный решение в кодировании ответа чтобы передать информацию о цвете шляпы последующему", ты ответ правильный не знаешь. Там не нужно передавать от гному к гному правильный ответ о цвете его шапки
- GITS - вот настоящий мужчина))) Знает, когда надо остановиться и дать девушке понять, что она была права))) Тем более, если она на самом деле права :-D
- Данила, да не ответила она правильно, просто спорщица большая!
Оля, ты вроде бы английский знаешь, так вот в английском(а именно оттуда пошла задачка) и вспоминая Задорнова, ответ "Да нет, наверное" не принимается
- чаос, кончай занудствовать, пушане шоколадку за верный ответ ) какая разница тянуть звуки или добавлять частичку "не" суть от этого не меняется. верный решение в кодировании ответа чтобы передать информацию о цвете шляпы последующему :P
Кстати, даже не столько математическая, сколько логическая))
з.ы.: ....а с женской логикой лучше не спорить ;))))
- Саш, ты сам признал, что задача математическая, а я нашла лазейку для ее решения..)) Нашла.. и не только лазейку, но и решение))) хи-хи)))
- 2 0RI0N: поддерживаю))) действительно, противоречий нет никаких в решении)))
- А впрочем, я уже посмотрел и убедился, что условие полностью совпадает с оригиналом, так что....!) Решение (по крайней мере, один из вариантов) благополучно найдено) "Счёт, пожалста!" (с) ))))
- Хосподи... фразеологический оборот, антицвет... при чём тут это?))) цвета два) обзовём их буквами A и B... тогда с ними можно выполнять любые логические действия, в том числе и унарную операцию отрицания, говоря про (not A) и (not B) )) И так как A=0, а B=1, то (not A)=1=B, а (not B)=0=A...) Всё весьма элементарно, правильно, и фразеология и антицвет тут ни при чём)) И если в условии задачи стоит фраза "...какого цвета шляпа...", то отвечать чётко "чёрная" или "белая" совершенно не обязательно) Если ты просто скопипастил условие задачи, то решение найдено)) если нет - требую оригинального условия задачи, где было бы сказано: "...каждый гном может ответить лишь "чёрная" или "белая"..."!))) Тогда я успокоюсь :))))
ээ... вооот...(с) ))))
- Сашенька, изначально твоя речь не имеет никаких недостатков..)))) Но вот последний коммент - по поводу "если бы все гномы ответили "Не красный", то все бы были живы" я готова поспорить....))))
Я делаю вывод о том, что ты не уловил логики моего решения.. если бы уловил, то не сказал бы такую глупость))
Если бы гном сказал "не красный", то след. гном хрен бы понял, какой у него цвет)) Или того хуже, подумал бы, что говорящий просто-напросто свихнулся)) Потому как по условию цвета два всего... черный и белый)
А ты прицепился к этому "фразеологическому обороту и антицвету"...)
Люди вообще часто отвечают на вопросы "антиответом")))
Например, на вопрос "Сложно ли тебе было решать эту задачу?" отвечают: "Ну уж точно не легко"))))
Или на вопрос "Много ли было допущено ошибок в документе?" отвечают "Немало"))))
Так что тут ты меня не переубедишь)) Я права в своем решении, и тут даже не докопаешься)
А то, что есть еще одно решение - математическое - так это пожалуйста..) Я его оспаривать не буду))
Чем оспаривать мой вариант, лучше бы посидел и подумал над каким-нибудь третьим решением)) Авось найдешь)))
- Оля, Если твой ответ считать правильным, то решение можно найти гораздо проще, если бы все гномы ответили "Не красный", то все бы были живы.
- Притом мое мнение условие правильно составлено:
"они спрашивают его, какого цвета шляпа не нём надета."
Нужно назвать цвет, а не фразеологические обороты и не антицвет)
- Оля: условия не я придумал.
С 50% я тормознул, т.к. действительно сразу допер, что ты помимо черный и белый еще что-то добавляешь.
Есть нормальное решение с ответами гномов "черный" и "белый"
так, что Оля думай) ты кстати на верном пути) ты умная допрешь:)
Гитс: у нас давно в чате любят решать загадки, только некоторые загадки не приживаются, а другие приживаются, за эту вроде бы народ ухватился:)
- Саш)))) тогда в условии бы прописать это надо, тебе так не кажется?))
- Пушаня, так говорить-то можно только "черный" или "белый"
Гитс, я поместил задачку, которая мне понравилась, для тех, у кого только фос.
ещё гномик может снять шляпу, посмотреть какого она цвета и ответить
- Так шеренги или колонны? уж разберитесь состовители задачки! это разные вещи!
- Кеос, не парь людям голову, Пушаня дала совершенно верный ответ )гном кодирует ответ так чтобы последующий понял какой цвет у него. макс потери 1 штук.
а вообще.. ты все задачки планируешь сюда копипастить? )
есть мнение что с acm.sgu.ru/olimp задачки поинтересней будут, да и больше их там ;)
а ещё вот этот блог community.livejournal.com/coding4fun_ru настоятельно рекомендую, есть ещё зарубежный его аналог . и вообще много чего ещё есть.. итого постов у тебя на несколько лет вперед даже с учетом того что ты каждый день выкладывать будешь.
кстати годика через 2 можно начинать среди прочего выкладывать NP-полные задачки, люди не заметят и всеравно по инерции будут решение искать. авось найдут ;)