Максимални принос - Решење

Груба сила

Задатак може бити решен грубом силом, тј. испробавањем свих могућности расподеле додатне дужине. За сваку дужину \(i\) између \(0\) и \(c\), додајемо \(i\) страници \(a\) и \(c-i\) страници \(b\), израчунавамо површину и тражимо максимум тако добијених површина.

#include <iostream>
#include <algorithm>
using namespace std;

long long maksimalniPrinos(long long a, long long b, long long c) {
  long long maks = a * (b + c);
  for (long long i = 1; i <= c; i++)
    maks = max(maks, (a+i)*(b+c-i));
  return maks;
}

int main() {
  long long a, b, c;
  cin >> a >> b >> c;
  cout << maksimalniPrinos(a, b, c) << endl;
}

Израчунавање максималног приноса

Од свих правоугаоника датог фиксираног обима, највећу површину има квадрат. Заиста, ако је познат обим правоугаоника \(O = 2(a+b)\), тада је познат и полуобим \(a + b = s\). Површина \(a\cdot b = a \cdot (s - a) = a\cdot s - a\cdot a = s^2/4 - (a - s/2)^2\). Пошто је \((a - s/2)^2 \geq 0\), површина не може бити већа од \(s^2/4\), а једнака је тој вредности када је \(a = b = s/2\). Зато увећање треба направити тако да се добије облик који је што сличнији квадрату.

Нека је \(a \leq b\). Ако је \(a + c \leq b\), тада се целокупан износ увећања \(c\) може додати на мању страницу \(a\). У супротном се прво краћа страница \(a\) продужи тако да постане једнака дужој страници \(b\), а затим се преостали износ увећања (\(c - (b - a)\)) подели што равномерније могуће (ако је то паран број може се добити квадрат, а ако није, тада се добија правоугаоник код којег је једна страница за један дужа од друге). У имплементацији дужине нових страница можемо израчунати тако што дужу страницу \(b\) увећамо за \(\left\lfloor{\frac{c - (b - a)}{2}}\right\rfloor\) и за \(\left\lceil{\frac{c - (b - a)}{2}}\right\rceil = \left\lfloor{\frac{c - (b - a) + 1}{2}}\right\rfloor\).

#include <iostream>
#include <algorithm>

using namespace std;

long long maksimalniPrinos(long long a, long long b, long long c) {
  if (a > b) swap(a, b);
  if (c <= b - a)
    a += c;
  else {
    long long preostalo = c - (b - a);
    a = b + preostalo / 2;
    b = b + (preostalo + 1) / 2;
  }
  return a*b;
}

int main() {
  long long a, b, c;
  cin >> a >> b >> c;
  cout << maksimalniPrinos(a, b, c) << endl;
  return 0;
}