Максимальная сумма четырёх чисел

Обозначим третье число через zz. Тогда первые два не больше z−2z-2 и z−1z-1, четвёртое не больше ⌊U−1z⌋\left\lfloor \frac{U-1}{z}\right\rfloor. Значит, сумма не превосходит 3z−3+⌊U−1z⌋3z-3+\left\lfloor \frac{U-1}{z}\right\rfloor. Если (z−2)(z−1)≤L(z-2)(z-1)\leq L, первые два вообще не смогут удовлетворить нижней границе; если z(z+1)≥Uz(z+1)\geq U, не найдётся четвёртого. Во всех остальных случаях набор z−2z-2, z−1z-1, zz, ⌊U−1z⌋\left\lfloor \frac{U-1}{z}\right\rfloor допустим и достигает указанной суммы. Перебираем конечные zz от 3 до ⌊U−1⌋\left\lfloor \sqrt{U-1}\right\rfloor; таблица даёт все кандидаты максимума.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 1. Обозначим третье число через zz. Тогда первые два не больше z−2z-2 и z−1z-1, четвёртое не больше ⌊U−1z⌋\left\lfloor \frac{U-1}{z}\right\rfloor. Значит, сумма не превосходит 3z−3+⌊U−1z⌋3z-3+\left\lfloor \frac{U-1}{z}\right\rfloor. Если (z−2)(z−1)≤L(z-2)(z-1)\leq L, первые два вообще не смогут удовлетворить нижней границе; если z(z+1)≥Uz(z+1)\geq U, не найдётся четвёртого. Во всех остальных случаях набор z−2z-2, z−1z-1, zz, ⌊U−1z⌋\left\lfloor \frac{U-1}{z}\right\rfloor допустим и достигает указанной суммы. Перебираем конечные zz от 3 до ⌊U−1⌋\left\lfloor \sqrt{U-1}\right\rfloor; таблица даёт все кандидаты максимума.
таблица=((7;12;30);(8;10;31))\text{таблица}=\left(\left(7;12;30\right);\left(8;10;31\right)\right)
пример=(6;7;8;10)\text{пример}=\left(6;7;8;10\right)

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу