Форум

Юрий Мельников: Google // 12 сентября 2007, 01:14

Тестирование соискателей в компанию Google:

у одного короля была сотня советников. Все они были гномы. Советники давали плохие советы, и король принял решение их казнить.

В день казни гномики были выстроены в очередь. При этом у каждого гнома был на голове колпак черного или белого цвета.

Итак, ситуация такова: Если гном угадывает цвет колпака, который на нём надет, то он выживает, а ежели нет, то ему соответственно голову отрубают.

И еще: Каждый гном видит цвета колпаков впередистоящих гномов.

А также: гном, стоящий на плахе, видит всех остальных. Первым казнят последнего гнома в очереди.

Ах, да, вопрос: Какое максимальное количество гномов выживет?

Ну, и еще, Алексей Вадимович Белецкий полагает, что всё это излишне.

спасибо

Роман Родионов: Я не математик :) // 12 сентября 2007, 03:08

Максимальное - сто. Ну, например, если все угадают.

Дмитрий Кобак: 99 гномов // 12 сентября 2007, 12:28

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

Я решил задачу вчера по пути домой. Максимум, действительно, 99. Имеется в виду максимум в худшем случае, так что Ромино соображение ("если всем повезёт") не по делу.

Роман Родионов: Почему 99? // 12 сентября 2007, 22:54

А если все 100 угадают?

Дмитрий Кобак: Я же объясняю // 12 сентября 2007, 23:06

Вопрос задачи такой: какое наибольшее число гномов могут ГАРАНТИРОВАННО спастись.

Роман Родионов: А вот и нет! // 13 сентября 2007, 02:00

Вопрос задачи:
"Какое максимальное количество гномов выживет?"
При таком вопросе, правильный ответ - 100. Например, если каждый угадает.

Сергей Чистович: Не надо изображать из себя клоуна // 13 сентября 2007, 11:07

Конечно, задача с самого начала была сформулирована некорректно, но всё-таки понять суть проблемы можно. Мы же не в суде, а?

Роман Родионов: Тогда действительно 99. // 14 сентября 2007, 09:37

Лучше бы гномы потратили свой интеллект на советы королю.

В. В. Зельченко: И еще одна вещь, которую надо упомянуть: // 12 сентября 2007, 15:12

пока несли колпаки, у гномиков была возможность обсудить ситуацию.
Эта задача, кстати, знаменита в гимназии; по крайней мере, несколько классов знают ее в полном составе.

Артём Григорьев: Ага 99 // 12 сентября 2007, 17:31

Я её этим летом решил. Там не выжить может только первый.

Александр Симин: Сформулируйте нормально условия задачи... // 14 сентября 2007, 12:48

В отдном посте, а то непонятно, но тоже интересно...
Плиз

В. В. Зельченко: Специально для Вас // 14 сентября 2007, 19:04

Злой волшебник решил изощренно наказать 100 гномов. Он сказал им: "Я расставлю вас в затылок друг другу, сверху вниз на склоне холма, и надену на вас белые и черные колпаки (сколько каких колпаков - не скажу). Потом я буду подходить к каждому из вас по очереди, начиная с последнего, и спрашивать: "Какой на тебе колпак?" Отвечать можно только "Белый" или "Черный"; будете кашлять, шаркать или еще как-нибудь подавать знаки - сразу же съем всех. Если гном угадает, я его помилую; если назовет неправильный цвет - проглочу". Сказав это, волшебник ушел за колпаками, а гномы в это время пошептались. Задача: разработать за них такую стратегию, чтобы при экзекуции гарантированно уцелело как можно большее число гномов (как здесь уже подсказали - 99).

Сергей Чистович: А вот ещё задача // 12 сентября 2007, 20:27

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

Будем считать знаменитостью человека, которого знают все, а сам он не знает никого. Вопрос: можно ли за O(N) (то есть за N*какую-то_константу) операций выяснить, есть ли у нас в обществе знаменитость?

Александр Симин: по-моему можно... // 14 сентября 2007, 12:46

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

Сергей Чистович: Я не совсем понял, что ты предлагаешь, // 14 сентября 2007, 13:26

Но такое впечатление, что количество операций будет примерно N^3, нет? Сумму считать - это тебе не фунт изюму...

Понятно, что за 2N^2 сделать не проблема: пройтись по всей матрицен вдоль и поперек, да поискать ряд, где все единички и строку, где все нули. Но это слишком долго.

Александр Симин: Ну, // 14 сентября 2007, 15:35

я и предлагаю пройтись по всем, например, строчкам и поискать, где все нули. Потом для нулевых строк проверить соответствующие столбцы. Только сумму нужно считать для матрицы без j-й строки и j-го столбца, так как сам себя человек всегда знает... или нет?
Только ты определись с понятием "операция", так как для меня "поискать ряд, где все единички и строку, где все нули" - это непонятно. А сумма элементов любой строки/столбца - это имхо операция, нет? Кроме того, даже сама сумма не нужна, нужно сравнить больше она, равна или меньше нуля или N.

Сергей Чистович: Ты программист или что? // 14 сентября 2007, 17:22

Найти сумму N чисел - это N операций. Ладно, N-1. Проверить N чисел, являются ли они нулём - тоже N. Не очевидно?

Александр Симин: упаси Боже... // 14 сентября 2007, 17:26

неочевидно. Ладно, не буду мешать.

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

Сергей Чистович: Я думаю, пока сохраним его в тайне :) // 17 сентября 2007, 11:46

Я тоже решил, мне не нвдо.
Вроде кого-то на собеседовании в гугль спрашивали.

Дмитрий Кобак: Я тоже решил! // 17 сентября 2007, 22:13

Задача отличная. Я её наконец решил, сидя вчера в поезде Франкфурт-Фрайбург.

Сергей Чистович: нас уже трое! // 18 сентября 2007, 13:22

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