Оптимальный алгоритм

Question

У меня есть следующая проблема. На данной горе застряла девушка, и есть два пути. Один путь приведет ее к спасателю (левый поворот), а второй (правый поворот) приведет ее в джунгли, откуда нет шансов вернуться. Теперь она встречает группу людей, которые говорят n, которые всегда говорят правду, и некоторые люди говорят, что m может/не может говорить правду. Нам дано, что n больше m. Поэтому девушка может попросить случайного человека - каким образом это спасатели, проблема в том, что она не знает, о какой из них она просит (n или m). Я хочу знать, есть ли алгоритм Big Theta (n + m), чтобы узнать, сколько людей говорит правду? или, строго говоря, значение n?

Я могу решить более простую версию этого. Скажи там только два человека, 1 всегда говорит правду, а другой всегда лжет. Она может задать вопрос, для которого оба они дадут тот же ответ. Например: говорящему по правде, она может спросить: «Эй, по словам другого парня, каким образом он берет спасителя?». Истинный оратор скажет - правый поворот (потому что другой парень лежит). Теперь она может задать тот же вопрос лжецу - он ответит, сказав - правый поворот (потому что истинный ответ оставлен, но поскольку он всегда лжет, он скажет правильно). Теперь она может уйти налево, зная, что это правильный ответ.

Проблема в том, что в первом случае второй набор людей может/не может лежать. Но я думаю, что ключ состоит в том, что n> m i.e. Число людей, которые всегда говорят правду, больше, чем число людей, которые могут/не могут говорить правду. Так выглядит, что это что-то отменит.

Любая помощь будет оценена по достоинству. Благодарю.

Answer 1

Просто спросите любой из них следующий вопрос:

Если бы вы были противоположное тому, что вы собираетесь быть, когда вы ответить на этот вопрос, который был бы правильный путь?

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

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

Тогда просто идите в другую сторону. Никакого алгоритма не требуется, просто расчет O(1).

Сделано CW, потому что это не вопрос, связанный с программированием.

Answer 2

Спросите всех, где находится направление спасателя. Так как n> m, направление, указанное больше раз, является фактическим направлением.