Хлебови - Решење

Поставка

Груба сила

Решење грубом силом подразумева да се испитају све могуће тројке бројева \((m, z, d)\) и да се изброје оне које задовољавају \(m+z+d = n\) и \(2m+z+\frac{d}{2} = n\). Набрајање тројки се може урадити угнежђеним петљама. Јасно је да број деце мора да буде паран. Из услова \(m+z+d\), пошто су сви бројеви ненегативни јасно је да мора да важи да су вредности свих променљивих одозго ограничене са \(n\).

Сложеност. Овај алгоритам је сложености \(O(n^3)\). Границе се могу поправити (на пример, мора да важи да је \(2d \leq n\), па је \(d \leq \frac{n}{2}\), даље, граница за број жена се може смањити ако је фиксиран број мушкараца и слично), но сложеност свих тих решења и даље остаје \(O(n^3)\).

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int broj_resenja = 0;
  for (int broj_muskaraca = 0; broj_muskaraca <= n; broj_muskaraca++)
    for (int broj_zena = 0; broj_zena <= n; broj_zena++)
      for (int broj_dece = 0; broj_dece <= n; broj_dece += 2)
        if (broj_muskaraca + broj_zena + broj_dece == n &&
            2*broj_muskaraca + broj_zena + broj_dece / 2 == n)
          broj_resenja++;
  cout << broj_resenja << endl;
  return 0;
}

Решавање система једначина за фиксирани број деце

Ако се фиксира један од бројева (мушкараца, жена или деце), добија се систем од две једначине са две непознате који се може егзактно решити. На пример, ако је број деце \(d\) фиксиран, тада добијамо систем \(m+z = n - d\), \(2m+z = n - \frac{d}{2}\), одакле је \(m=\frac{d}{2}\), а \(z=n-3\frac{d}{2}\). Ако су оба ова броја ненегативна, тада је тројка \((m, z, d)\) представља исправно решење. Можемо пребројати таква решења за све парне вредности \(d\) између \(0\) и \(n\).

Сложеност. Пошто се за \(n\) вредности деце број мушкараца и жена израчунава и проверава у константној сложености, овим добијамо алгоритам сложености \(O(n)\).

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int broj_resenja = 0;
  for (int broj_dece = 0; broj_dece <= n; broj_dece += 2) {
    int preostalo_ljudi = n - broj_dece;
    int preostalo_hleba = n - broj_dece / 2;
    // broj_muskaraca + broj_zena = preostalo_ljudi
    // 2*broj_muskaraca + broj_zena = preostalo_hleba
    int broj_muskaraca = preostalo_hleba - preostalo_ljudi;
    int broj_zena = preostalo_ljudi - broj_muskaraca;
    if (broj_muskaraca >= 0 && broj_zena >= 0)
      broj_resenja++;
  }
  cout << broj_resenja << endl;
  return 0;
}

Анализа општег решења система једначина

Да би бројеви \(m = \frac{d}{2}\) и \(z = n - 3\frac{d}{2}\), били ненегативни, за паран број \(0 \leq d \leq n\), потребно је и довољно је да је \(2n \geq 3d\). Ако је \(d=2k\), тада свака тројка \((k, n-3k, 2k)\), задовољава услове ако је \(0 \leq 6k \leq 2n\), тј. \(0 \leq 3k \leq n\). Дакле, скуп свих решења је скуп \(\{(k, n-3k, 2k)\ |\ 0 \leq k \leq \frac{n}{3}\}\), који има \(\left\lfloor{\frac{n}{3}}\right\rfloor + 1\) елемената.

Сложеност. Добијени алгоритам је сложености \(O(1)\).

#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  cout << n / 3 + 1 << endl;
  return 0;
}