Комментарии 244
Задание под номер 8 интересное.
Популярный вопрос, задавали мне его на собеседовании. Решения очень простые.
если простое решение — это про наворачивание кругов вокруг полюса, то у меня вопрос.
если я нахожусь в 500м от южного полюса и начинаю идти на юг, верно ли утверждение, что через 500м я буду продолжать идти на юг? Кажется, что нет.
если я нахожусь в 500м от южного полюса и начинаю идти на юг, верно ли утверждение, что через 500м я буду продолжать идти на юг? Кажется, что нет.
Нет, оказавшись на южном полюсе вы дальше не сможете идти на юг, куда бы не пошли, все пути будут на север.
А вот идея про наворачивание кругов хорошая.
А вот идея про наворачивание кругов хорошая.
а ну я догнал. на расстоянии, скажем, (1000 + 1000/2*k*pi)м от южного полюса начать идти на юг, потом навернуть k кругов и вернуться назад. да, я не правильно запомнил то решение
Есть ещё второе, более простое решение.
Этой фразой можно убить любое решение любой задачи!
Любая точка в 500 метрах севернее экватора подойдёт.
НЛО прилетело и опубликовало эту надпись здесь
Неверно. Подойдет любая точка в 1 + 1/2pi км севернее южного полюса.
P.S. Действительно интересная задачка.
P.S. Действительно интересная задачка.
не согласен. по поверхности вы пройдёте 1 км. поэтому вам нужна половина этого расстояния по каждую сторону экватора, а это 500 метров.
Пройдя на 1 км на юг вы окажетесь в 1/2pi км от южного полюса. Если вы пройдете 1 км на запад, вы опишите окружность вернувшись в ту же точку (2 * pi * r = 2 * pi * (1/2pi) = 1). Теперь вернувшись на 1 км на север вы окажетесь в том месте, откуда начали путешествие.
Вот только мне кажется не 1/2π, а чуть больше — Земля же не плоская.
Так и есть, но на таких маленьких расстояниях погрешность ничтожно мала. Ну и главое в решении подобных задач не точные цифры, а общая идея решения :)
Кстати, вот тут вот у нас разгорелся интересный спор на тему погрешности: habrahabr.ru/post/230881/#comment_7806853
Чтоб, когда двигаешься на запад — вернулся в ту же точку.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Это про Северный полюс?
(1000 + 1000/2*k*pi)м
Не понял, как вы это получили?
Вот мое решение, идея похожа на вашу:
mathb.in/18669
пройдя 1 км на юг, путник должен остановиться на таком расстоянии от полюса, чтобы 1км пути на запад составил k полных кругов, чтобы вернуться в ту же точку при возвращении на север. Длина огружности 2*pi*r, 1000 = 2 * pi * r * k, ну да, неточность в том, что надо было написать 1000 / ( 2 * k * pi). подразумевал я это, дроби плэйн текстом — это занудно.
Не правильно выразился. Из вашего комментария было не понятно, что означает это число?
Вы получили сумму 1000 метров и некого радиуса до оси земли. В чем математический смысл этого числа?
То, что вы выше описали, и так очевидно :)
(1000 + 1000/2*k*pi)м
Вы получили сумму 1000 метров и некого радиуса до оси земли. В чем математический смысл этого числа?
То, что вы выше описали, и так очевидно :)
любая точка на окружности радиусом (1000 + 1000/2*k*pi)м с центром в южном полюсе подходит под решение.
то есть этих мест бесконечное количество применительно к вопросу задачи
то есть этих мест бесконечное количество применительно к вопросу задачи
Не понятно, что такое окружность с центром в южном полюсе?
радиус земли 6400 км, область о которой мы говорим, имеет радиус 1160 метров, в этих условиях можем считать область вокруг полюса плоской. Можно, конечно внести поправку на геоид, но это экономия на спичках, поправка на искривленность будет меньше, скажем, минимальной ширины траектории человека.
Если бы в условии задачи шла речь об отрезках, хотя бы 100км, то, да, поправка уже может стать весьма существенной
Если бы в условии задачи шла речь об отрезках, хотя бы 100км, то, да, поправка уже может стать весьма существенной
Все не так просто, как вам кажется:
Даже если для k=1 — вы промахнетесь на 0.01% в вычислении нужных точек, то вы ошибетесь на 0,036 градуса и немного не попадете в начальную точку. В принципе ничего страшного.
Но в вашей формуле ошибка в вычислениях пропорциональна k, и, ошибаясь в каждом витке на 0.01%, для k=500 вы пойдете в диаметрально противоположную сторону, потому что ошибка будет 180 градусов.
Даже если для k=1 — вы промахнетесь на 0.01% в вычислении нужных точек, то вы ошибетесь на 0,036 градуса и немного не попадете в начальную точку. В принципе ничего страшного.
Но в вашей формуле ошибка в вычислениях пропорциональна k, и, ошибаясь в каждом витке на 0.01%, для k=500 вы пойдете в диаметрально противоположную сторону, потому что ошибка будет 180 градусов.
при k=1 интересующий нас радиус составляет 159.15м. Поправка на искривленность в этом случае сильно меньше ширины траектории. Минимальная ширина траектории — это ширина ступни, то есть где-то 0.1м и то, добиться такой ширины траектории практически не возможно. При больших значениях k область еще больше сужается, что дает нам возможность без проблем говорить о плоскости.
1) Хорошо, сыграю вашим методом: С чего вы вообще взяли, что речь идет о платене Земля? С чего вы взяли, что «путешественник» — человек? Возьмем нейтронную звезду радиуса 1км и в качестве путешественника, например, электрон. Честное математическое решение будет работать до тех пор, пока piR > 1км.
2) При k=100 витки будут по 10 метров, ошибка хотя бы на 1 см в вычислении длины витка приведет к 1 метру погрешности в итоге. А это 1/10 круга или 36 градусов. В итоге путник промахнется на ~600 метров (если речь идет о Земле) от начальной точки.
2) При k=100 витки будут по 10 метров, ошибка хотя бы на 1 см в вычислении длины витка приведет к 1 метру погрешности в итоге. А это 1/10 круга или 36 градусов. В итоге путник промахнется на ~600 метров (если речь идет о Земле) от начальной точки.
1. казуистика
2. подсчитайте погрешность предположения о плоскости земли в радиусе 16 метров (k=100) от полюса. И сравните ее с 1см
2. подсчитайте погрешность предположения о плоскости земли в радиусе 16 метров (k=100) от полюса. И сравните ее с 1см
Ладно я понял вашу позицию, я думаю, вы поняли мою.
Вообще условие задачи слишком расплывчатое, чтобы что-то говорить конкретно. По крайней мере я на собеседовании больше смотрю на то, как человек пытается решать задачу и какие вопросы задает в процессе, а какой ответ от получит по большому счету вообще не важно.
Вообще условие задачи слишком расплывчатое, чтобы что-то говорить конкретно. По крайней мере я на собеседовании больше смотрю на то, как человек пытается решать задачу и какие вопросы задает в процессе, а какой ответ от получит по большому счету вообще не важно.
все, что я хотел сказать, что это задачка на сообразительность, а не на точность, поэтому достаточно приближения плоской земли вокруг плоскости. Ваш подход тоже плох, т.к. земля не шар, а геоид. Поэтому углубляться в такие точности в этой задаче в рамках собеседования — это скорее минус на собеседовании, любой оптимизации свое время.
если же вы просто хотите докопаться до погрешности моей формулы, то, конечно же, вы правы, поправка на форму поверхности нужна. Но тогда и вы не правы, используя поправку на сферу
ну и я тогда напоследок докопаюсь :)
при k=500 и погрешности 0.01% на витке, я в итоге ошибусь на 5% и в итоге собьюсь на 18 градусов )
при k=500 и погрешности 0.01% на витке, я в итоге ошибусь на 5% и в итоге собьюсь на 18 градусов )
Это да, я хотел написать про 5000 конечно же =)
Ну и оба вы не правы.)
1. Условия задачи не расплывчатые, а предельно конкретные.
2. Ответ тоже предельно конкретен: существкет бесконечное множество точее, для которых удовлетворяются условия задачи.
3. Доп.вопрос «а какие это точки» полностью удовлетворяется ответом: это сев.полюс и множество окружностей у южного, пройдя 1 км на юг от которых, оказываешься в месте, пройдя 1 км на запад, ты сделаешь один или больше полных кругов. Заметьте, вопроса и ответа о точном расстоянии этих кругов до полюса все еще нет, хотя множество этих кругов описано однозначно четко.
4. На вопрос о формуле для расстояния этих кругов от полюса абсолютно подходит плоское приближени (предполагаем что это Земля).
5. Любителям докапываться до точности замечу, что мелкие неровности поверхности, холмики, торосы, ямки и т.п. существенно увеличивают расстояние и напрочь убивают любые «точные» представления хоть как шара, хоть как геоида, хоть как гамбургера.
6. Задача явно на сообразительность, а не на расчеты.
1. Условия задачи не расплывчатые, а предельно конкретные.
2. Ответ тоже предельно конкретен: существкет бесконечное множество точее, для которых удовлетворяются условия задачи.
3. Доп.вопрос «а какие это точки» полностью удовлетворяется ответом: это сев.полюс и множество окружностей у южного, пройдя 1 км на юг от которых, оказываешься в месте, пройдя 1 км на запад, ты сделаешь один или больше полных кругов. Заметьте, вопроса и ответа о точном расстоянии этих кругов до полюса все еще нет, хотя множество этих кругов описано однозначно четко.
4. На вопрос о формуле для расстояния этих кругов от полюса абсолютно подходит плоское приближени (предполагаем что это Земля).
5. Любителям докапываться до точности замечу, что мелкие неровности поверхности, холмики, торосы, ямки и т.п. существенно увеличивают расстояние и напрочь убивают любые «точные» представления хоть как шара, хоть как геоида, хоть как гамбургера.
6. Задача явно на сообразительность, а не на расчеты.
Ох, помню эту задачу с фальшивой монетой. В начальной школе давали каждую неделю парочку подобных логических задач и очень часто были разные вариации с фальшивой монетой. Эти задачи испортили мне все детство!
Интересно, а в этой задаче, как она тут сформулирована, ответ два взвешивания подходит?
Не совсем… По идее да, это будет считаться правильным вариантом решения, хоть это им и не является:
По условию фальшивая монета может обладать абсолютно любым весом относительно остальных. И задача спрашивает
Значит, может получиться частный случай, когда фальшивая монета тяжелее двух масс обычной монеты. (3х, 4х, etc)
В этом случае можно обнаружить фальшивую монету за одно взвешивание. Если вам повезёт, и первым взвешиванием вы положите на одну чашу весов фальшивую монету, а на другую чашу весов — две обычных. Фальшивая монета перевесит, и единственный вывод из этой ситуации будет: одна монета, перевешивающая две другие — фальшивая.
Правильно было бы задать вопрос:
По условию фальшивая монета может обладать абсолютно любым весом относительно остальных. И задача спрашивает
За какое минимальное число взвешиваний на чашечных весах можно обнаружить фальшивую монету?
Значит, может получиться частный случай, когда фальшивая монета тяжелее двух масс обычной монеты. (3х, 4х, etc)
В этом случае можно обнаружить фальшивую монету за одно взвешивание. Если вам повезёт, и первым взвешиванием вы положите на одну чашу весов фальшивую монету, а на другую чашу весов — две обычных. Фальшивая монета перевесит, и единственный вывод из этой ситуации будет: одна монета, перевешивающая две другие — фальшивая.
Правильно было бы задать вопрос:
За какое наименьшее количество взвешиваний вы всегда узнаете, какая из монет фальшивая.
Да, получается можно и за одно.
Интересно, а можно ли как-то посчитать вероятность с которой можно определить фальшивую монету за одно и два взвешивания?
Интересно, а можно ли как-то посчитать вероятность с которой можно определить фальшивую монету за одно и два взвешивания?
За одно в любом случае нельзя, ведь неизвестно заранее, тяжелее она или легче. Поэтому даже если рассматривать, как говорит Shultc, случай, когда сразу попалась пара хорошая-фальшивая — нужно провести еще одно взвешивание, чтобы определить, фальшивой является более тяжелая или более легкая монета.
Вообще, мне видится, что вопрос некорректен. Если какое минимально гарантированное, то 6, если просто минимальное, то одного взвешивания может хватить.
А нет, минимально гарантированно — за 3 раза.
Минимально гарантированно — за 2 раза.
за 2 не получится. ведь из условий задачи неясно, легче подделка или тяжелее, чем остальные.
Почему не получится? Исходя из формулировки «минимальное кол-во» предполагаем что нам повезло, и мы сразу выбрали для первого взвешивание две монеты одна из которых фальшивая. Для второго взвешивания мы берем третью монету, которая заведомо настоящая, и одну из первых двух. В зависимости от результата второго взвешивания определяется какая из первых двух фальшивая.
Эт как? Делим же 6 на 6, затем 3 на 3. У нас остается кучка из трех монет, одна из которых фальшивая. Как за два-то?
тоже всегда решал эту задачу бинарным поиском
1. взвешиваем 1234 и 5678 (1)
если равны — взвешиваем 9-10 и 11-8 (2)
если равны — дефектный 12, сравниваем его с любым другим (3)
если второе взвешивание неравно — взвешиваем 9 и 10 (3)
если равно — дефектный 11, сторона по результату второго взвешивания
если не равно, то по результату второго взвешивания известна сторона, а по результату третьего известно кто из них.
— остался вариант когда первое взвешивание не равно, 1234 <> 5678
взвешиваем 125 и 369 (2)
если равно — дефектный среди 478
взвешиваем 7 и 8 (3)
если равно — дефектный 4, сторона по первому взвешиванию
если нет — сторона по первому взвешиванию, какой шар — по третьему
— если второе не равно, то два варианта — знак во взвешивании 1 и взвешивании 2 разный или одинаковый
если разный — дефектный один из перемещенных шаров: 5 или 3.
взвешиваем любой из них с любым нормальным (3) по результату понятно какой из них, по результату первого взвешивания известна сторона
если одинаковый — дефектный один из 126
тогда сравниваем 1 и 2 (3)
если равны — дефектный 6, сторона по результату первого взвешивания
если нет, то сторона по результату первого взвешивания, а кто из них понятно по третьему.
если равны — взвешиваем 9-10 и 11-8 (2)
если равны — дефектный 12, сравниваем его с любым другим (3)
если второе взвешивание неравно — взвешиваем 9 и 10 (3)
если равно — дефектный 11, сторона по результату второго взвешивания
если не равно, то по результату второго взвешивания известна сторона, а по результату третьего известно кто из них.
— остался вариант когда первое взвешивание не равно, 1234 <> 5678
взвешиваем 125 и 369 (2)
если равно — дефектный среди 478
взвешиваем 7 и 8 (3)
если равно — дефектный 4, сторона по первому взвешиванию
если нет — сторона по первому взвешиванию, какой шар — по третьему
— если второе не равно, то два варианта — знак во взвешивании 1 и взвешивании 2 разный или одинаковый
если разный — дефектный один из перемещенных шаров: 5 или 3.
взвешиваем любой из них с любым нормальным (3) по результату понятно какой из них, по результату первого взвешивания известна сторона
если одинаковый — дефектный один из 126
тогда сравниваем 1 и 2 (3)
если равны — дефектный 6, сторона по результату первого взвешивания
если нет, то сторона по результату первого взвешивания, а кто из них понятно по третьему.
Да. За 3. Думаю решение полезно знать. Решается методом теории инфонмации.
b — эксперимент, определить монету. Его энтропия H(b)=log(12). одно взвешивание дает не более log(3) информации. k — взвешиваний дают не более I<= klog(3) информации. Так как информация I позволяет определить монету, то I>=H(b). Имеем k>=log(12)/log(3). То есть k>=2.26… Так как k — целое, то требуемое равно 3.
b — эксперимент, определить монету. Его энтропия H(b)=log(12). одно взвешивание дает не более log(3) информации. k — взвешиваний дают не более I<= klog(3) информации. Так как информация I позволяет определить монету, то I>=H(b). Имеем k>=log(12)/log(3). То есть k>=2.26… Так как k — целое, то требуемое равно 3.
Каждое взвешивание дает один трит=lb(3) бит информации. Следовательно, максимум три.
Задачки с монетками, только попроще, были в книжке Шарыгина «Задачи на смекалку для 5-6 класса».
Я просто оставлю это здесь
braingames.ru
braingames.ru
«Капча» у них прекрасна!
а я тогда, вот это nazva.net
Вернулся сюда только чтобы сказать спасибо.
За ссылку спасибо
По-моему, задача 7 сводится к задаче Дидоны. По незамкнутой траектории ходить не стоит: есть риск, что лес — узенькая полосочка вокруг нашей траектории. Если же мы прошли по замкнутой траектории, а лес всё ещё не кончился — значит, траектория гарантированно не охватывает площадь S…
9 — внешняя сортировка, несложного и для всех случаев оптимального алгоритма для неё вроде бы нет…
9 — внешняя сортировка, несложного и для всех случаев оптимального алгоритма для неё вроде бы нет…
Т.е., кажется, смысл вопроса 9 такой. Знает ли человек, что такое внешняя сортировка; и если не знает — способен ли написать хоть какую-то.
для каких случаев сортировка слиянием может считаться не оптимальной? что оптимальнее?
Я не читал, всё это — моё личное ИМХО.
Отрезки, умещающиеся в память, лучше сортировать «на месте» — а значит, не до слияний.
Несколько десятков или сотен таких отрезков можно слить таким образом. Заводим двоичную «кучу» по количеству отрезков. Минимальный элемент вытаскиваем, вставляем следующий за ним.
Если отрезков тысячи или десятки тысяч, то, вероятно, лучше рекурсивно: например, сливаем отрезки по 100 шт., потом полученные сотни сливаем ещё раз, снова сотнями… 100 — это я так сказал: эта цифра должна быть меньше на механическом винчестере и больше на SSD.
Отрезки, умещающиеся в память, лучше сортировать «на месте» — а значит, не до слияний.
Несколько десятков или сотен таких отрезков можно слить таким образом. Заводим двоичную «кучу» по количеству отрезков. Минимальный элемент вытаскиваем, вставляем следующий за ним.
Если отрезков тысячи или десятки тысяч, то, вероятно, лучше рекурсивно: например, сливаем отрезки по 100 шт., потом полученные сотни сливаем ещё раз, снова сотнями… 100 — это я так сказал: эта цифра должна быть меньше на механическом винчестере и больше на SSD.
P.S. Это если сортируем обычные числа фиксированной длины — например, восемь или шестнадцать байтов. Но часто ключ сортировки не числовой (а, например, строковый), и на этом ключе висит «полезная нагрузка» — какие-нибудь данные в сотни и более байтов на запись. В такой ситуации будут работать какие-нибудь хитрые, специфичные для задачи методики экономии памяти.
Здесь про память ничего не сказано. Если под «целыми числами» понимать int (32 бит) и у нас есть полгига ОЗУ, задача решается в лоб сортировкой подсчётом за О(N). Так же как и следующие.
Внешнюю сортировку я не писал, признаюсь честно. Подсчёты на «пограничном» объёме памяти писал. Приходится налаживать хитрый механизм: заводим массив по полбайта на число. В нём хранятся цифры до 14. 1111 = 15 — признак, что цифра перевалила за 14 и точное количество хранится в особой структуре памяти. Красно-чёрное дерево не годится из-за больших накладных расходов, лучше подобие хэш-таблицы.
Вопрос «Как это эффективно сделать». Самое эффективное, как мне кажется: sort <unsorted_ints> > <sorted_ints>. Это будет эффективнее чем писать собственный алгоритм :)
Мне вот задача 5 кажется интересной. Мы же не знаем ничего о вероятности получения чая или кофе в третьем автомате.
Аналогично. После трех монеток однозначно определяем один автомат, а дальше как повезет.
Одной монеты достаточно, кидать в чай/кофе. Ключ в том что надписи заведомо неправильные. Т.е. они не ничего не говорят, а точно говорят чего там нет.
Ах ну то есть они полностью перепутали, так гораздо проще, да.
Если, бросая монетку в «чай», мы получаем чай => Это случайный автомат.
А если получаем кофе — это либо автомат с кофе, либо случайный. Одной монетой не отделаешься.
А если получаем кофе — это либо автомат с кофе, либо случайный. Одной монетой не отделаешься.
Вы не поняли. Нужно кидать одну монету в автомат, помеченный, как «случайный». Она всё и решит:
- Если вам нальётся кофе, значит это автомат с кофе. Он не может быть случайным, ибо наклейки никогда не говорят правду. Осталось два аппарата:
- Аппарат с наклейкой «Чай» будет «Случайным».
- Аппарат с наклейкой «Случайный» будет наливать чай.
- Если вам нальётся чай, значит это автомат с чаем. Он не может быть случайным, ибо наклейки никогда не говорят правд. Осталось два аппарата:
- Аппарат с наклейкой «Кофе» будет «Случайным».
- Аппарат с наклейкой «Случайный» будет наливать кофе.
Точно, не правильно понял ваше «кидать в чай\кофе».
Немного не правильно написали. Вы же всегда бросаете монету в «Случайный» автомат. Значит всегда остаются автоматы «Кофе» и «Чай».
То есть:
если в «случайном» налили чай, то:
— в автомате «чай» — кофе,
— в автомате «кофе» — случайный.
если в случайном налили кофе, то всё наоборот:
— в автомате «чай» — случайный,
— в автомате «кофе» — чай.
То есть:
если в «случайном» налили чай, то:
— в автомате «чай» — кофе,
— в автомате «кофе» — случайный.
если в случайном налили кофе, то всё наоборот:
— в автомате «чай» — случайный,
— в автомате «кофе» — чай.
.
9 — обычно это тестовое задание. Внешняя сортировка, как она попала в «логические задачи»? 10, 11 — частные случаи.
А где задача про циклический поезд в котором надо посчитать число вагонов включая и выключая свет? :)
И вообще их там дофига разных, давно почти всё разжевали и даже книжку написали. Ерунда всё это, вот есть книжки хорошие «Математическое понимание природы» и «Задачи для детей от 5 до 15 лет» Арнольда. :)
А где задача про циклический поезд в котором надо посчитать число вагонов включая и выключая свет? :)
И вообще их там дофига разных, давно почти всё разжевали и даже книжку написали. Ерунда всё это, вот есть книжки хорошие «Математическое понимание природы» и «Задачи для детей от 5 до 15 лет» Арнольда. :)
11 — не частный случай, она намного проще :)
Зачем в задачах 10 и 11 вообще что-то сортировать? Создаем битовый массив, где номер бита равен значению числа (для диапазона 1..10^9 этот массив займет менее 120 Mb в памяти; в 1 Gb массива влезут числа в диапазоне от 0 до 8589934591). Первоначально все биты равны 0. Встречаем число — инвертируем соответствующий бит. А после ищем в массиве номер единственного оставшегося единичного / нулевого бита.
В 10) про диапазон чисел ничего не сказано. Может быть и MAX_INT.
Вы написали то, что мне и, думаю, всем давно известно. Это работает для «маленьких» массивов. А теперь представьте, что данных настолько много, что у вас нет памяти, чтобы выделить её на битовый массив. Что вы будете делать? В этом суть задач с «огромными файлами» — у вас нет памяти, куда можно всё положить.
Сортировать не нужно, «частный случай» — это я имел в виду «частный случай задач на огромные файлы». Самая известная из них «внешняя сортировка» ещё у Кнута расписана. :)
Сортировать не нужно, «частный случай» — это я имел в виду «частный случай задач на огромные файлы». Самая известная из них «внешняя сортировка» ещё у Кнута расписана. :)
Проблема возникнет, если файлы и числа настолько «огромные», что памяти не хватит даже на хранение одного числа.
НЛО прилетело и опубликовало эту надпись здесь
10 решается помоему простым XOR попорядку всех чисел — на выходе ответ. с дополнительным условием ничего не меняется.
в 11 считаем попорядку сумму чисел, как только сумма становится больше 10^9 — вычитаем из нее (10^9+1) и прибавляем остальное таким образом дальше. на выходе получим ответ.
в 11 считаем попорядку сумму чисел, как только сумма становится больше 10^9 — вычитаем из нее (10^9+1) и прибавляем остальное таким образом дальше. на выходе получим ответ.
7 — идти по кругу с площадью больше S?
А не короче буквой Г?
Минуточку, но ведь в постановке значится
А что если лес имеет форму полоски, а путник неверно выбрал направление и пошел вдоль? Тогда маршрут не минимальный!
Или тут нужно делать акцент на слово «гарантировано»? (кстати почему-то с одной «н»)
гарантировано выйти из леса затратив минимальный по длине маршрут
А что если лес имеет форму полоски, а путник неверно выбрал направление и пошел вдоль? Тогда маршрут не минимальный!
Или тут нужно делать акцент на слово «гарантировано»? (кстати почему-то с одной «н»)
2 и 8 — задачи из Перельмана.
11 — из «Жемчужин программирования».
11 — из «Жемчужин программирования».
А кто-то понял условие шестой задачи? До сих пор ломаю голову над самим условием…
У кого этот сейф? Имеют ли А и В к нему доступ? Если имеют оба, значит они могут просто передать письмо друг-другу из рук в руки… А если не имеют, то в любом случае прося почтальона положить письмо в сейф, есть вероятность, что тот его прочитает… Тогда сейф вообще не важен? Или вейф у одного из них, и его можно использовать как «мешочек» для письма?
У кого этот сейф? Имеют ли А и В к нему доступ? Если имеют оба, значит они могут просто передать письмо друг-другу из рук в руки… А если не имеют, то в любом случае прося почтальона положить письмо в сейф, есть вероятность, что тот его прочитает… Тогда сейф вообще не важен? Или вейф у одного из них, и его можно использовать как «мешочек» для письма?
Можно предположить, что оба имеют доступ к сейфу, но один — по чётным дням, другой — по нечётным, так что встретиться не могут. Почтальону не доверяют (в смысле, он может вскрыть письмо), так что письмо можно передать только через сейф. Ключ можно передать через почтальона, но тогда у почтальона окажется копия, которой он сможет открыть один из замков (и если откроется сейф — прочитать письмо).
Другой вариант (более вероятный) — что сейф портативный, и его тоже можно отдать почтальону. Как и ключ.
Другой вариант (более вероятный) — что сейф портативный, и его тоже можно отдать почтальону. Как и ключ.
О том и речь. Что ж это за задача, в условии которой есть «варианты понимания»?
А правильный ответ будет вообще «Зашифруйте письмо» =)
А правильный ответ будет вообще «Зашифруйте письмо» =)
Хотя во втором варианте непонятно, зачем два замка.
A кладёт письмо в сейф, закрывает на замок, отправляет B.
B, получив сейф, отправляет записку «сейф получен».
A отправляет ключ. У почтальона сейфа уже нет, так что ключ не поможет.
A кладёт письмо в сейф, закрывает на замок, отправляет B.
B, получив сейф, отправляет записку «сейф получен».
A отправляет ключ. У почтальона сейфа уже нет, так что ключ не поможет.
Я так понял, что оба имеют доступ к сейфу. Предположим, что это непередвигаемая банковская ячейка.
У сейфа два замка — и открывается он только тогда, когда открыты оба.
Ну и написать алгоритм для обмена почтой через такой сейф можно, но использовать асимметричное шифрование разумнее.
У сейфа два замка — и открывается он только тогда, когда открыты оба.
Ну и написать алгоритм для обмена почтой через такой сейф можно, но использовать асимметричное шифрование разумнее.
Ах да. А что, если почтальон отправляет записку «сейф получен», не передав его?
Возможности верификации автора записки у нас по условию не предусмотрено.
Возможности верификации автора записки у нас по условию не предусмотрено.
Я думаю
— А цепляет замок на сейф (считаем что крепления на сейфе в форме 2-х колец, а замки амбарные без возможности автоматического закрытия) на одно из колец
— Передает его к B, B всовывает в сейф письмо, и цепляет свой замок на замок А и второе кольцо и передает обратно
— А получает сейф обратно и открывает свой замок.
А воще не совсем понятны характеристики сейфа(можно ли туд кинуть ключ, сколько замков с какой логикой)/замков(можно ли замок закрыть без ключа, он встроенный или навесной, можно ли его положить в сейф)…
— А цепляет замок на сейф (считаем что крепления на сейфе в форме 2-х колец, а замки амбарные без возможности автоматического закрытия) на одно из колец
— Передает его к B, B всовывает в сейф письмо, и цепляет свой замок на замок А и второе кольцо и передает обратно
— А получает сейф обратно и открывает свой замок.
А воще не совсем понятны характеристики сейфа(можно ли туд кинуть ключ, сколько замков с какой логикой)/замков(можно ли замок закрыть без ключа, он встроенный или навесной, можно ли его положить в сейф)…
ЗЫ: Как ниже написали не применимо если можно подменить сам сейф, вобщем надо очертить меры возможностей почтальона.
зачем так сложно?
кладем письмо, закрываем А
приходит Б закрывает
А открывает
Б открывает, достает письмо
Этож классика криптографии. :)
кладем письмо, закрываем А
приходит Б закрывает
А открывает
Б открывает, достает письмо
Этож классика криптографии. :)
кладем письмо, закрываем А
отправляем письмо Б «письмо в сейфе» почтальоном
приходит Б закрывает
отправляем письмо А «сейф закрыл» почтальоном
А открывает
отправляем письмо Б «сейф открыт» почтальоном
Б открывает, достает письмо
разве не так [ключи ни разу не попадают к почтальону => сейф можно использовать повторно]?! ведь в задаче вообще не сказанно, что сейф переносной; нет указаний и на то, что почтальон изменяет письма…
Тут просто надо передавать сейф.
А кладет письмо в сейф и заквыет на свой КлючА. И передете почтальону, чтоб тот передал сейф к Б.
Почтальон открыть сейф не может.
Б получив сейф Закрывает его на свой ключБ. И отправляет обратно.
А получив обратно окрывает свой замок ключемА, он сейф теперь закрыт на ключБ. И отправляет к Б.
Б получив открывает сейф своим ключом.
При каждой передаче через почтальона сейф был закрыт хотя бы на один замок.
А кладет письмо в сейф и заквыет на свой КлючА. И передете почтальону, чтоб тот передал сейф к Б.
Почтальон открыть сейф не может.
Б получив сейф Закрывает его на свой ключБ. И отправляет обратно.
А получив обратно окрывает свой замок ключемА, он сейф теперь закрыт на ключБ. И отправляет к Б.
Б получив открывает сейф своим ключом.
При каждой передаче через почтальона сейф был закрыт хотя бы на один замок.
Большая часть задач на собеседованиях стырена из книжки «Как сдвинуть гору Фудзи». Там же есть и общие указания, как решать задачку, если — внезапно! — попалась незнакомая.
НЛО прилетело и опубликовало эту надпись здесь
Задача 6
Сейф — это ящик с двумя замками.
1. А — кладет письмо в сейф, запирает своим ключом, отдает почтальону.
2. Почтальон доставляет ящик B.
3. B — запирает ящик своим ключом, отдает почтальону для доставки A.
4. A открывает свой замок и убеждается, что сейф остается заперт.
5. Почтальон снова доставляет ящик B
6. B — открывает сейф и получает письмо.
6.5 — Почтальон сильно устал.
Если есть прорезь, то B запирает сейф и отправляет его A. A сует письмо в прорезь и отправляет сейф B. B — отпирает.
Сейф — это ящик с двумя замками.
1. А — кладет письмо в сейф, запирает своим ключом, отдает почтальону.
2. Почтальон доставляет ящик B.
3. B — запирает ящик своим ключом, отдает почтальону для доставки A.
4. A открывает свой замок и убеждается, что сейф остается заперт.
5. Почтальон снова доставляет ящик B
6. B — открывает сейф и получает письмо.
6.5 — Почтальон сильно устал.
Если есть прорезь, то B запирает сейф и отправляет его A. A сует письмо в прорезь и отправляет сейф B. B — отпирает.
С 6 ничего не могу понять
«Есть два абонента A и B, почтальон C и открытый сейф с двумя замками. У каждого абонента есть ключ от одного из замков.»
Тогда незачем передавать ключ.
«Если передавать ключ через почтальона, то он может сделать дубликат.»
Кому передавать? Корреспондент свой ключ имеет.
«Как передать письмо от одного абонента к другому через почтальона, чтобы тот не смог его прочитать?»
Зашифровать.
Что-то с формулировкой мутно.
«Есть два абонента A и B, почтальон C и открытый сейф с двумя замками. У каждого абонента есть ключ от одного из замков.»
Тогда незачем передавать ключ.
«Если передавать ключ через почтальона, то он может сделать дубликат.»
Кому передавать? Корреспондент свой ключ имеет.
«Как передать письмо от одного абонента к другому через почтальона, чтобы тот не смог его прочитать?»
Зашифровать.
Что-то с формулировкой мутно.
Нагуглил слудующий вариант этой задачки:
Ромео и Джульетта были разлучены родителями и сидели каждый в своем замке. Они не могли встречаться, но им хотелось хотя бы писать друг другу любовные письма. Почта в те времена в Италии уже работала, но работала примитивно. Курьер относил адресату шкатулку со всем в нее вложенным. Влюбленные не могли допустить даже мысли о передаче своих писем в незапертой шкатулке, ведь содержание их так интимно! У Джульетты был навесной замок, на который она могла бы запереть почтовую шкатулку, но как ее раскроет Ромео? Ведь она не догадалась заранее снабдить его ключом. У Ромео тоже был замок, но пробемма у него была таже: как передать Джульетте ключ? Послать ключ в незапертой шкатулке до писем было бы полохой идеей. Любопытный почтальон наверняка сделал бы с него копию. Неужели положение безвыходно?
Ромео и Джульетта были разлучены родителями и сидели каждый в своем замке. Они не могли встречаться, но им хотелось хотя бы писать друг другу любовные письма. Почта в те времена в Италии уже работала, но работала примитивно. Курьер относил адресату шкатулку со всем в нее вложенным. Влюбленные не могли допустить даже мысли о передаче своих писем в незапертой шкатулке, ведь содержание их так интимно! У Джульетты был навесной замок, на который она могла бы запереть почтовую шкатулку, но как ее раскроет Ромео? Ведь она не догадалась заранее снабдить его ключом. У Ромео тоже был замок, но пробемма у него была таже: как передать Джульетте ключ? Послать ключ в незапертой шкатулке до писем было бы полохой идеей. Любопытный почтальон наверняка сделал бы с него копию. Неужели положение безвыходно?
Эта постановка задачи значительно проще и, возможно, корректнее.
Навесные замки можно соединить «цепочкой», таким образом, что открытие одного из них приведет к отпиранию шкатулки.
В случае сейфов с внутренними замками, задачу можно решить очевидным способом при наличии дубликатов своих ключей и возможности при закрывании сейфа автоматически защелкнуть любой из двух замков, даже если ключа от него нет.
Навесные замки можно соединить «цепочкой», таким образом, что открытие одного из них приведет к отпиранию шкатулки.
В случае сейфов с внутренними замками, задачу можно решить очевидным способом при наличии дубликатов своих ключей и возможности при закрывании сейфа автоматически защелкнуть любой из двух замков, даже если ключа от него нет.
А если просто передать сначала замок?
Замок нужно передавать по надежному каналу связи. Иначе почтальон может сделать свой ключ или подменить замок.
Если подменить замок — то переписки не выйдет. Потому что получатель не сможет открыть. И может замок такой сложный, что сделать ключ невозможно.
А отправляет замок З. Почтальон передает B свой замок Z. B отправляет письмо, закрыв сейф замком Z. Почтальон снимает замок Z, читает письмо, вешает замок З.
В сейфах редко бывают навесные замки. Чаще встроенные.
Навесные — это для похожей задачи:
habrahabr.ru/post/230881/#comment_7805223
habrahabr.ru/post/230881/#comment_7805223
Но идея та же — он подменяет сейф в таком случае.
В оригинальной задаче все правильно — у А и В есть ключи, которые были переданы по надежному каналу, и сейф. Если есть возможность убедиться в целостности замка (пломбы те же), то можно гарантировать надежную переписку.
В задаче про Ромео и Джульетту ничего про надежный канал связи не сказано, так что она нерешаема.
В задаче про Ромео и Джульетту ничего про надежный канал связи не сказано, так что она нерешаема.
Не проходит.
Всё упирается в две вещи:
1) если почтальон подменяет сейф, то в нём оба замка другие, и тот, кто получил этот сейф, сразу обнаружит подмену.
2) Когда A открывает свой замок, он проверяет, не открылся ли сейф. Если сейф неправильный (что невозможно по п.1), то ущерба не возникло — письма в нём нет. Если правильный, но не открылся — то второй замок мог закрыть только B, но не почтальон. Ущерба опять нет.
Единственный вопрос — как мог возникнуть сейф с такими свойствами. Откуда A и B знают, что у них ключи от одного и того же сейфа (и почему они не могли сами сделать две копии ключей хотя бы от одного замка).
Всё упирается в две вещи:
1) если почтальон подменяет сейф, то в нём оба замка другие, и тот, кто получил этот сейф, сразу обнаружит подмену.
2) Когда A открывает свой замок, он проверяет, не открылся ли сейф. Если сейф неправильный (что невозможно по п.1), то ущерба не возникло — письма в нём нет. Если правильный, но не открылся — то второй замок мог закрыть только B, но не почтальон. Ущерба опять нет.
Единственный вопрос — как мог возникнуть сейф с такими свойствами. Откуда A и B знают, что у них ключи от одного и того же сейфа (и почему они не могли сами сделать две копии ключей хотя бы от одного замка).
НЛО прилетело и опубликовало эту надпись здесь
В случае со шкатулкой (и навесными замками) почтальон может притвориться, что он B — ведь исходно замка ZB на шкатулке нет. А B шкатулки так и не увидит. Или, открыв шкатулку и прочитав письмо, почтальон перевесит свой замок на место ZA, и будет общаться с B от имени A. Тогда вообще никто ничего не заподозрит, пока к влюблённым не нагрянет полиция нравов.
В смысле?
А замок можно защелкнуть (закрыть) без ключа?
Задача номер 3 меня задела.
Ну зачем они сказали про потолок? Почему он низкий? Я его трогать, что ли должен? Как это мне поможет узнать, какая лампочка включилась?
Ну зачем они сказали про потолок? Почему он низкий? Я его трогать, что ли должен? Как это мне поможет узнать, какая лампочка включилась?
Там расчет на то, что лампочка будет нагреваться и ее можно потрогать, скорее всего. Что, конечно, совсем не является обязательным (что она будет нагреваться).
Если по ней будет идти ток, то она будет нагреваться. Если по ней не будет идти ток, то вы неправильно решали задачу =)
Ток может идти очень маленький, и нагрев будет неощутим.
Вот впаять в выключатель реле с таймером — это хороший ответ =)
Вот впаять в выключатель реле с таймером — это хороший ответ =)
Думаю, все-таки, задачу предполагалось решить, включив два переключателя на время, достаточное для нагрева лампочки. По истечении времени выключаем олин переключатель и топаем во вторую комнату. Будут лампочки: включенная, теплая и холодная.
Данное решение разбивается в пух и прах хорошими контр-аргументами.
И очень желательно прочитать вот это: blogs.msdn.com/b/ruericlippert/archive/2011/02/28/what-would-feynman-do.aspx
И очень желательно прочитать вот это: blogs.msdn.com/b/ruericlippert/archive/2011/02/28/what-would-feynman-do.aspx
Уже читал ранее. Сомневаюсь, что на собеседовании ожидались именно такие ответы)
Вспомнилась байка про Бора и барометр
Сэр Эрнеcт Резерфорд, президент Королевской академии и лауреат Нобелевской премии по физике рассказывал такую историю:
Однажды к нему обратился коллега за помощью. Он собирался поставить самую низкую оценку по физике одному из своих студентов, в то время как тот утверждал, что заслуживает высшего балла. Оба — преподаватель и студент — согласились положиться на суждение третьего лица, незаинтересованного арбитра. Выбор пал на Резерфорда. Экзаменационный вопрос гласил: «Объясните, каким образом можно измерить высоту здания с помощью барометра?».
Ответ студента был таким: «Нужно подняться с барометром на крышу здания, спустить барометр вниз на длинной верёвке, а затем втянуть его обратно и измерить длину верёвки, которая и покажет точную высоту здания».
Случай был и впрямь сложный, так как ответ был абсолютно полным и верным! С другой стороны, экзамен был по физике, а ответ имел мало общего с применением знаний в этой области.
Резерфорд предложил студенту попытаться ответить ещё раз. Дав ему шесть минут на подготовку, он предупредил его, что ответ должен демонстрировать знание физических законов. По истечении пяти минут студент так и не написал ничего в экзаменационном листе. Резерфорд спросил его, сдаётся ли он, но тот заявил, что у него есть несколько решений проблемы, и он просто выбирает лучшее.
Заинтересовавшись, Резерфорд попросил молодого человека приступить к ответу, не дожидаясь истечения отведённого срока. Новый ответ на вопрос гласил: «Поднимитесь с барометром на крышу и бросьте его вниз, замеряя время падения. Затем, используя формулу, вычислите высоту здания».
Тут Резерфорд спросил своего коллегу преподавателя, доволен ли он этим ответом. Тот, наконец, сдался, признав ответ удовлетворительным. Однако студент упоминал, что знает несколько ответов, и его попросили открыть их.
— Есть несколько способов измерить высоту здания с помощью барометра, — начал студент. — Например, можно выйти на улицу в солнечный день и измерить высоту барометра и его тени, а также измерить длину тени здания. Затем, решив несложную пропорцию, определить высоту самого здания.
— Неплохо, — сказал Резерфорд. — Есть и другие способы?
— Да. Есть очень простой способ, который, уверен, вам понравится. Вы берёте барометр в руки и поднимаетесь по лестнице, прикладывая барометр к стене и делая отметки. Сосчитав количество этих отметок и умножив его на размер барометра, вы получите высоту здания. Вполне очевидный метод.
— Если вы хотите более сложный способ, — продолжал он, — то привяжите к барометру шнурок и, раскачивая его, как маятник, определите величину гравитации у основания здания и на его крыше. Из разницы между этими величинами, в принципе, можно вычислить высоту здания. В этом же случае, привязав к барометру шнурок, вы можете подняться с вашим маятником на крышу и, раскачивая его, вычислить высоту здания по периоду прецессии.
— Наконец, — заключил он, — среди множества прочих способов решения данной проблемы лучшим, пожалуй, является такой: возьмите барометр с собой, найдите управляющего и скажите ему: «Господин управляющий, у меня есть замечательный барометр. Он ваш, если вы скажете мне высоту этого здания».
Тут Резерфорд спросил студента, неужели он действительно не знал общепринятого решения этой задачи. Он признался, что знал, но сказал при этом, что сыт по горло школой и колледжем, где учителя навязывают ученикам свой способ мышления.
Студент этот был Нильс Бор (1885–1962), датский физик, лауреат Нобелевской премии 1922 г.
Однажды к нему обратился коллега за помощью. Он собирался поставить самую низкую оценку по физике одному из своих студентов, в то время как тот утверждал, что заслуживает высшего балла. Оба — преподаватель и студент — согласились положиться на суждение третьего лица, незаинтересованного арбитра. Выбор пал на Резерфорда. Экзаменационный вопрос гласил: «Объясните, каким образом можно измерить высоту здания с помощью барометра?».
Ответ студента был таким: «Нужно подняться с барометром на крышу здания, спустить барометр вниз на длинной верёвке, а затем втянуть его обратно и измерить длину верёвки, которая и покажет точную высоту здания».
Случай был и впрямь сложный, так как ответ был абсолютно полным и верным! С другой стороны, экзамен был по физике, а ответ имел мало общего с применением знаний в этой области.
Резерфорд предложил студенту попытаться ответить ещё раз. Дав ему шесть минут на подготовку, он предупредил его, что ответ должен демонстрировать знание физических законов. По истечении пяти минут студент так и не написал ничего в экзаменационном листе. Резерфорд спросил его, сдаётся ли он, но тот заявил, что у него есть несколько решений проблемы, и он просто выбирает лучшее.
Заинтересовавшись, Резерфорд попросил молодого человека приступить к ответу, не дожидаясь истечения отведённого срока. Новый ответ на вопрос гласил: «Поднимитесь с барометром на крышу и бросьте его вниз, замеряя время падения. Затем, используя формулу, вычислите высоту здания».
Тут Резерфорд спросил своего коллегу преподавателя, доволен ли он этим ответом. Тот, наконец, сдался, признав ответ удовлетворительным. Однако студент упоминал, что знает несколько ответов, и его попросили открыть их.
— Есть несколько способов измерить высоту здания с помощью барометра, — начал студент. — Например, можно выйти на улицу в солнечный день и измерить высоту барометра и его тени, а также измерить длину тени здания. Затем, решив несложную пропорцию, определить высоту самого здания.
— Неплохо, — сказал Резерфорд. — Есть и другие способы?
— Да. Есть очень простой способ, который, уверен, вам понравится. Вы берёте барометр в руки и поднимаетесь по лестнице, прикладывая барометр к стене и делая отметки. Сосчитав количество этих отметок и умножив его на размер барометра, вы получите высоту здания. Вполне очевидный метод.
— Если вы хотите более сложный способ, — продолжал он, — то привяжите к барометру шнурок и, раскачивая его, как маятник, определите величину гравитации у основания здания и на его крыше. Из разницы между этими величинами, в принципе, можно вычислить высоту здания. В этом же случае, привязав к барометру шнурок, вы можете подняться с вашим маятником на крышу и, раскачивая его, вычислить высоту здания по периоду прецессии.
— Наконец, — заключил он, — среди множества прочих способов решения данной проблемы лучшим, пожалуй, является такой: возьмите барометр с собой, найдите управляющего и скажите ему: «Господин управляющий, у меня есть замечательный барометр. Он ваш, если вы скажете мне высоту этого здания».
Тут Резерфорд спросил студента, неужели он действительно не знал общепринятого решения этой задачи. Он признался, что знал, но сказал при этом, что сыт по горло школой и колледжем, где учителя навязывают ученикам свой способ мышления.
Студент этот был Нильс Бор (1885–1962), датский физик, лауреат Нобелевской премии 1922 г.
Ну, не только же лампы накаливания в природе существуют. Там ниже Ogra привел отличную ссылку, кстати =)
про потолок сказано, ибо намекнуть, что вы можете дотянуться до лампочек.
Такие задачи в школьные годы решали
А решение простое
1) Включаем первый рубильник на некоторое время.
2) Выключаем первый рубильник и включаем второй.
3) Заходим в комнату. Горящая лампочка — второй рубильник, тёплая лампочка — первый рубильник, холодная лампочка — третий рубильник
2) Выключаем первый рубильник и включаем второй.
3) Заходим в комнату. Горящая лампочка — второй рубильник, тёплая лампочка — первый рубильник, холодная лампочка — третий рубильник
Такие задачи в школьные годы решали
Мои ответы на некоторые
1) Белый, так как северный полюс.
2) Фальшивая монета по определению обладает сопоставимым весом, то есть он отличается незначительно.
Взвешиваем две кучки по 6 — одна будет тяжелее, а другая легче.
Каждую кучку разбиваем ещё на две кучки по 3 монеты и их взвешиваем.
Если вес равный — в этой кучке нет фальшивой, если отличается — она в этой кучке.
На этом этапе мы определили легче или тяжелее ли фальшивая монета от оригинальной.
Берём кучку из трёх монет, которая была тяжелее или легче на последнем взвешивании в соответсвии с определённым весом фальшивой монеты.
Взвешиваем две случайные монеты из этих трёх — если вес равен, то фальшивая осталась на столе, если отличается — фальшивая соответсвующей чаше весов.
Итого минимум — 3, но может быть 4, как повезёт.
3) Один выключатель не трогать, другой включить, третий включить, подождать и выключить. Зайти в комнату и посмотреть какая горит, какая не горит и какая тёплая.
4) Поджчечь первую верёвку с двух сторон, а вторую с одной. Когда первая догорит, пройдёт 30 минут, в этот момент поджечь второй конец второй верёвки. Когда она догорит пройдёт ещё 15 минут.
5) Одну монету бросить в автомат с наклейкой «случайный».
6) Не понял условие.
7) Двигаться по периметру фигуры, площадь которой больше площади леса. Эффективнее всего будет окружность.
8) Первое это северный полюс, а второе вроде как рядом с южным полюсом, но когда оказываешься точно на полюсе, невозможно идти на запад или восток, и если обратно идти на север, можно оказаться на любой точке на данной параллеле, так что тут непонятно.
9) Merge sort?
10) Применить XOR последовательно для каждого числа. В конце останется только то, что встречается нечётное число раз.
11) Выделить 10^9 байт оперативной памяти (почти гигабайт), заполнить нулями. Идти по файлу и записывать единицы в ячейки памяти с номером текущего числа. Если единина уже есть, то это искомое число. Потребление памяти можно уменьшить в 8 раз, если использовать не целые байты, а биты в них. То есть первые восемь чисел будут занимать не 8 байт, а лишь 1.
12)
2) Фальшивая монета по определению обладает сопоставимым весом, то есть он отличается незначительно.
Взвешиваем две кучки по 6 — одна будет тяжелее, а другая легче.
Каждую кучку разбиваем ещё на две кучки по 3 монеты и их взвешиваем.
Если вес равный — в этой кучке нет фальшивой, если отличается — она в этой кучке.
На этом этапе мы определили легче или тяжелее ли фальшивая монета от оригинальной.
Берём кучку из трёх монет, которая была тяжелее или легче на последнем взвешивании в соответсвии с определённым весом фальшивой монеты.
Взвешиваем две случайные монеты из этих трёх — если вес равен, то фальшивая осталась на столе, если отличается — фальшивая соответсвующей чаше весов.
Итого минимум — 3, но может быть 4, как повезёт.
3) Один выключатель не трогать, другой включить, третий включить, подождать и выключить. Зайти в комнату и посмотреть какая горит, какая не горит и какая тёплая.
4) Поджчечь первую верёвку с двух сторон, а вторую с одной. Когда первая догорит, пройдёт 30 минут, в этот момент поджечь второй конец второй верёвки. Когда она догорит пройдёт ещё 15 минут.
5) Одну монету бросить в автомат с наклейкой «случайный».
6) Не понял условие.
7) Двигаться по периметру фигуры, площадь которой больше площади леса. Эффективнее всего будет окружность.
8) Первое это северный полюс, а второе вроде как рядом с южным полюсом, но когда оказываешься точно на полюсе, невозможно идти на запад или восток, и если обратно идти на север, можно оказаться на любой точке на данной параллеле, так что тут непонятно.
9) Merge sort?
10) Применить XOR последовательно для каждого числа. В конце останется только то, что встречается нечётное число раз.
11) Выделить 10^9 байт оперативной памяти (почти гигабайт), заполнить нулями. Идти по файлу и записывать единицы в ячейки памяти с номером текущего числа. Если единина уже есть, то это искомое число. Потребление памяти можно уменьшить в 8 раз, если использовать не целые байты, а биты в них. То есть первые восемь чисел будут занимать не 8 байт, а лишь 1.
12)
10 * 10 * 10 * 10 * 10 * 10, 2 * 50 * 10 * 10 * 10 * 10, 2 * 50 * 2 * 50 * 10 * 10, 2 * 50 * 2 * 50 * 2 * 50
на счет задачи №2, я думаю, что после первого взвешивания оставшиеся 6 монет нужно разделить на 3 кучки по 2 монеты, и дальше фальшивка определяется в 2 действиями. итого для определения фальшивки необходимо 3 шага.
а если взевисить в первый раз 6 монет, то 2
как у вас получилось 2 действия?
1)взвешиваем по 6 монет
далее оставшиеся 6 монет разбиваем на 3 кучки по 2 монеты
2)взвешиваем произвольную пару по 2 монеты (определяется та пара в которой фальшивка)
3)взвешиваем по 1 монете из этой пары -> фальшивка найдена
1)взвешиваем по 6 монет
далее оставшиеся 6 монет разбиваем на 3 кучки по 2 монеты
2)взвешиваем произвольную пару по 2 монеты (определяется та пара в которой фальшивка)
3)взвешиваем по 1 монете из этой пары -> фальшивка найдена
Как вы определяете какая из двух кучек по 6 монет «оставшаяся»? Вы изначально не знаете легче или тяжелее фальшивка.
да, мое решение неверное
а зачем вы вообще взвешиваете по 6 монет? если разбить на 4 кучки по 3 монеты, а дальше как у вас написано?
Разбиваем на 4 кучки по 3 монеты.
Допустим:
1. Взвешиваем первые две кучки — они равны, фальшивки нет.
2. Взвешиваем вторую и третью кучку — они равны, фальшивки нет. Фальшивка в четвёртой кучке.
3. Взвешиваем две монеты из последней кучки — они не равны, какая-то из низ фальшивка.
4. Взвешиваем оставшуюся монету с какой-либо из предыдущих двух и определяем фальшивку.
Всё равно максимум 4 получилось Как-то не так?
Если говорить об абсолютном минимуме с участием удачи, то нужно всего два взвешивания. Первый определяем эталон, вторым сравниваем фальшивку с эталоном.
Допустим:
1. Взвешиваем первые две кучки — они равны, фальшивки нет.
2. Взвешиваем вторую и третью кучку — они равны, фальшивки нет. Фальшивка в четвёртой кучке.
3. Взвешиваем две монеты из последней кучки — они не равны, какая-то из низ фальшивка.
4. Взвешиваем оставшуюся монету с какой-либо из предыдущих двух и определяем фальшивку.
Всё равно максимум 4 получилось Как-то не так?
Если говорить об абсолютном минимуме с участием удачи, то нужно всего два взвешивания. Первый определяем эталон, вторым сравниваем фальшивку с эталоном.
нет, я говорю о решении, при котором при любом стечении обстоятельств результат должен быть найден.
а если так:
-разбиваем на 3 кучки по 4 монеты
-затем наибольшее 2 взвешиваниями определяем кучку с фальшивкой
-кучку с фальшивкой из 4 монет разбиваем на 2 кучки по 2 монеты, и делаем дополнительную кучку из 2 монет, в которых точно нет фальшивки(какие настоящие мы уже знаем)
-одним взвешиванием определяем, в какой кучке фальшивка
-кучку с фальшивкой из 2 монет разбиваем на 2 кучки по 1 монете, и снова одним взвешиванием определяем фальшивку, используя монету, которая точно не фальшивка
гарантированное решение для которого необходимо 4 взвешивания
а если так:
-разбиваем на 3 кучки по 4 монеты
-затем наибольшее 2 взвешиваниями определяем кучку с фальшивкой
-кучку с фальшивкой из 4 монет разбиваем на 2 кучки по 2 монеты, и делаем дополнительную кучку из 2 монет, в которых точно нет фальшивки(какие настоящие мы уже знаем)
-одним взвешиванием определяем, в какой кучке фальшивка
-кучку с фальшивкой из 2 монет разбиваем на 2 кучки по 1 монете, и снова одним взвешиванием определяем фальшивку, используя монету, которая точно не фальшивка
гарантированное решение для которого необходимо 4 взвешивания
Все выше приведённые методы гарантированно находят фальшивку за 4 взвешивания, разницы нет.
Но можно управиться и за 3.
habrahabr.ru/post/230881/#comment_7805291
habrahabr.ru/post/230881/#comment_7805291
пардон. там не 9 монет, а 12. за 2 ни как
Задача №2.
У нас после первого взвешивания нет «оставшихся 6 монет», т.к. мы не знаем, тяжелее фальшивка или легче.
Гарантированный способ определения за 3 взвешивания.
А вообще, я эту задачку видел в другой форме — «как за 3 взвешивания найти фальшивку среди 12 шаров».
У нас после первого взвешивания нет «оставшихся 6 монет», т.к. мы не знаем, тяжелее фальшивка или легче.
Гарантированный способ определения за 3 взвешивания.
А вообще, я эту задачку видел в другой форме — «как за 3 взвешивания найти фальшивку среди 12 шаров».
12) а где 10 = 2 * 5?
11-ую можно решить через пару long-ов без массивов.
Зато O(M<=N)
С матожиданием в виде N/2.
Правда, мне почему-то кажется, что предварительное обнуление и запись в память будут заметно дороже, чем вариант тратящий пару long-ов.
Правда, мне почему-то кажется, что предварительное обнуление и запись в память будут заметно дороже, чем вариант тратящий пару long-ов.
Я не очень понимаю, что здесь написано. Могу свое уточнить. Задачу можно решить в один проход, практически не используя память.
Используя много памяти, задача будет решаться МЕНЬШЕ, чем за один проход. В худшем случае — ровно за один проход. В лучшем — за два обращения к памяти.
с интересом бы посмотрел на решение меньше чем за один проход :)
При жадном до памяти алгоритме один полный проход получается, только если дублирующееся число стоит последним. Во всех остальных случаях, нам не нужно заканчивать проход по массиву, и как результат — получается даже меньше одного прохода. При работе с файлом на 4 Гб(миллиард целых по 4 байта), возможность получить результат прочитав только 2Гб (например, мат.ожидание надо еще посчитать), откровенно говоря, радует.
Решение задачки №2
Мне удалось придумать алгоритм на три взвешивания. Не знаю только, как доказать, что это минимальное количество необходимых взвешиваний. Вот сам алгоритм.
Взвешиваем (в первый раз) две кучки по четыре:
А) если равны, то у на есть 8 эталонных монет. Взвешиваем (во второй раз) из оставшихся четырех монет две, сравнивая с эталонными.
а) если равны, то взвешиваем (в третий раз) из оставшихся двух монет одну, сравнивая с эталонной.
б) если не равны, то мы узнает, тяжелее, или легче, фальшивая монетка, и на остается взвесить (в третий раз) две монетки между собой.
Б) если не равны, то у нас есть четыре эталонные моентки и две неопределенных кучки: одна с потенциально тяжелой (обозначим +) и другая с потенциально легкой (обозначим -) фальшивой монеткой, — мы ведь незнаем тяжелее фальшивка или легче. Затем мы берем по две монетки из двух неопределенных кучек (запоминая их) и кладем на одну чашу. Затем берем по одной монетки опять из двух неопределенных кучек (запоминая их) и кладем на другую чашу, добавив две эталонные. Взвешиваем (во второй раз). Вот иллюстрация для наглядности:
а) если равны, то взвешиваем (в третий раз), сравнивая из двух оставшихся монеток одну с эталнной.
б) если не равны
б.1) и правая тяжелее левой, то либо потенциально легкая (-) монетка из левой кучки фальшивка, либо одна из потенциально тяжелых (+) монеток из правой кучки фальшивка. Кладем на одну чашу весов потенциально легкую и одну из потенциально тяжелый, а на другую две эталонные и взвешиваем (в третий раз):
a.1.1) если равны, то фальшивка — оставшаяся потенциально тяжелая
a.1.2) если правая тяжелее, то фальшивка — потенциально тяжелая с правой чаши весов
a.1.3) если правая легче, то фальшивка — потенциально легкая с левой чаши весов
б.2) и правая легче левой, то действуем аналогично пункту (б.1)
Взвешиваем (в первый раз) две кучки по четыре:
А) если равны, то у на есть 8 эталонных монет. Взвешиваем (во второй раз) из оставшихся четырех монет две, сравнивая с эталонными.
а) если равны, то взвешиваем (в третий раз) из оставшихся двух монет одну, сравнивая с эталонной.
б) если не равны, то мы узнает, тяжелее, или легче, фальшивая монетка, и на остается взвесить (в третий раз) две монетки между собой.
Б) если не равны, то у нас есть четыре эталонные моентки и две неопределенных кучки: одна с потенциально тяжелой (обозначим +) и другая с потенциально легкой (обозначим -) фальшивой монеткой, — мы ведь незнаем тяжелее фальшивка или легче. Затем мы берем по две монетки из двух неопределенных кучек (запоминая их) и кладем на одну чашу. Затем берем по одной монетки опять из двух неопределенных кучек (запоминая их) и кладем на другую чашу, добавив две эталонные. Взвешиваем (во второй раз). Вот иллюстрация для наглядности:
- + - - + + о о о о о о о оа) если равны, то взвешиваем (в третий раз), сравнивая из двух оставшихся монеток одну с эталнной.
б) если не равны
б.1) и правая тяжелее левой, то либо потенциально легкая (-) монетка из левой кучки фальшивка, либо одна из потенциально тяжелых (+) монеток из правой кучки фальшивка. Кладем на одну чашу весов потенциально легкую и одну из потенциально тяжелый, а на другую две эталонные и взвешиваем (в третий раз):
- + о о о оa.1.1) если равны, то фальшивка — оставшаяся потенциально тяжелая
a.1.2) если правая тяжелее, то фальшивка — потенциально тяжелая с правой чаши весов
a.1.3) если правая легче, то фальшивка — потенциально легкая с левой чаши весов
б.2) и правая легче левой, то действуем аналогично пункту (б.1)
она в два взвешивания решается =) подумайте как, если не получится, то в личку напишите.
12 монет, не решается она в два звешивания в 100% случаев. Только в некоторых частных. Когда-то она была разжёвана на брейнгеймс, чего там только небыло, но все решения в два взвешивания, как и большинство с 3 взвешиваниями где-то давали сбой.
Есть ровно один алгоритм решения в три взвешивания. В два нет.
Есть ровно один алгоритм решения в три взвешивания. В два нет.
9) Merge sort?Хоть это и не логическая задача, а задача на знание алгоритмов сортировки, сделать которую — дело техники, но на самом деле реализация получается не такая и простая. Для примера вот код filesort из MySQL. Я писал подобное когда-то на Python с мультипроцессингом сортировки и слияния кусков для скорости. Приятного мало :)
Мои решения:
1. северный полюс
2. постановка так себе. Минимальное число — 2, минимальное гарантированное — 3. А про то чтобы рассказать как именно это сделать за 3 взвешивания там вообще не спрашивают. Как в том анекдоте «А это уже второй вопрос»
3. задача с нагревом, сомнительная логичность.
4. классика, поджечь одну с одной стороны, вторую с двух, когда вторая прогорит — поджечь первую со второй стороны.
5. решил неправильно, упустил из виду что наклейка всегда врёт, коменты помогли
6. плохая формулировка. Если почтальён носит сейф то моё решение совпало с madixi
7. не решил, коменты сделали меня чуть умнее. Я думал идти по расширяющейся спирали либо по прямой в любом случайном направлении. Впрочем решение с окружностью площадью больше S по постановке тоже не подходит — это не гарантирует именно минимальный маршрут, ведь выход может быть в трех метрах от нас, только не в той стороне куда мы пошли. И тогда расширяющаяся спираль окажется эффективнее.
8. Так и не понял какой второй вариант. Разве что действительно кругами вокруг полюса ходить.
9. Не придумал эффективного способа, кроме просто сортировки. Как ни крути в моём понимании — работы немеряно, придётся весь файл перелопатить.
10. XOR всех чисел
11. просуммировать все числа, отнять от полученного (10^9)!
12. Даже не пытался. Не люблю такого рода задачи.
1. северный полюс
2. постановка так себе. Минимальное число — 2, минимальное гарантированное — 3. А про то чтобы рассказать как именно это сделать за 3 взвешивания там вообще не спрашивают. Как в том анекдоте «А это уже второй вопрос»
3. задача с нагревом, сомнительная логичность.
4. классика, поджечь одну с одной стороны, вторую с двух, когда вторая прогорит — поджечь первую со второй стороны.
5. решил неправильно, упустил из виду что наклейка всегда врёт, коменты помогли
6. плохая формулировка. Если почтальён носит сейф то моё решение совпало с madixi
7. не решил, коменты сделали меня чуть умнее. Я думал идти по расширяющейся спирали либо по прямой в любом случайном направлении. Впрочем решение с окружностью площадью больше S по постановке тоже не подходит — это не гарантирует именно минимальный маршрут, ведь выход может быть в трех метрах от нас, только не в той стороне куда мы пошли. И тогда расширяющаяся спираль окажется эффективнее.
8. Так и не понял какой второй вариант. Разве что действительно кругами вокруг полюса ходить.
9. Не придумал эффективного способа, кроме просто сортировки. Как ни крути в моём понимании — работы немеряно, придётся весь файл перелопатить.
10. XOR всех чисел
11. просуммировать все числа, отнять от полученного (10^9)!
12. Даже не пытался. Не люблю такого рода задачи.
Поясните, пожалуйста, вашу мысль про 11. От суммы всех чисел в последовательности вы отнимаете 10^9 факториал? Но как?
Сумма всех чисел в последовательности от 1 до 10^9, где одно из чисел повторяется два раза, очевидно, не может превышать значения 500000001500000000. (10^9)! — это невероятно огромное число (произведение всех чисел в последовательности от 1 до 10^9).
Сумма всех чисел в последовательности от 1 до 10^9, где одно из чисел повторяется два раза, очевидно, не может превышать значения 500000001500000000. (10^9)! — это невероятно огромное число (произведение всех чисел в последовательности от 1 до 10^9).
Задачи интересные и довольно известные, но если бы я отбирал сотрудников такими задачами, уверен, лишился бы самых лучших из них )
Такие задачи иногда подбрасываю разработчикам для расширения сознания с тегом «а слабо не гугля»?
Такие задачи иногда подбрасываю разработчикам для расширения сознания с тегом «а слабо не гугля»?
1. Человек построил дом в расщелине горы. Медведь — чёрный с белой грудью.
2. Двенадцатичашечные весы сделают это за один приём. Как сделать двенадцатичашечные весы в домашних условиях: взять обычные настенные часы, выдрать из них циферблат; подвесить к часовым штрихам двенадцать крышечек от пепсикоки, а сам циферблат подвесить за центр или поставить на точечную опору.
3. Зайти в комнату и устроить короткое замыкание в одной лампочке. Дальше тривиально.
4. Встречная задача: какие интервалы вы можете отмерить этими верёвками?
8. Континуум. А именно:
— северный полюс
— счётное количество окружностей вокруг южного полюса — 1км + 1/2Пk, k=1..+oo
— окружность неопределённости — ровно 1км от южного полюса
— круг некорректности — внутри этой окружности
9. Дофига способов сортировки, — например, подсчётом. Поскольку у сортировок асимптотика O(nlogn), то тормознутая сортировка будет отличаться от линейной (подсчётом) в жалкие 32 раза. Да мы на фоне дисковых операций можем это не заметить. Видимо, задача возникла в эпоху, когда числа были маленькие, а компьютеры большие.
12. Многими способами. Самый тупой способ — тотальным перебором всех множителей от 1 до миллиона. Есть и более оптимальные, — лучше всего разложить на простые множители (2^6 и 5^6) и посчитать всякие сочетания. (Лень думать).
Короче говоря, гораздо интереснее у этих задач — не искать стандартные решения, а выламываться из рамок, которые были у автора задачи.
Так же, как Нильс Бор троллил препода по физике с барометром и высотой здания.
2. Двенадцатичашечные весы сделают это за один приём. Как сделать двенадцатичашечные весы в домашних условиях: взять обычные настенные часы, выдрать из них циферблат; подвесить к часовым штрихам двенадцать крышечек от пепсикоки, а сам циферблат подвесить за центр или поставить на точечную опору.
3. Зайти в комнату и устроить короткое замыкание в одной лампочке. Дальше тривиально.
4. Встречная задача: какие интервалы вы можете отмерить этими верёвками?
8. Континуум. А именно:
— северный полюс
— счётное количество окружностей вокруг южного полюса — 1км + 1/2Пk, k=1..+oo
— окружность неопределённости — ровно 1км от южного полюса
— круг некорректности — внутри этой окружности
9. Дофига способов сортировки, — например, подсчётом. Поскольку у сортировок асимптотика O(nlogn), то тормознутая сортировка будет отличаться от линейной (подсчётом) в жалкие 32 раза. Да мы на фоне дисковых операций можем это не заметить. Видимо, задача возникла в эпоху, когда числа были маленькие, а компьютеры большие.
12. Многими способами. Самый тупой способ — тотальным перебором всех множителей от 1 до миллиона. Есть и более оптимальные, — лучше всего разложить на простые множители (2^6 и 5^6) и посчитать всякие сочетания. (Лень думать).
Короче говоря, гораздо интереснее у этих задач — не искать стандартные решения, а выламываться из рамок, которые были у автора задачи.
Так же, как Нильс Бор троллил препода по физике с барометром и высотой здания.
2. Не получится. Вы определите диагональ, на которой лежит фальшивая монета, но вы не знаете, легче она или тяжелее. Но красиво, согласен ;)
Да, получится только если класть монеты крест-накрест, по-очереди. А это уже сложно считать за одно взвешивание.
Значит, надо взять 11 чашек. А последнюю монету вообще спрятать.
А, ну да. Тогда за два. Сперва нашли проблемную пару и десять заведомо подлинных монет, затем взвесили эту пару (или одну монету из пары) вместе с одной из подлинных. Двенадцатичашечные весы позволяют взвешивать две и три монеты.
НЛО прилетело и опубликовало эту надпись здесь
Ну, это из второй комнаты в первую можно только один раз перейти. То есть, достаточно, побывав в первой комнате, одну лампочку закоротить, вторую вывернуть. Во второй комнате )предположим, автомат или предохранитель там же) дёргаем выключатели, пока не выбьет автомат. Помечаем, на каком выключателе выбило. Затем, выключив все выключатели, включаем один из «неизвестных» и идём в первую комнату. Если оставшаяся лампочка горит, то включили выключатель к ней. Если не горит — соседний.
В 4 получается только 2, 3/2, 1, 3/4 и 1/2 часа. Даже 5/4 получить не удаётся :(
На самом деле, делитель может быть любой.
Режем верёвку на много кусочков и поджигаем N концов. Как только один кусочек догорает до конца, немедленно поджигаем новый конец. Если не осталось свободных концов, а что-то поджечь надо, — режем кусочки на ещё более мелкие кусочки.
То есть, сидим и дежурим с ножницами и зажигалкой (либо прикуриваем новый конец от догорающего старого).
Поддерживаем N огней до полного сгорания верёвки.
Таким образом, нам доступны все числа вида
— 1/N — сожгли только одну верёвку
— 1/N + 1/M — сожгли одну, затем другую
— 1/N + (1-1/M)/K — зажгли две верёвки с разными коэффициентами; когда одна догорела, вторую потушили и переподожгли с новым коэффициентом
Режем верёвку на много кусочков и поджигаем N концов. Как только один кусочек догорает до конца, немедленно поджигаем новый конец. Если не осталось свободных концов, а что-то поджечь надо, — режем кусочки на ещё более мелкие кусочки.
То есть, сидим и дежурим с ножницами и зажигалкой (либо прикуриваем новый конец от догорающего старого).
Поддерживаем N огней до полного сгорания верёвки.
Таким образом, нам доступны все числа вида
— 1/N — сожгли только одну верёвку
— 1/N + 1/M — сожгли одну, затем другую
— 1/N + (1-1/M)/K — зажгли две верёвки с разными коэффициентами; когда одна догорела, вторую потушили и переподожгли с новым коэффициентом
Все бы хорошо, но вы ни одного решения правильного не привели, в отличие от Нильса Бора ) Ключевая фраза — «Лень думать» )
Фигассе не привёл. Тибетский домик в горах — неправильно? Весы с кукушкой — неправильно?
Задача: «сколькими способами можно разложить?»
Я два способа привёл: тупым тотальным перебором и арифметическим выражением. Но не конкретизировал ни тот, ни другой.
Очень надо? Да пожалуйста. Перебор
Ещё способы — динамическим программированием, рекуррентным выражением (сейчас час ночи, конкретизировать действительно лень), наконец, залезанием в справочник, гуглением и подсматриванием чужих ответов.
Итого, ответ — 5. Довлеет?
Задача: «сколькими способами можно разложить?»
Я два способа привёл: тупым тотальным перебором и арифметическим выражением. Но не конкретизировал ни тот, ни другой.
Очень надо? Да пожалуйста. Перебор
sixtets n = length (
do
(a,na) <- divisors n
(b,nb) <- divisors na
(c,nc) <- divisors nb
(d,nd) <- divisors nc
(e,f) <- divisors nd
return (a,b,c,d,e,f)
)
where
divisors m = [ (x,m`div`x) | x <- [- abs m .. abs m], x/=0, m`mod`x==0 ]
main = putStrLn $ show $ sixtets 1000000
Ещё способы — динамическим программированием, рекуррентным выражением (сейчас час ночи, конкретизировать действительно лень), наконец, залезанием в справочник, гуглением и подсматриванием чужих ответов.
Итого, ответ — 5. Довлеет?
> Фигассе не привёл. Тибетский домик в горах — неправильно? Весы с кукушкой — неправильно?
Конечно нет. Во первых, это не решение (расщелина не настолько узка, что обе стены были параллельны и не имели перпендикулярной стены, не говоря уже про то, что домик построен; часы всего лишь перекосятся, фальшивая монета может быть и в самой нижней точке и в самой верхней — фейл,...), это всего лишь отмазки из разряда «любым способом» — не попытка решить задачу, а всего лишь попытка использовать неточность постановки задачи, чтобы решить ее неправильно. Я знаю таких разработчиков — если дать им возможность реализовать задачу неверно, они обязательно так и сделают — в силу своей природной лени, видимо )
Решения могут выходить из плоскости задачи и тогда это действительно гениальные решения (как автомат Калашникова — все пытались сделать зазоры меньше, чтобы препятствовать попаданию внутрь всякой шняги типа песка и воды, а чел сделал наоборот — чтобы песок и вода спокойно вываливались наружу и ничему не вредили), но тут явно не этот случай. Хотя вариант с часами — хорошая попытка, но все-таки нет, а значит фэйл — в очередной раз по вине программиста спутник упал, поезда столкнулись )
Конечно нет. Во первых, это не решение (расщелина не настолько узка, что обе стены были параллельны и не имели перпендикулярной стены, не говоря уже про то, что домик построен; часы всего лишь перекосятся, фальшивая монета может быть и в самой нижней точке и в самой верхней — фейл,...), это всего лишь отмазки из разряда «любым способом» — не попытка решить задачу, а всего лишь попытка использовать неточность постановки задачи, чтобы решить ее неправильно. Я знаю таких разработчиков — если дать им возможность реализовать задачу неверно, они обязательно так и сделают — в силу своей природной лени, видимо )
Решения могут выходить из плоскости задачи и тогда это действительно гениальные решения (как автомат Калашникова — все пытались сделать зазоры меньше, чтобы препятствовать попаданию внутрь всякой шняги типа песка и воды, а чел сделал наоборот — чтобы песок и вода спокойно вываливались наружу и ничему не вредили), но тут явно не этот случай. Хотя вариант с часами — хорошая попытка, но все-таки нет, а значит фэйл — в очередной раз по вине программиста спутник упал, поезда столкнулись )
Сказано «все стены». Одна стена из одной — это все или нет? Хорошо, пусть множественное число: две стены на двух этажах, с уступом. Обе-две, ориентированные на юг.
А вы просто тупо цепляетесь за шаблонное решение шаблонной задачи. Ну и смысл в таких интервью, сто раз перетирать про размер люка?
Победит тот, у кого справочник в голове толще.
А вы просто тупо цепляетесь за шаблонное решение шаблонной задачи. Ну и смысл в таких интервью, сто раз перетирать про размер люка?
Победит тот, у кого справочник в голове толще.
В одной стене можно жить?
Я совсем не против выхода за рамки, но тогда уж будьте последовательны и представьте работающее решение.
Измерить высоту здания кидая с него барометр и замеряя время падения — работает. А жить в одной стене — нет )
Я совсем не против выхода за рамки, но тогда уж будьте последовательны и представьте работающее решение.
Измерить высоту здания кидая с него барометр и замеряя время падения — работает. А жить в одной стене — нет )
Вообще без стен живут как-то.
Да, кстати, моё решение про многочашечные весы уже развили коллеги. С одиннадцатью чашками они найдут монету за единственное взвешивание.
Задача 12 висела в Минске, в метро, так рекрутила программеров одна фирма (если интересно какая, напишу в личку).
Правильный ответ и мое решение в одну строку на js
6830208
(function factorizationCount (number, less, result, i) { if (less === 1)return 1; for (i = 1; i <= number; i++) if (!(number % i)) result += factorizationCount (number / i, less — 1, 0); return result;})(1000000, 6, 0) * 32;
(function factorizationCount (number, less, result, i) { if (less === 1)return 1; for (i = 1; i <= number; i++) if (!(number % i)) result += factorizationCount (number / i, less — 1, 0); return result;})(1000000, 6, 0) * 32;
(function f(n, l, r, i) { if (l === 1)return 1; for (i = 1; i <= n; i++) if (!(n % i)) r += f (n / i, l — 1, 0); return r;})(1000000, 6, 0) * 32;
а так бы ваше решение вообще в одну строчку влезло, наверное
А есть вменяемое объяснение, зачем эти задачи задают на собеседовании?
Задача номер 6.
Предположим, что A отправляет письмо B.
Предлагаю так:
1. A кладет письмо в сейф и закрывает ключом А.
2. В приходит к сейфу, видит, что он закрыт, и закрывает на свой ключ.
3. А приходит, видит, что не может открыть сейф, т.к. тот закрыт на оба замка.
4. А отправляет свой ключ через почтальона В.
5. В получает оба ключа и открывает сейф.
Если есть прорезь для писем, то все проще.
1. В закрывает сейф своим ключом.
2. А видит, что сейф закрыт и кладет в него письмо через прорезь.
3. В открывает сейф и читает письмо.
Предположим, что A отправляет письмо B.
Предлагаю так:
1. A кладет письмо в сейф и закрывает ключом А.
2. В приходит к сейфу, видит, что он закрыт, и закрывает на свой ключ.
3. А приходит, видит, что не может открыть сейф, т.к. тот закрыт на оба замка.
4. А отправляет свой ключ через почтальона В.
5. В получает оба ключа и открывает сейф.
Если есть прорезь для писем, то все проще.
1. В закрывает сейф своим ключом.
2. А видит, что сейф закрыт и кладет в него письмо через прорезь.
3. В открывает сейф и читает письмо.
Задача 7:
Условие задачи можно считать не достаточным:
«Путник находится в лесу в какой-то случайной точке. Известно, что площадь леса равна S, а форма может быть совершенно произвольная, однако в лесу нет полян. По какой траектории нужно двигаться путнику, чтобы гарантировано выйти из леса затратив минимальный по длине маршрут?»
Здесь сказано, что необходимо выбраться из леса ГАРАНТИРОВАННО и затратить минимальный по длине маршрут.
В задаче не сказано, что маршрут должен быть наименьший из всех возможных, что накладывает ограничение на решение задачи.
Так как, в принципе путник може выбрать абсолютно любой маршрут, то существует вероятность, что форма леса примет как раз его форму: возрастаюдая спираль, ломаные, пунктиры, что угодно.
Но если исходить из геомертии, то минимальное расстояние между двумя точками — это прямая. И среди тысяч любых траекторий в любом направлении, путник по прямой преодалеет расстояние меньше, чем, скажем, по дуге или еще какой траектории (между двумя точками)
Площадь S здесь дана для того, чтобы исключить возможность представления леса в виде бесконечной прямой. В этом случае траектория «прямая» не является правильным ответом. Так как площать равна S, значит она конечна, значит она является интегралом функции, график которой не является бесконечной прямой (иначе интеграл = 0)
Отсутствие полян внутри леса здесь дано для облегчения задачи. Ведь если в лесу есть поляна, тогда путник не будет знать, выбрался он из леса, или нет.
Все зависит от выбранного направления, и идти надо по прямой. Лучше залезть на дерево и посмотреть, куда идти будет короче :)
Условие задачи можно считать не достаточным:
«Путник находится в лесу в какой-то случайной точке. Известно, что площадь леса равна S, а форма может быть совершенно произвольная, однако в лесу нет полян. По какой траектории нужно двигаться путнику, чтобы гарантировано выйти из леса затратив минимальный по длине маршрут?»
Здесь сказано, что необходимо выбраться из леса ГАРАНТИРОВАННО и затратить минимальный по длине маршрут.
В задаче не сказано, что маршрут должен быть наименьший из всех возможных, что накладывает ограничение на решение задачи.
Так как, в принципе путник може выбрать абсолютно любой маршрут, то существует вероятность, что форма леса примет как раз его форму: возрастаюдая спираль, ломаные, пунктиры, что угодно.
Но если исходить из геомертии, то минимальное расстояние между двумя точками — это прямая. И среди тысяч любых траекторий в любом направлении, путник по прямой преодалеет расстояние меньше, чем, скажем, по дуге или еще какой траектории (между двумя точками)
Площадь S здесь дана для того, чтобы исключить возможность представления леса в виде бесконечной прямой. В этом случае траектория «прямая» не является правильным ответом. Так как площать равна S, значит она конечна, значит она является интегралом функции, график которой не является бесконечной прямой (иначе интеграл = 0)
Отсутствие полян внутри леса здесь дано для облегчения задачи. Ведь если в лесу есть поляна, тогда путник не будет знать, выбрался он из леса, или нет.
Все зависит от выбранного направления, и идти надо по прямой. Лучше залезть на дерево и посмотреть, куда идти будет короче :)
Всё решили!
Насчёт 9 задачи дам комментарий, но я не уверен, что правильный :)
Если бы по условию в файле могли находиться лишь числа из небольшого диапазона, например, от 0 до 100 000, то было бы достаточно эффективно завести обычный словарь, где ключом являлось само число, а значением, количество его вхождений в файл.
Тогда чтобы получить отсортированный файл достаточно единожды пройтись по исходному и создать словарь.
Поскольку у нас диапазон значений не задан, имеет смысл самостоятельно разделить MaxInt на несколько диапазонов и проводить по каждому сортировку вышеуказанным способом. Да, потребуется много проходов по файлу и промежуточные результаты, наверняка, необходимо будет сохранять во временный файл, но если грамотно подобрать параметры, то можно вписаться в ограничения по памяти на реальных машинах и выполнить сортировку за разумное время.
Насчёт 9 задачи дам комментарий, но я не уверен, что правильный :)
Если бы по условию в файле могли находиться лишь числа из небольшого диапазона, например, от 0 до 100 000, то было бы достаточно эффективно завести обычный словарь, где ключом являлось само число, а значением, количество его вхождений в файл.
Тогда чтобы получить отсортированный файл достаточно единожды пройтись по исходному и создать словарь.
Поскольку у нас диапазон значений не задан, имеет смысл самостоятельно разделить MaxInt на несколько диапазонов и проводить по каждому сортировку вышеуказанным способом. Да, потребуется много проходов по файлу и промежуточные результаты, наверняка, необходимо будет сохранять во временный файл, но если грамотно подобрать параметры, то можно вписаться в ограничения по памяти на реальных машинах и выполнить сортировку за разумное время.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Дюжина логических задач с собеседований