Berlaga wrote:
Смотрите. П стоит в центре, если он не видит В - то В как минимум в 10м от центра. П уходит в туннель, проходит 20м (видит на 30)...
Так вор может в один из оставшихся двух занырнуть, а программист не увидит, а какой. А так как нужно гарантированно, то вор необычайно удачлив и может так менять туннели до бесконечности.
Не увидит сразу. Но после того, как П вернется в центр - В не успеет убежать дальше, чем на 10м. И П его увидит.
Ха! Этот ответ неверный. Можно еще лучше!
Имхо, я нашел решение для любой конечной длины туннеля. О как!
Давайте переформулируем задачу. В трёх рассматриваемых туннелях есть Плесень. И есть Дворник с ультрафиолетовой лампой, которая мгновенно убивает всю плесень в радиусе 10 в прямой видимости лампы. Плесень разрастается вдоль туннелей со скоростью 1. Дворник же ходит со скоростью 2. Какой максимальный размер туннелей можно очистить от Плесени?
В переводе на язык оригинальной постановки, Плесень - это множество мест, где может находиться вор.
Если плесень есть в торцах всех трёх туннелей, то продвижение дворника вглубь одного туннеля уничтожает плесень со скоростью 2. В то же время, в каждом их двух остальных туннелей она нарастает со скоростью не меньше 1, если они не полностью заплесневелые. То есть суммарная длина плесневых туннелей от этого не уменьшается. Это значит, что алгоритмы, не требующие полного уничтожения плесени в одном одного из туннелей без захода в него, не могут уменьшать длину плесневых туннелей. Стало быть, они неработоспособны. Итак, начинаем с полной дезинфекции третьего туннеля и возвращаемся в центр.
Чтобы не пускать плесень в третий туннель, не забегая в него, надо успевать пробежать в центр из одного туннеля так, чтобы плесень из другого в третий не проникла глубже 10. Если поочерёдно забегать в первый-второй туннели так, чтобы успевать убить плесень в третьем из центральной точки, то максимальная глубина, на которую можно забежать в каждый из туннелей - 40. Для этого достаточно почерёдно забегать в первый и второй туннели на глубину 40(1-1/2^N) (N=1,2,.. - номер "забега").
Выходит, что туннели длиной выше 50 продезинфицировать таким способом не получится совсем, а для дезинфекции 50-метрового потребуется бесконечное время. Из вышесказанного можно даже доказать, что алгоритма, позволяющего очистить больше 50, не существует.
Мой ответ: за конечное время задача решается для туннеля короче 50.
emax wrote:Так это классика - волк, крестьянин, коза и капуста. Такие задачки на логику давали 3-5 классе (во всяком случае когда я учился в школе), почти в каждом задачники по математике и логике приводились в том или ином виде. Если голова натренирована на такие задачи, то это и решается за 2-7 минуты - принципы одни и те же.
Предлагаю свести классику (волк, крестьянин, коза и капуста) к какому-нить алгоритмическому решению и с помощью этого решения решить задачу в японском тесте.
Я полагаю что это должен быть поиск пути в двудольном графе. В качестве вершин графа брать пермутации из участников + символ отсутствия.
Например
В - волк
О - овца
К - капуста
_ - отсутствие
Л - левый берег
П - правый берег
helg wrote:...то максимальная глубина, на которую можно забежать в каждый из туннелей - 40.
20, т.к. дворнику нужно идти туда и обратно. Плюс он может не доходить до конца 10, получаем 30.
В первый забег дворник действительно может зайти в первый туннель только на 20, потому что плесень в начале забега во втором была очищена только на глубину 10.
Когда дворник возвратился в центр из первого туннеля, от плесени в первом чисты не 10 метров, а уже 20 (когда дворник возвращался с 20 метров до 0, плесень успела распространиться с 30 до 20).
Поэтому, как нетрудно посчитать, во второй туннель дворник может зайти глубже, а именно на 30 метров. Можно и дальше арифметику разводить, но проще по индукции доказать, что глубина каждого N-го забега - это те самые 40(1-1/2^N), то есть надо делать забеги на глубину 20, 30, 35, 37.5... поочерёдно в первый и второй туннели.
Обозначим максимальную глубину забегания в первый-второй туннели как Х. После большого количества забегов и невозможности более глубокого продвижения, эта глубина окажется одинаковой для первого и второго туннелей из-за симметрии. Эта глубина должна быть такой, чтобы возвращаясь с неё из первого туннеля, затем забегая на неё же во второй туннель, и наконец вернувшись в центр, не допустить распространения плесени из первого туннеля в третьем.
Пробежка дворника при этом - X в первом туннеле, и 2X во втором (поскольку туда и назад). Максимально допустимое распространение плесени - X+10 (столько ей надо разрастись по первому туннелю до центра) плюс ещё 10, которые убьёт свет лампы из центра в третьем.
Чтобы плесень не убежала в третий туннель, путь дворника должен быть короче двойного пути плесени:
3X < 2(X+20)
Откуда X<40, и максимальная длина туннеля - до 50.
Заодно получаем общий ответ для случая, когда дворник в S раз быстрее плесени, а лампа светит на L. Имеем 3X < S(X+2L), то есть длина туннелей (X+L) не более
L*(3+S)/(3-S). Отрицательное значение при S>3 говорит о том, что если дворник в три или более раз быстрее плесени, он сможет очистить туннели любой конечной длины.
helg wrote:А можно без индукции, просто предел найти.
Обозначим максимальную глубину забегания в первый-второй туннели как Х. После большого количества забегов и невозможности более глубокого продвижения, эта глубина окажется одинаковой для первого и второго туннелей из-за симметрии.
...
О! Вот это отличное решение, сразу все понятно. helg - респект!
Единственно, я так и не понял, зачем тут дворник и плесень Все таки лучше придерживаться оригинальной терминологии.
Berlaga wrote:Единственно, я так и не понял, зачем тут дворник и плесень
Музыкой навеяло.
А если серьёзно, понятие "область, где может находиться преступник" мне показалось менее удобным для размышлений, чем понятная концепция расползающейся плесени.
Last edited by helg on 08 Nov 2014 04:40, edited 1 time in total.
50м – согласен. Я забыл, что программист в 2 раза быстрее.
>> если дворник в три или более раз быстрее плесени, он сможет очистить туннели любой конечной длины.
Вот здесь позвольте возразить. Давайте вернемся к первоначальной формулировке. Вор, в отличие от плесени, не может возникать из воздуха. Кроме того, по условию задачи он не обязан все время перемещаться, впрочем, как и программист. Хотя программист не знает, где находится вор (в противном случае задача имела бы тривиальное решение), однако в условии для вора этого ограничения нет. Допустим, что вор обладает способностью видеть, где находится в данный момент программист и действовать сознательно. Допустим, вор использует такую стратегию. Он занимает позицию в одном из туннелей на расстоянии от центра 10м + 1мм. Допустим, программист пошел в другой туннель. Как только он удалился от центра на 40м, вор может безопасно сменить позицию на такую же в третьем туннеле (ему надо пройти для этого 20м). Осмотрев туннель, программист возвращается в центр и выбирает из двух оставшихся туннелей, далее процесс повторяется. Допустим, программист каждый раз выбирает туннель по каким-то своим, неизвестным нам, соображениям. Тогда для вора имеет смысл менять позиции случайно, процесс таким образом будет носить вероятностный характер и сможет продолжаться сколь угодно долго, при условии что программист будет удаляться от центра не менее чем на 40 метров. Данные рассуждения верны для любой конечной разницы скоростей. Для S=3 максимальное удаление для программиста будет 60м и т.д. Максимальная длина туннеля будет 20S+10.
За время "t", которое полицейский "q" пройдет от точки своего максимального удаления "P" от центра "О" в одном тоннеле до точки маскимального удаления в другом тоннеле и вернется в точку P' во втором тоннеле, когда центр ему буден виден, вор "v", который стоит в точке Xmax, должен успеть дойти до центра и шмыгнуть в третий тоннель (или в любой другой, количество тоннелей не важно). Максимальное длина тоннеля при которой полицейский имеет шанс словить вора Xmax = P + L:
t = (P+L)/v = 2P/q + (P-L)/q,
где v, q - скорость ворa и полицейского соответственно.
решая это урвнение при условии q=2v, получаем P=3L, a Xmax = P+L = 40.
Kolbasoff wrote: [..]и вернется в точку P' во втором тоннеле, когда центр ему буден виден
Вместо возвращения в P', программисту лучше дойти до центра O, откуда видны все три туннеля. В ситуации, когда вор достигает O, а программист находится на пути к ней на расстоянии 20, вор в точке O не ловится. Но он ловится, когда программист достигает O.
Kolbasoff wrote: [..]и вернется в точку P' во втором тоннеле, когда центр ему буден виден
Вместо возвращения в P', программисту лучше дойти до центра O, откуда видны все три туннеля. В ситуации, когда вор достигает O, а программист находится на пути к ней на расстоянии 20, вор в точке O не ловится. Но он ловится, когда программист достигает O.
Вор не ловится пока еще, но полицейский его уже увидел и знает, в какой туннель вор побежал. Он зайдет в тот туннель, заблокирует его, перекусит, проверит пистолет, вызовет подмогу и не спеша поймает вора в конце тоннеля.
кстати, вы правы: вору надо успеть не только шмыгнуть в другой туннель, но и пройти по нему расстояние L, что бы возвратившийся в O полицейский его не увидел. Тогда уравнение такое:
Интересно, но я почему то решал задачу вот в такой формулировке. Вор первым приходит в комнату и из нее вбегает в один из тоннелей. Через некоторое время (формально произвольное) заходит в комнату программист и начинает своий алгоритм поиска вора в 3-х тоннелях. Задача вора, оказатся назад в комнате, чтобы потом из нее навсегда упорхнуть наружу (не в тоннелли). Соответственно задача программиста этого не допустить.
Здесь похоже обсуждается другая формулировка, когда вор и программист все время "бегают" по тоннелям, т.е. не та, что выше. На мой взгляд, задача с плесенью, введенная Хельгом, все-таки не совсем то (хотя естественно имеет место быть). Допустим, вор находитя в тоннеле #2 на расстоянии более 10 м. Программист заходит в тоннель #1 и проходит произвольное расстояние Х. Далее он возвращается назад в комнату. За это время вор мог поменять комнату # 2 на комнату # 3 (а мог и не менять). Далее, когда программер, снова в комнате после тоннеля # 1 и него выбор с вероятностью 0.5 пойти в тоннель #2 или тоннель # 3, т.к. он с вероятностью 100% знает, что вора нет в тоннеле # 1 вплоть до расстояния Х+10. Далее программист проделывает маршрут Х в тоннеле # 2. Есlи он не нашел вора (т.е. его нет вплоть до рассtояния Х+10), программист снова возвращется в комнату и у него снова выбор с вероятностью 0.5. И так далее. Ясно, что т.к. после возвращения в комнату у программиста всегда выбор с конечной вероятностью, то после какой-то попытки он выберет тот тоннель, где находится вор. Значит, за конечное время он найдет вора при длинне тоннелей X+10. Очевидно, что такой алгоритм работает при любой конечной длине X. Данная формулирока отлична от той, что предлoжена Хельгом, т.е. это две разные задачи. Формулиривка в начале - это как бы третья возможная формулировка.
Физик-Лирик wrote: [..]после какой-то попытки он выберет тот тоннель, где находится вор. Значит, за конечное время он найдет вора[..]
Правильнее вместо выделенного сказать: "за конечное время найдёт с любой заданной вероятностью меньше 1". Даже простой последовательный обход всех туннелей со случайным выбором туннеля всякий раз при попадании в центр уже находит вора за конечное время с любой вероятностью меньше 1, тут и задачи нет.
С точки зрения математики, любое конечное число подбрасываний монеты не гарантирует выпадания хотя бы одной решки, хотя здравый смысл такое принимает с трудом. Смена же вора на плесень как раз помогает тому, чтобы здравый смысл не мешал решению.
Физик-Лирик wrote: [..]после какой-то попытки он выберет тот тоннель, где находится вор. Значит, за конечное время он найдет вора[..]
Правильнее вместо выделенного сказать: "за конечное время найдёт с любой заданной вероятностью меньше 1". Даже простой последовательный обход всех туннелей со случайным выбором туннеля всякий раз при попадании в центр уже находит вора за конечное время с любой вероятностью меньше 1, тут и задачи нет.
С точки зрения математики, любое конечное число подбрасываний монеты не гарантирует выпадания хотя бы одной решки, хотя здравый смысл такое принимает с трудом. Смена же вора на плесень как раз помогает тому, чтобы здравый смысл не мешал решению.
Задача зависит от формулировки. Я совсем не против Вашей формулировки, у меня как видите своих две. Просто начальные условия самой задачи были сформулированы несколько размыто, что и допускает различные "модели".
Еще небольшой коммент.
Формально мы можем рассматривать данный процесс как цепочку Бернули, т.е. p(k) = C^n_k p^k (1-p)^(n-k), p=0.5. Тогда имеем
p(0,n) = 0.5 ^n, т.е. формално да, стремится к нулю, но не нуль. На приктике это означает, что программист все время заходит в "неправильный" тоннель, т.е. у него некий инсайд. В этом случае, максимальная длина тоннеля - 10 м, т.е. то что может увидеть из общей комнаты. Но этот инсайд как бы нарушет "произвольность" (randomness) процесса.
Завидую я вам ребяты. Умные вы все просто до офигения.
Я тридцать пять лет работаю в этой отрасли. Ни разу за все время подобные задачи в работе не встречались. Все как то тупо и просто.
Поговорить с заказчиком, понять что он хочет (самое сложное на самом деле), понять что ему на самом деле нужно (разные вещи между прочим), написать спецификацию (или какой либо документ где записано что будем делать), утвердить этот документ, написать код, задеплоить все на продакшен. И никаких воров в туннелях..
adda_ wrote:Я тридцать пять лет работаю в этой отрасли. Ни разу за все время подобные задачи в работе не встречались. Все как то тупо и просто.
Поговорить с заказчиком, понять что он хочет (самое сложное на самом деле),
Ну да, большая часть нас примерно так, не часто вникает в подобное. Но кто-то же пишет Google Search, двигуны баз данных, и ещё много чего интересного. А большей части программистов да, "вникать в требования заказчика", и использовать технологии, над которыми корпели, решали нетривиальные задачи.
Я лично, пока с работой (хорошей), так на ней много всего, и без того нарешаешься, что в алгоритмические задачи неохота вникать. Лень. Вот если что более "физическое"... Потому и работы у меня похожие...
... and even then it's rare that you'll be going there...
adda_ wrote:Завидую я вам ребяты. Умные вы все просто до офигения.
Я тридцать пять лет работаю в этой отрасли. Ни разу за все время подобные задачи в работе не встречались. Все как то тупо и просто.
Поговорить с заказчиком, понять что он хочет (самое сложное на самом деле), понять что ему на самом деле нужно (разные вещи между прочим), написать спецификацию (или какой либо документ где записано что будем делать), утвердить этот документ, написать код, задеплоить все на продакшен. И никаких воров в туннелях..
На самоме деле Вам с таким огромным опытом работы никто уже не решится давать каких-либо задачек. Думаю Вас на интервью рассматривают как "чтобы сделать, чтобы этот кандидат согласился на нас работать", а не как "ну-ка докажи, что ты достоин нашей конторы". Я на себе это уже замечаю. Если когда-то решал на интервью задачи (реальные задачи с диффурами, по физике, по тер. веру; всю доску исписывали), то сейчас как-то общим трепом все ограничевается. Я правда всегда стараюсь схитрить и где-то в начале интервью стараюсь как бы внезначай вставить что-то "умное", термин какой-либо, "формулу". Далее если народ был в этой области начинаются ностальгические воспоминания, как они были "физиками". Если народ не в теме, то все как-то упрощается и идет просто треп. А задачки - это конечно баловство для начинающих кандидатов.
Физик-Лирик wrote:На самоме деле Вам с таким огромным опытом работы никто уже не решится давать каких-либо задачек.
На самом деле решатся, ещё как. Не только в гуглах, даже в большинстве контор Bay Area. И не только.
Правда? Как интересно. Если идти в "ресэрч", тогда как бы понятно. Но если не в ресэрч, тогда не совсем ясно зачем. Если человек 35 лет в теме, то задачки как то странно выглядят.
Физик-Лирик wrote:Правда? Как интересно. Если идти в "ресэрч", тогда как бы понятно. Но если не в ресэрч, тогда не совсем ясно зачем. Если человек 35 лет в теме, то задачки как то странно выглядят.
Правда. Интервью для всех. Не так давно вдвоём на интервью в старт-ап общались с очень опытным человеком. Какая разница, 20 или 35 лет он в бизнесе? Особенно, если бизнесу больше 15-ти лет быть не может пока. Вопросы задавали, поскольку процедура. Писали в табличку, что спрашивали, и оценивали ответ. :-p
... and even then it's rare that you'll be going there...
Medium-rare wrote:Писали в табличку, что спрашивали, и оценивали ответ. :-p
Я на одном собеседовании тоже - начали отвечать по табличке, потом через пять минут забросили и пошли обсуждать реальные проблемы и как их решать. Два часа просидели, разные интересные варианты разбирали. Табличку куда-то засунули
