Сработал МУТАГЕН из прошлой задачи OFF: Поиск паука-матки в лабиринте (Python)
Теперь всё чаще вылупляются дружелюбные пауки, которые вообще не трогают людей, просто проходят мимо и вообще веганы (не едят мясо). Но замечено, что такое дружелюбное поведение у них сохраняется только когда вокруг такие же дружелюбные пауки. И при этом их поведение становится даже более разумным!

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

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

Сказано — сделано! С помощью телепортатора отобрали 1000 вроде подходящих пауков и переместили их в ангар базы. К ним запустили овечку и никто её не сожрал, т.е. вся тысяча гарантированно дружелюбная!

И всё шло хорошо, но камеры засекли, что ночью на базу прокрался один злобный паук и убил одного дружелюбного (вот валяется труп), а пауков опять тысяча, только теперь все злобные! Они даже сожрали овечку, набросились всем стадом!

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

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

(1) Пауки прикрыли гнёзда металлизированными сетями и теперь луч телепортатора не работает.

(2) И даже наш ангар на базе? Я предлагал из него отбирать.

Есть ещё простое решение: рассаживаем пауков по одному, потом по очереди подсаживаем к ним овечек. Т.к. овечек 10, то можно подсаживать сразу к 10 паукам, что сократит время выявления.

Тот, кто сожрет овечку - тот и злобный.

(3) На базе теперь все злобные.
(4) Идея правильная, но для деления групп по 10 нужно 100 овечек, а овечек всего 10.

Когда я вижу 10 и 1000, то сразу вспоминаю, что 2¹⁰ = 1024 )

(7) Да, есть тут какая-то бинарность. Сожрут или не сожрут...

(5) Не нужно 100 овечек. Берем первые 10 пауков - и 10 овечек (отдельно по паре паук-овечка). Если одну сожрали - то всё, паук найден. Если не сожрали - то хороших отсаживаем отдельно и берём следующих 10 пауков, овечки-то целы.

(9) Ну так достаточно и 1 овечки. Просто понадобится 1000 испытаний, когда задачу можно решить за минимальное количество испытаний.

Делим пауков на 2 группы по 500, запускаем в обе овечку. В которой сожрали - уничтожаем, оставшуюся оставляем размножаться)

(11) Так Вы уничтожите 499 добрых пауков, что войдёт в историю добрых пауков и станет миной замедленного действия для будущего сотрудничества.

(10) вот так и не жалко вам овечек ради скорости)))

(12) А мы им не расскажем. Мы скажем, что добрых пауков убили злые.

(12) А сколько можно уничтожить добрых? 259 норм?)

(15) нисколько

(13) А чего их жалеть, они же неразумные. А тут 999 разумных добрых пауков, которые построят новую цивилизацию, вот их надо жалеть.

Ну а вообще быстрее всего так: Делим пауков на 11 групп. 10 по 91 и 1 с 90. К 10 подсаживаем овечку. Если в какой то съели то злой там. Если не съели то в последней. Потом делим на 10 групп 9 по 9 и 1 с 10ю. К тем что по 9 сажаем овечек. И на последней итерации делим по 1 пауку. Итого за 3 раза определяем.

Получается 10 (пока)

(18)
1 итерация выявила группу из 91 пауков.
2 итерация какая?

(20) разбить на 10 групп. 9 по 9 и одна по 10. К 9 первым группам сажаем 9 овечек.

Если съели то разбиваем по одному и к 8 первым паукам сажаем по овце. Если не съели то овец остается 9 и тогда к 9 паукам сажаем по овце.

Кстати этим методом можно было бы за 3 итерации отфильтровать 1010 пауков.

(18)(21)(22) Да, сработает.

(24) Точно. Ну тогда даже проще.

Если пополамить, то как раз максимум 10 овечек и хватит.

(26) Это если у них там 1с) Но задача то про алгоритмы)

Странно, что здесь в задаче про пробирки и мышей получилось 3-4 дня.
https://dzen.ru/a/XiAi4OT_8ACtwr-K#zadacha_pro_tsyachy_probirok

Не пойму, почему у нас получилось 3 испытания строго.

Зачем кого-то одного искать? В условиях же сказано "теперь все злобные". Бери любого - он будет злобный.

(29) Они злобные по поведению только в присутствии злобного по геному. Читайте условие внимательно.
А отобрать надо 999 добрых по геному.

(11) Зачем такие сложности? Спалить всю тысячу и не мучаться. А из овечек приготовить вкусный шашлык и нашить цигейковых шапок на зиму.

(28) они первый раз делят на 10 групп, а нужно на 11.

(31) 7 овечек на шашлык не хватит? Слушай зачем так много шашлык? А так и шашлык и добрый паук. Всем радостно!

(32) Да. Причём 11-я группа бОльше по размеру, нежели одинаковые первые 10 групп, т.к. для неё опять будет 10 целых овечек, а для одной из первых 10-ти групп останется 9.

Тут можно использовать метод троичного деления
Делить исходную группу пауков на 3 части и в первые две запускать по 1 овечке
Если сожрали - в той группе есть злобный, берем ее и так же делим
Если не сожрали - злобный в группе без овечки

+(34) Например:
1. 90 ... 90 100
2. 9 ... 9 10
3. 1

(36) не эффективно, делить на 3 группы лучше поровну

(37) Я делю на 11 групп: 10 по 90 и 11-я 100.
Если не сожрано, то 11-ю группу делю опять на 11 групп: 10 по 9 и 11-я 10. Если не сожрано, то третьим ходом сразу находим вражину, имея так и оставшиеся целыми 10 овечек.

(37) что это не эффективно? Мы быстрее находим и меньше овец расходуем.

Ну а если на первом ходе сожрали, то имеем 9 овечек на 90 пауков. Делим на 10 групп.

(38) я примерно так и предлагал.

(41) Ключевое у нас, что последняя N_овец+1 группа бОльше.

(42) да так можно даже 1021 паука протестировать.

(38) понял разом всех 10 овец решили использовать, поэтому разбиение на 11 групп

(44)+ тут вопрос это считается за всего 1 испытание или за 10?

вроде как "запустить овечку в некую группу" - отдельное испытание
и неважно если их делается несколько параллельно

(33) Конечно не хватит, там же ещё плов, димляма и другие вкусности. Да и друзей и соседей завсегда попотчевать надо. А с пауков какая корысть?

Поскольку вывод нужно делать однобитный: сожрали или нет, то вряд ли есть что-то лучше дихотомии. Даже сомневаюсь, что если группы делить 1:2 сильно убыстрит процесс, поскольку требуется гарантированное уничтожение засранца.

(46) В некоторых странах пауков едят.

(46) "А с пауков какая корысть?" Пятница из фильма про Робинзона с Куравлевым мог бы возразить...

(46) Ну возможно шелк. Если они шелкопряды.

(47) ну вы же не будете есть разумных пауков. Причем тех что могут съесть целую овцу.

Кстати это идея!!! Можно же овцу поделить!! Тогда будет много тестовых кусков))

(49) Разве бывают пауки-шелкопряды? Так-то обычно бабочки этим занимаются.

(52) Ну это же инопланетные пауки.

(50) Так-то и у овцы есть какой-то разум.

(49) Шелкопряд — как бы бабочка (гусеница)
(47) Мне доводилось и попротивнее еду тестить, но без этого всяко можно обойтись. А вот жирная баранина — очень вкусный и питательный продукт. Про овечий сыр даже и говорить не нужно — вкусно, питательно и полезно.

(52) у Колина Уилсона были.

(54) У овцы самец — баран, какой там разум?

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

(54) Верное замечание. Но есть разумных овец как то привычнее.

(58) я бы наверное умер от такого)

(60) Скорее бы добавки попросил. Когда курдюк под плов или димляму растапливают, запах такой что готов полказана съесть. Но особенность у баранины , что есть её нужно максмально горячей, практически обжигаясь, имеется. Но вкуснотища ведь.

(61) Ну плов да люблю. Но даже он жирноватый по мне.

ИМХО 10 овец запустили это 10 испытаний, или даже 11 если считать по тому на сколько групп делили а не 1.
Вопрос сколько минимум овец может погибнуть прежде чем выясним злобного паука по этой методики их всего 3 погибает.
А так
1 500/500 -1
2 250/250 -1
3 125/125 -1
4 62/63   -1
5 31/32   -1
6 16/16   -1
7 8/8     -1
8 4/4     -1
9 2/2     -1
10 1/1
10 итераций овец хватает.

(55) "жирная баранина — очень вкусный и питательный продукт" - В последнее время предпочитаю менее жирную ягнятину. От жирного нехорошо становится.

(63) меньше или равно 1000 итераций:
всех пауков по очереди запускаем к овце.
подбегает- на ему по хребту.
все овцы целы.
о-оптимизация.