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