Найдите самый тяжелый мяч, задав не более 8 вопросов

Question

дано 6 шаров с отличающимися весами.Цель состоит в том, чтобы найти самые тяжелые из этих шаров.

Проблема идет в форме ответа на вопрос, то есть мы должны задавать вопросы, и разработчик проблемы дает нам ответ.Каждый вопрос состоит из предоставления 5 показателей из шести.Ответ возвращается с индексами 3 ^rd самый тяжелый и 2 ^nd самый тяжелый мяч (в этом порядке).Мы можем задать не более 8 таких вопросов, чтобы найти самый тяжелый шар.

Пример:

Скажем, индексы шаров - 1,2,3,4,5,6.

Q : 1 2 3 4 5     A : 3 4   (here 3 is the third most and 4 is the second most heaviest of the 5 balls)

Q : 1 2 3 4 6     A : 3 4

Q : 1 2 3 5 6     A : 3 5

Q : 1 2 4 5 6     A : 4 5

Q : 1 3 4 5 6     A : 4 5

Q : 2 3 4 5 6     A : 4 5

Этих 6 вопросов достаточно, чтобы установить, что мяч с индексом 6 является самым тяжелым.(Еще 2 вопроса могут быть заданы - нам не нужно минимизировать количество вопросов. Также эти запросы могут или не могут упорядочить все 6 чисел, наша цель - найти только самые тяжелые).

---

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

Answer 1

Я думаю, что это можно решить таким образом, например:

Ввод: 24, 7, 12, 1986, 6, 99

Q1: Give me second and third from set {24,7,12,1986,6}
A1: second 24, third 12

Теперь из этого ответа мы знаем, что24 и 12 никогда не будут самыми тяжелыми.Таким образом, мы можем просто помнить, что idx {0,2} не будет принадлежать нашему ответу.Теперь давайте добавим idx 5, о котором мы ничего не знаем.

Q2: Give me second and third from set that includes our second from first answer {24,7,1986,6,99}
A2: second 99 third 24

Теперь у нас есть секунда, это наше новое значение, поэтому idx со значением 99 не может быть самым тяжелым.Такая же ситуация произошла бы, если бы второй из ответа 1 остался прежним.С другой стороны, если секунда станет третьей, мы уже знаем, что на idx 5 что-то более тяжелое, чем все раньше, и это одно.

В текущем состоянии у нас есть 3 индекса, которые наверняка не самые тяжелые :(idx 0) 24 (idx 2) 12 и (idx 5) 99.

Теперь давайте попросим некоторый набор с idx, у нас нет никакой информации, например, idx 1.

Q3: Give me second and third from set {24,12,1986,6,99}
A3: second 99, third 24

Этот ответ не зависит от того, что мы получили из ответа 2, поэтому мы знаем, что его нет в индексе 1. Остальная часть алгоритма - это тот же шаг вывода.

IE:

Мы не делаемзнать что-нибудь о idx 3.

Q4: Give me second and third from set {24,7,12,6,99}
A4: second 24 and third 12

Здесь значение Second изменилось, так как ранее было 99, что означает, что индекс 3 имеет значение, и это его.

Answer 2

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

Прежде всего, после первых 3 ваших вопросовответ уже известен как 6. Как так?Тот факт, что ответ на вопрос 2 не изменился, говорит о том, что либо 5 и 6 оба> 4> 3, либо оба <3 <4. В вопросе 3 выясняется, что 5> 3, следовательно, 6> 3. И фактто, что 5 появляется в # 2, говорит о том, что что-то> 5, и единственный возможный ответ - 6. Итак, мы закончили!

Вам просто нужно знать, какую информацию вы собираете, и применить ее полностью.

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

Наш первый раунд мы ничего не знаем, поэтому мы весим 1 2 3 4 5.Это даст ответ x y.Замените x на 6 и попробуйте снова.Вот возможные варианты:

1. Если мы получим y z с z, а не 6, тогда наш ответ будет 6 в 2 вопросах по той же причине, что и ответ был найден ранее.
2. Если мы получим y 6 или 6 y, тогда это не x, y или 6.Мы обмениваем x на все остальные три, пока не изменится ответ второго места.Тот, где это произошло, является самым тяжелым, максимум из 5 вопросов.
3. Если мы получим z y с z, а не 6, тогда 6 будет легче, чем y (иначе это будеттолкнул его вниз).Теперь мы знаем, что ответ не x, y, z или 6.Таким образом, мы просто должны обменяться x с двумя другими по очереди, применяя те же рассуждения, что и раньше, чтобы найти самое тяжелое из не более 4 вопросов.