frosty7777777
@frosty7777777

Как решить хитрую задачку про этажи?

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

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

Чем-то напоминает задачу оптимизации. Какие есть идеи для решения?
  • Вопрос задан
  • 212 просмотров
Решения вопроса 2
  • longclaps
    @longclaps
    Найди этаж - "медианный этаж" и помести всех на него (это такие этажи, что разница между живущими выше и живущими ниже минимальна).
    Спустись или поднимись на несколько этажей (столько, чтобы среди них были "родные" этажи постояльцев).
    Сравни сумму пройденых пролётов.
    Ответ написан
  • @Mercury13
    Программист на «си с крестами» и не только
    Пусть турнир назначен на этаже X.
    На этажах 1…X живут L’ людей, на этажах X+1…N — H′ людей.
    Вопрос 1. Стоит ли переносить турнир на этаж X+1?
    Тогда для L′ людей добавляется лишний этаж, для H′ — исчезает лишний этаж, и выигрыш будет H′−L′.
    Стоит, если H′ > L′. Не стоит, если H′ < L′. Безразлично, если H′ = L′.

    Вопрос 2. Возможно ли такое: вверх на 1 перенести не удаётся (будет хуже или безразлично), но этаж Y > X оптимальнее (строго)?
    Раз вверх на 1 перенести нельзя, то H’ <= L’.
    Если этаж Y − 1 безразличен с Y, перенесём турнир туда. Если Y − 2 тже безразличен, то туда, и т.д. Остановимся на этаже Z. Видно, что Z > X + 1: если мы в результате этих движений добрались до X+1, то он лучше X, противоречие.
    Раз Z — оптимальный этаж, то у этажа Z−1 > X есть свои L″ и H″, и поскольку с Z−1 на этаж вверх перенести всё же можно, то H″ > L″.
    С другой стороны, при повышении этажа увеличивается L и уменьшается H, и L″ >= L′ >= H‘ >= H″, то есть H″ <= L″. Противоречие.

    Следствие 3. Если турнир выгодно перенести на несколько этажей выше/ниже, то его выгодно перенести и на этаж выше/ниже.

    Задача 4. Пусть на этажах 1…X−1 живут L людей, на этаже X — M людей, на этажах X+1…N — H людей.
    Для простоты считаем, что сверху и снизу есть по фиктивному пустому этажу — то есть теоретически можно (на практически неоптимально) проводить турнир в подвале и на чердаке.
    Задачу с переносом турнира вверх мы уже решали, и условие того, что турнир нельзя (или безразлично) перенести на этаж вверх: H <= L + M.
    Условие того, что турнир можно (или безразлично) перенести с этажа X−1: H + M >= L.
    Поскольку H + M + L = N (кол-во людей), то эти условия можно записать в виде: L + M >= N/2, L <= N/2
    (всё, получили чеканное условие, и ключи от чердака и подвала можно отдать техслужбам гостиницы.)

    Решение: Идём по этажам, считаем людей. Где накопится N/2, там проводим турнир.

    // считаем полное кол-во
    N = 0
    для i = [0..nFloors)
      N += a[i]
    // ищем, где половинка N
    sum = 0;
    для i = [0..nFloors)
      sum += a[i]
      если sum * 2 >= N
        вывести: i
        СТОП

    Расширенное решение: Если накопилось ровно N/2, безразличны данный этаж, все нулевые над ним, и ещё один ненулевой. (Можно без кода?)
    Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через TM ID
Похожие вопросы