14 окт. 2011 г.

Маляры и котлеты

- Илья, где ты пропадаешь две недели?
- В глубоком-глубоком роуминге :)

Но я вернулся, почти всем ответил на почту и комментарии, а теперь, извините, поделюсь неприятным впечатлением от Питерского Пулково-1. Несколько лет я не был в этом дивном месте, поэтому успел подзабыть его бардак и грязь. Если бы номер гейта на билете соответствовал реальному номеру двери, от которой автобус повезёт к самолёту, если бы табло над гейтом правильно указывало номер рейса, то сотрудницы аэропорта не были бы вынуждены кричать: «Рейс ###, подходите сюда, а рейс ### отойдите, сейчас мы не вас сажаем. Да, мы знаем, что на табло сейчас указан ваш город, поэтому не читайте табло». Зачем я это пишу? Пару лет назад помогло же :) А пока, если меня спросят европейцы, через какую из столиц лучше влетать в Россию, то я однозначно назову Москву. Как минимум, в Москве работают лифты, хорошо светят лампочки и моют туалеты, а в Пулково-1 в тёмных коридорах неподвижно стоят грязные эскалаторы, о которых сразу забываешь, посетив уборную. Злые языки утверждают, что ремонта там не было со времён блокады Ленинграда.

Ладно, забыли и проехали. Давайте лучше вспомним важный жанр задачек на поиск оптимального решения (в данном случае, минимального количества действий для достижения результата):

1. Много лет назад у нас была задачка о хрупких шариках: Есть стакан с очень дорогими одинаковыми хрупкими шариками из очень прочного материала. И есть лестница с сотней ступенек. Какой минимум шариков придётся разбить, чтобы выяснить предельную высоту (число от 1 до 100 — бросаем со ступенек), с которой можно ронять шарики целыми (т.е. чтобы они не разбились)?

2. Старинная детская задачка о готовке звучит так: На одной сковороде может поместиться не более 2 котлет. Одна сторона котлеты жарится 1 минуту. За какое минимальное время можно пожарить три котлеты с 2-х строн.

3а. Два маляра столкнулись на дороге с другими двумя малярами. Этикет обязывает каждого из первой пары поздороваться с каждым из второй пары, но руки у каждого маляра испачканы в краске своего цвета. А так как маляры не хотят пачкать руки в краске другого цвета, то у них есть несколько чистых перчаток. Какое минимальное количество перчаток они будут вынуждены испачкать, чтобы поприветствовать друг друга?

3б. Три маляра столкнулись на дороге с одним маляром. Соответственно, каждый из них должен с ним поздороваться. Остальное как в задаче (3а): их руки испачканы четырьмя цветами, есть несколько чистых перчаток. Сколько перчаток им придётся испачкать?

(последние две задачки своевременно напомнил Антон, а я чуть-чуть поменял формулировки)

Пожалуйста, напишите в комментариях статус по этим задачкам примерно в таком виде:
   1. Помню, ответ x,
   2. Давно знаю, ответ y,
   3. а) тоже слышал, ответ z1, б) первый раз слышу, ответ z2.


Хороших выходных!

35 комментариев:

  1. Анонимный14.10.2011, 9:39

    1. Помню, ответ 1;
    2. Первый раз слышу, ответ 3 минуты;
    3. а) первый раз слышу, ответ 2; б) тоже впервые слышу, ответ 2.
    Григорий

    ОтветитьУдалить
  2. По 1.

    Есть более интересная вариация задачи: пусть мы кидаем объекты с этажей; не разбившиеся объекты можно подобрать с земли. Но мы ленивые (старые) и хотим минимизировать число подъемов вверх по лестнице(вниз спускаемся без проблем), чтобы определить с какого этажа объекты бьются.

    Если классика решается двумерной динамикой, то тут (авторское и то, до которого мы дошли) требует пятимера.

    Можно еще вариации генерить...

    ОтветитьУдалить
  3. Анонимный14.10.2011, 10:19

    к комментарию 67108864: кажется, что ответ тот же, что и в классике. Два шарика, не более 19 подъёмов вверх по лестнице. Если считать вариант "поднялся на 10-й этаж - шарик не разбился, дошел до 20-го, кинул второй шарик" за один подъём, а не за два - тогда задачка резко усложняется.

    ОтветитьУдалить
  4. 3а, 3б — это вариант задачи про три презерватива. ;) Хотя, кажется, есть разница, поскольку у перчатки есть левизна, а у презерватива — нет

    1,2 — помню ответы.

    ОтветитьУдалить
  5. Анонимный14.10.2011, 11:08

    в задаче 3б должно быть три, в остальном согласен с первым комментарием. Первую задачу помню. У второй есть аналог с автомобилем и запаской (не по формулировке, но по виду решения), поэтому как бы знаю. Третьи первый раз слышу.

    Антон

    ОтветитьУдалить
  6. 1. Первый раз, 1
    2. Помню, 3
    3. Первый раз, а-2, б-3

    ОтветитьУдалить
  7. Анонимный14.10.2011, 13:31

    2 Про котлеты - самая лучшая, 4 минуты.

    ОтветитьУдалить
  8. Анонимный14.10.2011, 13:53

    1. Помню, ответ 1,
    2. Первый раз, 1 мин
    3. Первый раз, а-1, б-3.

    ОтветитьУдалить
  9. 1. помню, ответ 1
    2. первый раз вижу, ответ 2
    3а. видел у антона, две перчатки
    3б. тоже там видел, но ответ у меня три. если не прав, объясните как можно с двумя обойтись

    ОтветитьУдалить
  10. Анонимный14.10.2011, 15:12

    1. давно знаю. ответ - 1
    2. помню. ответ - 3
    3а. помню про презервативы. ответ - 2
    3б. не видел. ответ - 2.
    P.S. Через ЖЖ не авторизовало, аккаунту gmail Сказало account do not have access. Фигня какая-то

    ОтветитьУдалить
  11. 1. Не видел, ответ 1
    2. Давно знаю, ответ 3
    3а. Не видел, ответ 2
    3б. Не видел, ответ 2

    ОтветитьУдалить
  12. Анонимный14.10.2011, 16:56

    1) Давно знаю, 1
    2) Помню, 3
    3а) Не видел, 2
    3б) не видел, 2

    ОтветитьУдалить
  13. 1. первый раз слышу, ответ 1
    2. давно знаю, ответ 3
    3а. давно знаю (в варианте про презервативы), ответ 2
    3б. впервые слышу, ответ 2

    ОтветитьУдалить
  14. 1) Помню задачу, тогда не решил, теперь заморочился - оказалось неправильно.
    2) Знаю, где-то в детстве далеком точно решал. ответ: 3.
    3а) Не знал, решил, но ответ 3. Что я делаю не так?
    3б) Тоже не знал, тоже три. Странно. Опять же: можно выворачивать перчатки?Это может быть важно.

    ОтветитьУдалить
  15. Анонимный15.10.2011, 6:05

    Азат, конечно перчатки выворачивать нужно. Иначе совсем неинтересно :-)

    ОтветитьУдалить
  16. гм, я тут опечатался, во второй задаче ответ конечно же 3 минуты.
    насчет третей - можно снимать перчатки и передавать другому?

    ОтветитьУдалить
  17. Несколько недель назад я тоже был проездом в аэропорту Пулково-1, и хотел бы поделиться некоторыми впечатлениями.

    1. Трансфер Пулково-2 -> Пулково-1

    Я прилетел в терминал Пулково-2, и мне надо было попасть на внутренний авиарейс, в терминал Пулково-1. Между этими двумя терминалами достаточно большое расстояние, пешком идти минут 40 (и самое главное, непонятно как). Вполне логично предположить, что между терминалами должен ходить автобус - "шаттл" аэропорта или хотя бы городской транспорт. На самом деле "шаттла" нет (как мне сказали, над его запуском руководство аэропорта еще только размышляет), а на городском транспорте придется ехать до метро Московская и обратно. Пассажир, у которого следующий рейс вылетает из Пулково-1, должен получить багаж и подойти к окошку "Трансфер" на первом этаже аэропорта, показать билет и объяснить ситуацию. Любезная женщина, которая сидит за этим окошком, собирает пассажиров, которым нужно попасть в другой терминал. Когда набирается достаточно большая группа, женщина выводит их на улицу и усаживает в специальный микроавтобус, который едет до Пулково-1. Мне такая организация трансфера показалась очень милой, но наверное регулярный автобус был бы более практичным решением.
    Автоматического перевоза багажа между терминалами нет. То есть нужно получить весь багаж в Пулково-2 и сдать в Пулково-1.

    2. Вход в аэровокзал

    Для того, чтобы попасть в аэровокзал, необходимо пройти через входной пункт контроля, "просветить" сумки и пройти через металлоискатель. Поскольку на входе стоит только одна установка для проверки багажа и одна или две рамки металлоискателя, очередь двигается очень медленно. Вход, в котором я стоял в очереди, почему-то был еще и выходом. Большая часть очереди стояла на улице и в длинном тамбуре, в котором постоянно дул холодный ветер. Пассажиры спешили, ругались и обещали жаловаться руководству. Сотрудники аэропорта тоже ругались и говорили, что их руководство уже давно не слушает, поэтому жалуйтесь на здоровье. К слову, в предыдущий раз я был в этом терминале три года назад, и основное воспоминание о нем - холодный вход с очередью.
    На мой взгляд, гораздо более удобный вход можно сделать за счет небольшого дополнительного помещения снаружи, либо за счет переноса пункта контроля глубже внутрь аэровокзала.

    3. Организация пространства

    Внутри здания очень тесно, всюду очереди, переходы между этажами очень узкие и извилистые. Указатели есть, но мне приходилось задумываться о том, как попасть в то или иное место. Если я правильно понял, для того, чтобы пройти от входа к выходу, нужно один раз подняться, и один раз спуститься по лестнице.

    4. Контроль перед залом вылета

    Очень тесное помещение с длинной, но относительно быстро двигающейся очередью. Сотрудников мало, места, где можно было бы раздеться / сложить вещи тоже очень мало.

    Вообще, на мой взгляд, конкретно эта процедура максимально адекватно устроена в европейских аэропортах. Типичная схема примерно такая: есть "лента", вдоль которой двигается очередь (примерно как в столовой). По мере приближения к сканирующему оборудованию, люди в очереди снимают верхнюю одежду и выкладывают вещи в коробки, которые стоят на ленте. Ключевой момент - с другой стороны ленты стоят сотрудники аэропорта, которые помогают пассажирам (если надо - подержат сумку, помогут сложить вещи в коробку, при необходимости перенесут сумку назад, чтобы пропустить еще раз через сканирующий аппарат).

    5. Зал вылета

    В зале на первом этаже почти в самом центре стоит курилка, рядом с которой сильно пахнет табачным дымом. В туалете старая сантехника, грязно. В женский туалет была очередь. Неужели для одного из крупнейших аэровокзалов России нормальные туалеты - нерешаемая проблема?

    Конечно большая часть неприятных моментов объясняется тем, что зданию аэровокзала около 40 лет, и со времен проектирования и постройки значительно вырос пассажиропоток и изменились требования безопасности. Но ведь все эти проблемы вполне решабельны, и стоимость решения совсем не фантастическая!

    ОтветитьУдалить
  18. 1. Такой вариант первый раз слышу, ответ 1.
    Более сложный вариант, на мой взгляд:
    Есть всего два шарика и сто ступенек. За какое минимальное количество попыток можно узнать с какой высоты шарики разбиваются. Или лучше сказать какая оптимальная стратегия для получения ответа.
    2. Не видел, ответ 3.
    3а. Не видел, ответ 4.
    3б. Не видел, ответ 3.
    Тут вот говорят что можно переворачивать перчатку, но разве перчатка не будет уже испачкана краской внутри?

    ОтветитьУдалить
  19. 1. не понимаю условие задачи :(
    2. 4 минуты. Народ, а почему три все пишут, объясните плиз!
    3а. 4
    3б. 4

    ОтветитьУдалить
  20. fibon-ache,
    > можно снимать перчатки и передавать другому?
    Правилами не запрещено.

    Дима, спасибо за детальное описание проблем этого аэропорта.

    Voland
    > Тут вот говорят что можно переворачивать перчатку, но разве перчатка не будет уже испачкана краской внутри?
    Будет, конечно. Но иногда это не мешает.

    la_sotte,
    детали условия задачи и сама задача были давно разобраны (ссылка в заметке есть).
    Что касается ответов на вторую и третью задачки, то складывается впечатление, что Вы стараетесь найти не оптимальное, а хоть какое-то решение.

    ОтветитьУдалить
  21. 1. Первый раз. Ответил 1, но решил, что сильно просто, начал рыть условие и искать, где ошибся (так и не понял, для чего в условии указана очень высокая прочность шариков?). Прошел по ссылке и понял, что в том месте, где я искал подвох скрупулезнее всего, его не оказалось, а связан он с неверным чтением условия и поиском алгоритма оптимального по времени, а не по экономии шариков. Действительно, здесь "программистский" подход может завести не в ту степь =)
    2. Первый раз, ответ 3 мин.
    3. Смутно помнил подобную задачу в формулировке с презервативом, но т.к. забыл и условие, и решение, пришлось решать повторно. В условии есть некоторая неоднозначность: у маляров перчатки парами или нет? Если парами, то можно ли правой рукой пожимать левую руку? Если не парами, то можно ли совершать рукопожатие левыми руками? Поскольку в условии эти моменты не оговорены, я решил, что подразумевается: перчатки не обязательно парные и можно совершать рукопожатие левыми руками. Тогда ответы:
    3а. 2 перчатки
    3б. 2 перчатки
    3б после 3а решается быстро, т.к. принцип обмена перчатками достаточно похож.

    Я сравнительно недавно познакомился с вашим блогом и сейчас активно читаю его прошлые статьи. Спасибо вам большое за такой замечательный интернет-дневник и такое вежливое отношение к посетителям, за внимательное чтение комментариев, помощь и постоянное желание слегка подтолкнуть к решению, не раскрывая его. Все это – большая редкость в современном рунете! Постараюсь в ближайшее время прокомментировать потрясающую задачу про туземцев острова беззеркалья, которая не решалась и не выходила у меня из головы два полных вечера подряд.

    Почему-то не могу подписаться ни через LiveJournal, ни через Google: "Input error: Cookie value is null for FormRestoration"

    ОтветитьУдалить
  22. Дмитрий,
    я понимаю условие третьей задачи так:
    - левые и правые перчатки не отличаются друг от друга,
    - поэтому у маляров они не парами, а по одной.

    Спасибо за тёплые слова!
    Досадно, что авторизация иногда неправильно работает. Здорово, что Вы смогли пробиться через это препятствие.

    ОтветитьУдалить
  23. 1. Совсем недавно читал блог с конца.
    2. Решил быстро. Ответ 3 минуты.
    3. Задачу не видел. Честно не понял до конца условия задачи. Получается перчатка изнутри не пачкается? Тогда: 3а - 2 перчатки, 3б - 1 перчатка.

    ОтветитьУдалить
  24. Допустим пачкается, тогда всё равно 3а - 2 перчатки. Правда с одним условием. 3б - 3 перчатки.

    ОтветитьУдалить
  25. «
    - левые и правые перчатки не отличаются друг от друга,
    - поэтому у маляров они не парами, а по одной.
    »

    Тогда задача точно не отличается от задачи про два презерватива (я почему-то в прошлом комментарии почему-то написал три вместо двух).

    Если же левизна всё-таки есть, то ответ в 3а будет отличаться — три перчатки вместо двух (правда, строго доказать пока не вижу как), а в 3б ответ такой же — две. Здесь под левизной подразумевается такая особенность, что у каждой перчатки есть две стороны — левая и правая, но если перчатку вывернули, то надеть на ту же руку уже нельзя.

    Хм, сейчас заметил, что фраза «левые и правые перчатки не отличаются друг от друга» оставляет некоторую неопределенность. Если есть левизна в том виде, как я определил, то перчатки изначально все одинаковы в том смысле, что путем выворачивания можно их все привести к каноническому виду — чтобы надевались на правую руку. Что оставляет два варианта толкования этой фразы, приводящих к разным ответам для 3а.

    ОтветитьУдалить
  26. Ой, я в предыдущем комментарии везде перепутал 3а и 3б.

    ОтветитьУдалить
  27. Анонимный20.10.2011, 7:12

    Илья, вторая задача мне понравилась - интересная и жизненная и комуто может быть полезная на практике, остальные imho высосаны, не из мира сего, поэтому и не даются легко некоторым здесь присутствующим.

    Вот Вы лучше Илья объясните на пальцах чем разновидность дихотомии, основанная на числах Фибоначчи, лучше половинного деления. А то у меня из закоулков памяти неожиданно всплыла фраза лектора, что якобы лучше, а вот чем и при каких обстоятельствах не могу понять. Какое бы число элементов упорядоченного массива я ни пытался взять для эксперимента, у меня всегда получалось, что поиск подходящего элемента методом половинного деления в худшем случае был быстрее либо таким же по скорости по сравнению с методом деления в пропорции Фибоначчи в худшем случае. Или речь должна идти о статистическом преимуществе? Помогите пожалуйста.

    Раз уж тут затронута тема дихотомии.

    ОтветитьУдалить
  28. Уважаемый аноним, спасибо за интересный вопрос. Он немножко не по адресу, потому что я не специализируюсь на этих методах. Поэтому я могу только поделиться своей версией ответа на вопрос.

    > Какое бы число элементов упорядоченного массива я ни пытался взять для эксперимента, у меня всегда получалось...
    В этом и дело. Вы проверяете эти два метода на одной задаче, а заточены они под различные постановки.

    Если задача звучит так: «Есть монотонная функция f(x), определённая на интервале [a, b], найти x из [a, b], для которого f(x) отличается от заданного y не больше чем на d», то метод деления пополам, конечно, должен показывать максимальную эффективность, потому что исследуемый интервал на каждой итерации сокращается в два раза (если мы ничего не знаем о функции f(x), то более эффективного решения не может быть).

    Если же наша задача состоит в поиске такого x из [a, b], для которого f(x) является минимальным значением этой функции на этом интервале, то начинаются интересные эффекты:

    1. В методе деления пополам для принятия решения о сужении интервала мы опираемся на значения в трёх точках (двух крайних и одной средней). А метод золотого сечения опирается на значения в четырёх точках, что должно увеличивать вероятность выбора правильного интервала (содержащего глобальный минимум).

    2. В методе деления пополам отрезок всякий раз сокращается в два раза, а в методе золотого сечения ~1.7, что опять же уменьшает вероятность упустить интервал, содержащий искомое значение.

    Вообще тут всё зависит от того, что мы знаем о функции f(x). Но даже если достоверно известно, что на данном интервале функция имеет только один локальный минимум (даже если известно, что она сначала строго убывает, а потом строго возрастает), то легко придумать примеры, когда значения в одной центрально точке не хватит для выбора правильного интервала.

    Более того, для таких функций доказано, что достаточно иметь значения в двух точках внутри интервала (см. ternary search). Таким образом, методы Фибоначчи и золотого сечения можно считать, например, разновидностью тернарного поиска. Отличие в том, что эти методы оптимизированы по количеству вычислений f(x) (классический тернарный поиск предполагает в два раза больше вычислений, чем эти методы).

    Как я понимаю, в статье 1966 года Avriel, Mordecai; Wilde, Douglass J. , "Optimality proof for the symmetric Fibonacci search technique" как раз поясняется, в каком смысле эти методы являются оптимальными. Если я правильно понял, речь об "удельном сокращении интервала" (т.е. о доле сокращения на каждое обращение к функции).

    ОтветитьУдалить
  29. Занятно, я слышал вторую задачу в варианте про двух мужчин, двух женщин и, извините за выражение, венерические заболевания и презервативы :) В любом случае, ответ 2.

    ОтветитьУдалить
  30. Извиняюсь, я имел в виду не вторую, а третью, о малярах.

    ОтветитьУдалить
  31. Grigory Javadyan, да, это известная формулировка, её выше уже пару раз вспоминали. Я стараюсь предлагать задачки в терминах "не из начальной школы" (даже пятиклассники уже не хихикают, услышав слово "презерватив" :).

    ОтветитьУдалить
  32. Илья, а вы будете разбирать представленные задачи? А то я, честно говоря, никак не могу понять как управиться с двумя перчатками.

    ОтветитьУдалить
  33. Voland, хорошо, мы разберём их в одной из следующих заметок.

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний