Comments 24
Вопрос 2
98, и по одной получат D и E за свои голоса. Хотя непонятно как они будут голосовать, если выгода равна.
Если считать 100 монет на двоих (с конца), то D получит все, а E 0. Так что для E не вариант доводить до такого исхода.
Если на троих — будет С — 99, D — 0 и E — 1.
На четверых B — 99, C — 0, D — 1 и E — 0.
На пятерых A — 98, B — 0, C — 0, D — 1, E — 1. Так у A получается 3 голоса, а D и E все равно больше никак не получат. Хотя, если пираты не сильно дальновидны, лучше предложить монету C, а не D.
Если считать 100 монет на двоих (с конца), то D получит все, а E 0. Так что для E не вариант доводить до такого исхода.
Если на троих — будет С — 99, D — 0 и E — 1.
На четверых B — 99, C — 0, D — 1 и E — 0.
На пятерых A — 98, B — 0, C — 0, D — 1, E — 1. Так у A получается 3 голоса, а D и E все равно больше никак не получат. Хотя, если пираты не сильно дальновидны, лучше предложить монету C, а не D.
А почему ты думаешь, что 2 маленьких пирата согласятся на 1 монетку?
Я бы предположил 2 варианта:
1)предложить разделить условно поровну деньги между 3 пиратами(34+33+33), в расчете, что 2 следующих пирата решат, что это наиболее выгодно, или же
2)Дать 2 малым пиратам по 21 монетке, мол это уже выше чем равная доля на пятерых, забрать себе остальное- 58.
3)а ещё есть улучшенный второй вариант- дать малому пирату 1 монетку, попутно объяснив, что если они дойдут до дележки между двумя, то он даже 1 не получит:) Итого большой пират получит аж 77 монеток.
Я бы предположил 2 варианта:
1)предложить разделить условно поровну деньги между 3 пиратами(34+33+33), в расчете, что 2 следующих пирата решат, что это наиболее выгодно, или же
2)Дать 2 малым пиратам по 21 монетке, мол это уже выше чем равная доля на пятерых, забрать себе остальное- 58.
3)а ещё есть улучшенный второй вариант- дать малому пирату 1 монетку, попутно объяснив, что если они дойдут до дележки между двумя, то он даже 1 не получит:) Итого большой пират получит аж 77 монеток.
Все монеты забирает последний. :)
1 — пираты D и E голосуют против. Пирату B в таком случае выгоднее слить A и самому распорядиться кассой.
2 — В таком случае не самый выгодный вариант для пирата А. Ведь он может иметь больше.
3 — Исходя из этой логики и был дан ответ. Самый выгодный для всех, учитывая условия задачи.
Задача не по писхологии, задача по математике/логике.
2 — В таком случае не самый выгодный вариант для пирата А. Ведь он может иметь больше.
3 — Исходя из этой логики и был дан ответ. Самый выгодный для всех, учитывая условия задачи.
Задача не по писхологии, задача по математике/логике.
Последний (младший) всегда может голосовать против, если не все монеты достанутся ему. Соответственно, все, кто предложит младшему не все монеты — умрут.
Младший при любом раскладе получает 0 либо 1. Посмотрите на случай с 2мя пиратами. Там младший не получает ничего. Соответственно ему не выгодно убивать 3го пирата.
Я за младшего (E).
A предлагает любой вариант кроме A:0, B:0, C:0, D:0, E:all. Я голосую против, A — умирает.
B предлагает любой вариант кроме B:0, C:0, D:0, E:all. Я голосую против, B — умирает.
C предлагает любой вариант кроме C:0, D:0, E:all. Я голосую против, C — умирает.
D предлагает вариант не D:0, E:all. Я голосую против, D — умирает.
Все монеты мои.
A предлагает любой вариант кроме A:0, B:0, C:0, D:0, E:all. Я голосую против, A — умирает.
B предлагает любой вариант кроме B:0, C:0, D:0, E:all. Я голосую против, B — умирает.
C предлагает любой вариант кроме C:0, D:0, E:all. Я голосую против, C — умирает.
D предлагает вариант не D:0, E:all. Я голосую против, D — умирает.
Все монеты мои.
Опять немного повредничаю на правах аналитика. :-) Крайне странно описывается процесс голосования. Если голосуют сразу все пираты (включая автора предложения), то разумно было бы написать «при равном числе голосов — предложение принимается». Ну потому что высказавший предложение пират голосует за него — это очевидно. «Решающий голос» обычно имеет место тогда, когда в группе имеется один не голосующий член (обычно — председатель), и если группа разделилась поровну — то выслушав аргументы каждой из сторон, ранее не голосовавший участник дает решающий голос. В общем, напиши мне такое клиент в пользовательской истории — я бы заставил привести уточняющие примеры, либо исправить формулировку, либо и то и другое сразу. :-) Также, непонятно насколько «кровожадны» пираты. Например, E понимает что в любом раскладе получит 1 монету. Если А предлагает ему 1 монету — он будет голосовать «за»? В принципе, он может проголосовать «против», пирата «А» скормят акулам, и ту же монетку ему предложит «Б». То есть ценность «остаться в живых» у пиратов прописана. А «оставить в живых» — нет! А это, на минуточку, может менять стратегии участников… Например, «A» в этой ситуации может предложить «E» две монетки, чтобы нарушить эквивалентность ситуаций у «E»…
999 крыс
10
это если за 10 часов — 10 крыс. А по условию у вас «Час» учитывая сроки жизни крысы после яда, у вас 1 итерация теста.
10 крыс хватит с избытком, т.к. 2^10=1024 (>1000). Надо пронумеровать бутылки и крыс, а дальше, для каждой крысы смешивать вино по определенному алгоритму так, чтобы в случае смерти — крысы бинарным кодом кодировали номер бутылки.
Разрешите дополнить ответ, просто для точности.
Докажем, что 9 и меньше крыс не хватит.
Рассмотрим пространство событий. У нас есть исходная ситуация — 1000 бутылок, среди которых одна отравлена. У нас есть 9 и меньше крыс, на которых мы опробуем вино тем или иным образом. Через час у нас будет не более 512 различных ситуаций (для каждой из 9 крыс будет известно мертва она или выжила). По принципу Дирихле в таком случае у нас будет не менее двух исходных событий, которые соответствуют некоторому результату. Простым языком это означает, что вне зависимости от того, как поить крыс, при каком-то из исходов будет ситуация в которой этот исход возможен если отравлена одна из двух бутылок, что не дает нам различить ответ.
Значит 9 крыс не хватит, а пример для 10 строится тривиально бинарным кодированием.
Докажем, что 9 и меньше крыс не хватит.
Рассмотрим пространство событий. У нас есть исходная ситуация — 1000 бутылок, среди которых одна отравлена. У нас есть 9 и меньше крыс, на которых мы опробуем вино тем или иным образом. Через час у нас будет не более 512 различных ситуаций (для каждой из 9 крыс будет известно мертва она или выжила). По принципу Дирихле в таком случае у нас будет не менее двух исходных событий, которые соответствуют некоторому результату. Простым языком это означает, что вне зависимости от того, как поить крыс, при каком-то из исходов будет ситуация в которой этот исход возможен если отравлена одна из двух бутылок, что не дает нам различить ответ.
Значит 9 крыс не хватит, а пример для 10 строится тривиально бинарным кодированием.
Если вас не затруднит, приведите пример тривиального бинарного кодирования. Мне видится, 10 достаточно только для покрытия начального пула, а вот для определения конкретики «нужно больше крыс!»
Пронумеруем бутылки от 1 до 1000. Для удобства сразу запишем номера бутылок в бинарном виде: 0000000001, 0000000010, 0000000011, ..., 1111101000.
Для каждой бутылки будем трактовать эту последовательность как инструкцию для того, кому из крыс давать вино из этой бутылки. Например, для бутылки номер 2 — 0000000010 — первым 8 крысам ее не даем, девятой — даем, десятой не даем.
После смерти крыс переводим их состояние в обратной последовательности. Грубо говоря, если умерли первые две и последняя крысы, значит отравленная бутылка имела номер 1100000001 — бутылка номер 301.
Для каждой бутылки будем трактовать эту последовательность как инструкцию для того, кому из крыс давать вино из этой бутылки. Например, для бутылки номер 2 — 0000000010 — первым 8 крысам ее не даем, девятой — даем, десятой не даем.
После смерти крыс переводим их состояние в обратной последовательности. Грубо говоря, если умерли первые две и последняя крысы, значит отравленная бутылка имела номер 1100000001 — бутылка номер 301.
Вот немного повредничаю со стороны не программиста, а аналитика. А никого не беспокоит факт, что из-за, э-э, конечной вместимости крысы — некоторые животные получат пониженную концентрацию действующего вещества по сравнению с оригинальной бутылкой? Если мне не изменяет память, то отравляющим веществам приписывается характеристика LD50 (измеряемая в (милли-, микро-) граммах на кг живого веса. И при этой концентрации вероятность гибели подопытного организма составляет 50%. Таким образом, исходное положение условия задачи «выпившая отравленное вино крыса умирает в течение часа» не эквивалентно положению «выпившая разбавленное отравленное вино крыса умирает в течение часа». Исходя из этого, я предложил бы использовать 20 крыс, причем вторую половину поить по принципу дополнения до единицы (одну напоили 100100111 — значит вторая получает вино из бутылок 011011000). Тогда в каждой паре через час должна подохнуть ровно одна крыса. Если в какой-то обе живы — значит концентрация сравнима (или даже ниже) LD50 и весь эксперимент ненадежен. Если обе подохли — вас подставили, и отравленных бутылок больше одной. :-) Или крыса подохла от случайного фактора. И дальше это плавно превращается в задачу о помехоустойчивом кодировании… В общем, если тестировать не математиков (у которых крысы, отрава и вино идеальные), а программистов — десять крыс маловато будет…
Уверяю Вас, что это типовая ситуация. Правильный ответ на любой вопрос/задачу полностью зависит от окружения и контекста, но отталкиваться, при формировании ответа, всё же следует от идеального математического решения.
А это, в свою очередь, зависит от целей — для чего мы решаем эту задачу. Если это просто красивая оболочка для задачи двоичного кодирования и дерева выбора — тогда ответ очевиден. Если же вторая сторона хочет оценить способность кандидата решать задачи из жизни (а не из идеального мира) — уже не так очевиден. А главный недостаток задач заключается в том, что применяют на собеседовании их, как правило, бездумно и бессистемно. :-( В норме — задача должна быть поводом к разговору, и способом оценить умение кандидата думать и находить решения. В большинстве случаев, интервьюеры просто поставят плюсик если вы дадите ответ 10, или крестик — если любой другой…
Вообще, это напоминает мне задачу с двойным дном из физики с далеких школьных факультативов. Разбиралась с Ланкиной Маргаритой Павловной, низкий ей поклон и долгих лет жизни. «Надутый воздушный шарик сильно надавили пальцем. Где он лопнет?». Первый ответ интуитивный — где надавили. Потом вспоминаем про давление в среде газов (распределяется равномерно) — значит лопнет в произвольном месте (где тоньше или есть дефект). Потом еще раз вспоминаем что под пальцем оболочка проминается и растягивается локально (остальная часть шара в первом приближении так и остается сферической). Следовательно, в шаре без дефектов производства — наиболее вероятен прорыв где-то в зоне нажатия. Если взять школьный сборник задач (или ЕГЭ) — в нем ответ «под пальцем» будет, хи-хи, неправильным!
Задачка с конями не программерская, там чисто на комбинаторику. Например, если N и M больше 4, то у первого коня есть 4 угловые позиции, где он бьёт 2 поля (и таким образом второму запрещено вставать на 3 клетки), 8 позиций на краю доски рядом с углом (по 3 битых поля), 4 позиции на диагонали рядом с углом (по 4 битых поля), 2N+2M-16 клеток на краю (по 4 битых поля), 2N+2M-16 клеток на рядах рядом с крайними (по 6 битых полей), ну и всё остальное, где конь бьёт 8 полей. Это всё правильно просуммировать, будет ответ.
Sign up to leave a comment.
Выпуск#31: ITренировка — актуальные вопросы и задачи от ведущих компаний