Ещё задачки на сообразительность

Боянь.

Первый в ответе кодирует четность красных или синих шапочек у оставшихся.

это очень легкая задачка. можно обойтись 1 смерью

Давай от себя тоже задачку.

Вот кстати ещё такая: какой должна быть толщина ребра монеты, чтобы вероятности выпасть на орла, решку и ребро были по 1/3.

только просьба не лезть в инет, тем есть решение

Главное, чтобы первым отвечающим выбрать того, кто не знал, что за неправильный ответ убивают. Иначе будет массовая резня ещё в прощессе сговора.

PI*R/2

Такая?

необходимо, чтобы площади поверхностей были равны? так?

Я честно говоря сам ответа уже не помню, но смысл в идеи решения.

там что-то R/sqrt(2)

дада)

R/2

Тьфу, совсем отупел... Пи не сократил. R/2 или d/4.

>необходимо, чтобы площади поверхностей были равны? так?

А почему?

Ну да. Я исходил из того же принципа. Только правда сначала ответ запостил неправильно, но потом засомневался, на бумажке написал и понял, что облажался в пи раз.

А вот ещё:

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

>А почему?

я не могу этого вывести.

Да, монету нужно вписать в сферу.

>Да, монету нужно вписать в сферу.

не понял. можешь строго доказать, что отношения площадей должны быть равны?

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

Спрашивали на собеседовании в yandex

Ответил, что надо делить на пары и асимптотически будет log(n)

Как доказать оптимальность хз.

PS в yandex не взяли :)

Вероятность 1 приходится на полную площадь сторон и ребра. Так как стороны одной площади, получаем для вероятности 1/3 площадь ребра равную площади стороны. Такая вероятность сразу намекает на решение. Лучше бы вероятность сделать отличную, например 20%. Тогда будет 40%+40%+20%. А при 33,3(3) даже голова не включается, всё решение на уровне спинного мозга.

площади поверхностей, образованные отсечением сферы.

два колпака и полоска.

а откуда слеует, что падение на каждую точу поверхности равновероятно? если падение на участки одинаковых площадей основания и боковой стороны разновероятно?

> Главное, чтобы первым отвечающим выбрать того, кто не знал, что за неправильный ответ убивают. Иначе будет массовая резня ещё в прощессе сговора.

Знаешь, если собрать парнишек с моего выпуска, что вряд ли кто-то в живых останется из самих мелкософтовцев из условия ;)

>площади поверхностей, образованные отсечением сферы.

как вписать монету в сферу?

Либо я пива перепил, либо одно из двух.

Площади смотрятся не монеты, а сферы. Сфера падает на каждую свою точу равновероятно.

Сначала делим всех на две половины. В первый день болеет одна половина, во второй вторая.

В следующую пару дней делятся на 2 части

В первой части - половина из первой половины + половина из второй половины и т.д.

Во второй части все остальные.

А что здесь такого, цилиндр идеально вписывается в сферу.

>Площади смотрятся не монеты, а сферы. Сфера падает на каждую свою точу равновероятно.

Сфера да, а монеты?

>А что здесь такого, цилиндр идеально вписывается в сферу.

нда, точно, тогда все предельно ясно. спасибо.

> Ответил, что надо делить на пары и асимптотически будет log(n)

Хм... А в течении дня скольких можно посетить? Если всех больных, то болеют по 15 по очереди, будет каждый раз количество посещённых уменьшаться в 2 раза, пока не останется последний, затем умножаешь это число на 2, так как болеть самому тоже надо. Получается где-то 12 дней. Если только одного, то 30 дней без выбора.

> Да, монету нужно вписать в сферу.

Да, ты прав. Сыплю голову пеплом. Но считать площади сегментов шара сейчас не могу, хотя надо просто вспомнить формулу. Так что мой ответ коту под хвост. Надо было голову включать, а не полагаться на спинной мозг.

А ещё такая задачка, боян бояном правда.

Есть 5 коробок, в них по 10 таблеток. В одной из коробок таблетки бракованные - весят по 9 грамм. Нормальная весит 10 грамм.

Как за одно взвешивание определить где бракованные?

>А в течении дня скольких можно посетить?

Все здоровые идут ко всем больным. Если болеет 5 человек, то толпа из 25 человек побывает у каждого больного.

Мой ответ на примере из 8 человек

Больные по дням

1) {1 2 3 4}

2) {5 6 7 8}

3) {1 2 5 6}

4) {3 4 7 9}

5) {1 3 5 7}

6) {2 4 6 8}

Всего 6 дней.

>Но считать площади сегментов шара сейчас не могу

нда, правильную формулку теперь потруднее вывести =))

баян =)

>как вписать монету в сферу?

элементарно. Строится сфера а в нею вписывается монета =) Из условий задачит нужно делать так

PS: Если со сферой, то получается h=R/3. Так, или нет, а то опять в уме считал.

а приведи все выкладки?

>нда, правильную формулку теперь потруднее вывести =))

Да бог с ней, с формулой. Это не суть важно.

Манета может крутится в воздухе, отскакивать и т.д

Для шара все очевино, а для монеты?

> Все здоровые идут ко всем больным. Если болеет 5 человек, то толпа из 25 человек побывает у каждого больного.

Есть две крайние точки у решения. 1 человек болеет = 30 дней, 29 человек болеет = 30 дней. Это явно максимумы. Минимум будет посередине.

>Манета может крутится в воздухе, отскакивать и т.д

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

интересно еще, а единственно ли это решение?

>Есть две крайние точки у решения. 1 человек болеет = 30 дней, 29 человек болеет = 30 дней. Это явно максимумы. Минимум будет посередине.

Ну примените это рассуждение к моему примеру с 8 человеками.

Низачет.

PS есть ли у кого знакомые программисты из yandex-а Может кто нибудь откроет страшную тайну, как доказывается оптимальность (ну или есть ли более оптимальное решение, кроме того рекурсивного)

>я так понял, что задачка н физическая а геометрическая =)

Да нет. Геометрическая сторона решения очень простая.

У сферы все точки наверняка равновероятны. Поэтому берём проекции с поверхности сферы на центр масс монеты (цилиндра). Это должно обеспечить необходимую физику при приземлении. Границы разделов для устойчивого равновесия при приземлении будут определяться именно окружностями на сфере, образованными вписанным цилиндром. Дальше остаётся только считать площади шаровых сегментов. ЕМНИП S1=2*Pi*R*H, для шара S2=4*Pi*R^2. По условию задачи (4*Pi*R^2)/3=2*Pi*R*H и... хахаха, я опять в уме облажался. В 2 раза. Чего-то туго у меня в пятницу вечером с арифметикой. Пора об стенку и спать.

>Да нет. Геометрическая сторона решения очень простая.

ну сфера - это да, несложно. впрочем я не догадался =( а вот физика сюда уже ни как не влазит. придется считать траектории, брать по ним интеграл от функции, которая отображает траекторию в итоговую позицию, учитывать потери энергии при отскоке (иначе монетка просто будет прыгать вечно и рещения будет - любая =))

> Ну примените это рассуждение к моему примеру с 8 человеками.

Болеют по одному = 8 дней. Болеют по 7 = 8 дней. Ты привёл пример для 4 из восьми, получил 6 дней. 6 дней явно меньше, чем 8, то есть болеть по 4 более оптимально. Что не так?

> Низачет.

А если подумать?

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

> придется считать траектории, брать по ним интеграл от функции, которая отображает траекторию в итоговую позицию, учитывать потери энергии при отскоке

Нафига? В зачёт идёт только одно касание -- последнее. На всю предысторию наплевать, как бы она там себя ни вела.

> Мне вот интересен смысл таких задач на собеседованиях. Имхо нужно спрашивать чем занимался человек, а не всякую такую тегомутину.

Это позволяет отделить хомо сапиенсов от хомо зубретикус.

>Нафига? В зачёт идёт только одно касание -- последнее.

а собственно почему? если условия задачи понимать так - монета может быть брошена из любой точки в верхнем полупространстве над плоскостью, с равномерным поляем тяготения (или над притягивающим шаром), с любыми начальными скоростями, и считать вероятность по всем параметрам, не факт что геометрическое решение верно. просто это уже придется учитывать что после некоторых начальных условий оно отскочет, и что после отскока она может полететь в силу своей формы тоьлко так.

но безусловно это уже рассуждения в духе есть атмосфера/ нет атмосферы или а учитывать ли квантовые явления =)))

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

здоровые в один день по очереди посещают всех больных.

или я чего не допонял?

> а собственно почему?

Просто подумай о законе больших чисел. Предыстория действительно не важна и не нужна. Не надо случайность и статистику завязывать на детерминизм.