У даній задачі достатньо просимулювати процес з умови, використовуючи цикл while.
Неважко переконатися, що наступний паттерн задовольняє умову задачі:
xoxoxo...
xoxoxo...
oxoxox...
oxoxox...
xoxoxo...
xoxoxo...
.........Покажемо, що Зенику оптимально видалити або якусь кількість сторінок з початку, або з кінця щоденника. Припустимо, що Зеник вирвав якісь сторінки \(L, L + 1, …, R\) з середини щоденника, але залишив і першу, і останню сторінки (тобто \(1 < L \le R < n\)). Тоді розглянемо середнє арифметичне оцінок на сторінках \([1, L - 1]\) (нехай це буде якесь число \(А\)), і середнє арифметичне оцінок на сторінках \([R + 1, n]\) — \(B\). Якщо \(B \le A\), то Зеник міг би вирвати всі сторінки від \(L\) до \(n\), при цьому не погіршивши загальне середнє, а якщо \(A \le B\), то він би міг вирвати всі сторінки від 1 до \(R\), також не погіршивши загальне середнє.
Таким чином, достатньо просто перебрати всі можливі префікси та суфікси заданого масиву і вибрати серед них максимальний. Це неважко зробити з лінійною складністю просто ітеруючись по масиву та підтримуючи кількість і суму оцінок.
Розв’яжемо дану задачу для двох точок \((x_1, y_1)\) і \((x_2, y_2)\). Якщо \(x_1 + y_1 \mod 3 \neq x_2 + y_2 \mod 3\), то відповіді не існує, оскільки ходи не змінюють остачу від ділення на 3 для суми координат. Неважко переконатись, що існує єдина точка \((x, y)\), у яку можна пересунути точки, використовуючи мінімальну кількість ходів.
Уміючи розв’язувати задачу для 2 точок, ми можемо зводити задачу з розміру \(n\) до розміру \(n - 1\) поки \(n \ge 2\).
Розглянемо найнижчу вершину \(u\), яку потрібно атакувати. Хаймарс вигідно ставити у найвищого предка \(u\), з якого ще можливо атакувати \(u\), оскільки таким чином він уразить найбільшу кількість вершин. Після цього можна видалити всі вершини з руснею, уражені хаймарсом, і повторити процес.
Схожий процес можна реалізувати, використовуючи алгоритм пошуку у глибину, підтримуючи для кожної вершини найглибшу русню і найнижчого хаймарса у піддереві.
Для початку посортуємо роботи за прибутком. Обчислимо масив \(q\) з імовірностями потрапити на роботу кращу за \(i\) за один місяць.
\(q_n = 0, q_{n-1} = p_n, q_{n-2} = q_{n-1} + (1 - p_n) (p_{n-1}), q_{n-3}=...\)
Далі будемо рахувати вклад роботи \(i\) у відповідь. Легко бачити, що перша робота приносить значення \(a_1 \cdot \sum_{j=1}^{m}(1 - q_1)^j\) до відповіді. Для 2 роботи вклад можна порахувати за допомогою принципу включення-виключення: \(a_2 \cdot \sum_{j=1}^{m}((1 - q_2)^j - (1 - q_1)^j)\). У цій формулі \((1 - q_2)^j\) означає що Зенику не вдалось потрапити на роботу кращу за 2, \((1 - q_1)^i\) потрібно відкинути, щоб виключити імовірність залишитись у першій компанії. Аналогічно значення можна порахувати для роботи \(i\).
Суму \(\sum_{j=1}^{m}(1 - q)^j\) порахуємо використовуючи формулу суми геометричної прогресії.
Припустимо Зеник найняв вже \(k\) людей. Розглянемо початкову множину їх зарплат \(A\). Зрозуміло, що не має сенсу подвоювати зарплату працівнику з найбільшою початковою зарплатою. Для кожного іншого працівника, будемо подвоювати його зарплату допоки вона не стане більшою за \(max(A) / 2\).
Тепер посортуємо всіх працівників за новими зарплатами — \(a_1 \le a_2 \le a_3 ... \le a_k < 2a_1\). Зрозуміло, що з цього моменту часу все, що може зробити Зеник це подвоїти зарплати якійсь кількості працівників з найменшими зарплатами. Якщо Зеник залишить все як є, то нерівність буде \(a_k - a_1\). Якщо ж він подвоїть зарплати першим \(1 \le i < k\) працівникам, то нерівність буде \(2a_i - a_{i+1}\). Тому підтримуватимемо множину \(S\) таких значень.
Припустимо тепер Зеник захоче найняти ще одного працівника з початковою зарплатою \(x\). Аналогічно подвоюватимемо цю зарплату доки вона не перевищить \(max(A) / 2\). Тепер є два випадки:
\(x \le max(A)\). Тоді якщо \(a_i \le x \le a_{i+1}\), то потрібно видалити з множини \(S\) число \(2a_i - a_{i+1}\) та вставити два нові відповідні числа (якщо \(x < a_1\), то просто вставити одне нове число).
\(x > max(A)\). Тоді додамо \(x\) в множину \(А\) та почергово будемо подвоювати зарплату найменш оплачуваному працівнику, аби знову досягти вищеописаного інваріанта \(min(A) * 2 > max(A)\). Підтримуватимемо при цьому актуальні значення множини \(S\).
Можна помітити, що впродовж всього часу жоден працівник не отримає подвоєнь зарплати більше аніж \(\log (max(A))\) разів. Тому сумарна кількість подвоєнь продовж всього процесу — \(O(n \log (max(A))\), а кожну таку операцію можна виконувати за час \(O(\log n)\) використовуючи, наприклад, set або map. Тому сумарна складність становитиме \(O(n \log n \log(max(A))\).