frosty7777777
@frosty7777777

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

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

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

Чем-то напоминает задачу оптимизации. Какие есть идеи для решения?
  • Вопрос задан
  • 367 просмотров
Решения вопроса 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, безразличны данный этаж, все нулевые над ним, и ещё один ненулевой. (Можно без кода?)
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы