Розглянемо всі варіанти вибору Василем двох задач:
перша й друга задачі;
перша й третя задачі;
друга й третя задачі.
Якщо хоча б в одному варіанті сума складностей не перевищує 47, тоді
відповідь YES, якщо ж ні, то відповідь —
NO.
Оптимальним розливанням соку буде таке:
розлити максимально апельсинового соку людям, які люблять тільки апельсиновий сік;
розлити максимально гранатового соку людям, які люблять тільки гранатовий сік;
розлити залишки соку тим людям, яким подобаються обидва типи.
Порахуємо кількість ям, у яких глибина строго більша ніж \(k\). Нехай їхня кількість — \(y\). За умовою водій може об’їхати \(x\) ям, а досягти точки призначення за
умови, якщо відвалилося не більше ніж одне колесо. Отже, якщо \(x - y \ge -1\), то відповідь
YES, інакше — NO.
Спочатку для зручності подвоїмо масив. Порахуємо кількість оливок від першого до \(\frac{n}{2}\)-го куска включно. Зазначимо, що для того, щоб дізнатися кількість оливок від другого до \((\frac{n}{2}+1)\)-го шматка, нам достатньо відняти 1 оливку від теперішньої кількості, якщо вона була на першому шматку, та додати 1 оливку, якщо вона є на \((\frac{n}{2}+1)\)-му шматку. Отже, за один прохід ми можемо порахувати кількість оливок на всіх можливих розділеннях піци. І серед усіх розділень піци взяти те, де є мінімальна можлива кількість оливок.
Переберемо довжину одного з крайніх відрізків, наприклад, правого. Нехай сума всіх елементів із цього відрізка рівна \(x\), а сума всіх інших елементів — \(2 \cdot s\). Доведемо, що для зафіксованого правого відрізка (його розміру), ту частину масиву, яка не входить у правий відрізок, оптимально поділити так, щоб модуль різниці цих двох відрізків був мінімально можливим.
Нехай ми розділили решту масиву на дві половини із сумами \(a\) й \(b\). Без обмежень загальності поставимо \(a \le b\) та \(2 \cdot y = b - a\) Тоді \(a + b = s\), \(a = s - y\), \(b = s + y\).
Тепер розглянемо три випадки взаємного розташування \(x\), \(a\) й \(b\):
\(x \le a \le b\) — тоді відповідь рівна \(b - x = s - x + y\);
\(a \le x \le b\) — тоді відповідь рівна \(b - a = 2 \cdot y\);
\(a \le b \le x\) — тоді відповідь рівна \(x - a = x - s + y\).
У цих випадках \(s\) та \(x\) є константами для зафіксованого правого відрізка. У кожному з них для того, щоб мінімізувати відповідь, потрібно мінімізувати \(y\).
Оскільки всі числа додатні, то оптимальне \(y\) для фіксованого правого відрізка можна знайти бінарним пошуком. Також можна шукати оптимальні розбиття для всіх можливих довжин правого відрізка двома вказівниками.
Зауважимо такий факт: якщо ми можемо зареєструвати всіх учасників за деякий час \(t\), то ми можемо зареєструвати всіх учасників і за час \(t + 1\). Скористаємось ідеєю бінарного пошуку по відповіді. Для цього попередньо відсортуємо за зростанням масив координат організаторів \(a\) та масив координат команд \(b\). Зафіксуємо якийсь час \(t\) та перевіримо, чи можливо за цей час зареєструвати всі команди. Для цього переберемо по черзі кожного організатора та будемо підтримувати вказівник на останню команду, яку може зареєструвати цей організатор, витративши час не більший за \(t\). Якщо вдасться зареєструвати всі команди, то змінимо праву границю для нашого бінарного пошуку, а якщо ні — ліву.
Якщо \(k = 1\), тоді існує єдине розбиття числа \(n\) на степені двійки — двійкове представлення числа.
Нехай ми знаємо розбиття \(n\) на \(a_1, \ldots, a_k\), де \(a_i\) позначає суму карт із кольором \(i\). Кожне таке розбиття відповідає єдиному набору карт, і кожен набір карт відповідає єдиному такому розбиттю, а отже кількість наборів карт, що в сумі дають \(n\) рівна кількості розбиттів \(n\) на \(a_1, \ldots, a_k\). А кількість таких розбиттів — це кількість комбінацій з повтореннями (детальніше про це можна прочитати за посиланням ). Тож кількість комбінацій з повторами рівна \(C_{n+k-1}^{k-1}\) — біноміальному коефіцієнтові, який можна порахувати за заданим модулем багатьма способами.