![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109чувак клянётся, что это реальная задачка с нашего интервью. итак:
большая вечеринка. party по-нашему. кто-то кого-то знает, кто-то кого-то нет. отношение "знает" не обязательно симметрично - А может знать Б, а Б - не знать А. особенно "несимметричны" знаменитости. знаменитость определяется как чувак, которого все знают, но который не знает никого. жосткое такое определение, но нужно для удобства задания задачки. то есть если чувак хоть кого-то знает, то он уже не знаменитость в нашем смысле. понятное дело, что при таком определении знаменитость на вечеринке может быть только одна, а может её и вообще не быть.
отношения участников вечеринки заданы в виде квадратной таблицы, где ячейка (i, j) содержит 1, если i знает j и 0, если не знает.
спрашивается, как за O(N), где N - количество народа на вечеринке, найти, есть ли знаменитость, и кто она.
все ответы по умолчанию будут скриниться, затем по мере возможности в реальном времени расскриниваться (за исключением ответов, содержащих правильное решение, которые останутся заскриненными несколько дней, чтобы у остальных было время подумать).
(я сам задачку услышал вчера, немного поломал голову и плюнул, а сегодня из глубин подсознания сам собой всплыл ответ)
Update: всё расскриниваю ввиду большого количества правильных ответов. чуть попозже выкину обзор типов ответов.
большая вечеринка. party по-нашему. кто-то кого-то знает, кто-то кого-то нет. отношение "знает" не обязательно симметрично - А может знать Б, а Б - не знать А. особенно "несимметричны" знаменитости. знаменитость определяется как чувак, которого все знают, но который не знает никого. жосткое такое определение, но нужно для удобства задания задачки. то есть если чувак хоть кого-то знает, то он уже не знаменитость в нашем смысле. понятное дело, что при таком определении знаменитость на вечеринке может быть только одна, а может её и вообще не быть.
отношения участников вечеринки заданы в виде квадратной таблицы, где ячейка (i, j) содержит 1, если i знает j и 0, если не знает.
спрашивается, как за O(N), где N - количество народа на вечеринке, найти, есть ли знаменитость, и кто она.
все ответы по умолчанию будут скриниться, затем по мере возможности в реальном времени расскриниваться (за исключением ответов, содержащих правильное решение, которые останутся заскриненными несколько дней, чтобы у остальных было время подумать).
(я сам задачку услышал вчера, немного поломал голову и плюнул, а сегодня из глубин подсознания сам собой всплыл ответ)
Update: всё расскриниваю ввиду большого количества правильных ответов. чуть попозже выкину обзор типов ответов.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2007-04-20 07:46 pm (UTC)0. Начинаем из левой верхней клетки. Диагональные клетки пропускаем.
1. Запоминаем позицию. Идём вправо до первой единички. Если упёрлись в стенку, то переходим на первый элемент этой же строки и продолжаем идти вправо до исходной позиции. Если упёрлись в исходную позицию, то идём на п.3.
2. Если встретили единичку, то начинаем идти вниз до первого нуля. Если упёрлись в пол, то нету знаменитостей. Если встретили ноль, то идём на п.1.
3. Бля, я никого не знаю, кто все эти люди? Идём вниз в поисках нуля. Если встретили 0, то идём на п.1, иначе если упёрлись в пол, то переходим на первый элемент столбца и продолжаем идти вниз. Если упёрлись в исходную позицию, то знаменитость найдена, если встретили 0, то знаменитостей нет.