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

Question

[frosty7777777]

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

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

Чем-то напоминает задачу оптимизации. Какие есть идеи для решения?

Comments

[Alex Setup]

А какие входные данные? Скиньте примеры (вход/выход)
И желательно ссылку на задачу.
Если есть проверяющая система, то вообще отлично.

[frosty7777777]

Alex, задача есть только в словесной формулировке. Попалась на олимпиаде по программированию.

Answer 1

[longclaps]

Найди этаж - "медианный этаж" и помести всех на него (это такие этажи, что разница между живущими выше и живущими ниже минимальна).
Спустись или поднимись на несколько этажей (столько, чтобы среди них были "родные" этажи постояльцев).
Сравни сумму пройденых пролётов.

Comments

[longclaps]

frosty7777777, вот что за фигня:

Какие есть идеи для решения?

Мой ответ содержит идею решения, и я не люблю, когда топикстартер "забывает", о чем спрашивал.
А если ты туповат и не понял написанного - вот тебе реализация алгоритма

aa = [7, 0, 1, 2]
diff, res = sum(aa), []
for a in aa:
    diff -= a
    res.append(abs(diff))
    diff -= a
print(res, "- это баланс для всех этажей")
print(res.index(min(res)), "- это оптимум")

А вот то, что ты отметил как решение, идеи решения не содержит - нельзя же считать за идею тупой подсчет сумм затрат для всех этажей и поиск мимнмума на этом массиве.
Даже сложность алгоритма Александр указал неверно - по факту O(N^2), стыдоба. Стиль кода - вовсе фейспалм.

[frosty7777777]

longclaps, ты крут :)

Answer 2

[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, безразличны данный этаж, все нулевые над ним, и ещё один ненулевой. (Можно без кода?)