näidislahendused

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

/* Ülesanne:
 * On antud kasvav funktsioon f (antud juhul f(x) = x ln (x))
 * ja reaalarv c.
 *
 * Lahenda võrrand f(x) = c. Leitud lahend tohib olla ülimalt
 * 10^{-6} võrra erinev tegelikust lahendist.
 */

double f (double x) {
  return x * log(x);
}

const double EPS = 1e-6;

// Lahendab võrrandi f(x) = c eeldusel, et lahend asub lõigus [lo, hi]
double solve (double lo, double hi, double c) {
  double mid = (lo + hi) / 2;
  if (hi - lo < EPS) {
    return mid;
  }

  if (f(mid) < c) {
    // siis teame, et lahend asub kuskil lõigus [mid, hi]
    return solve(mid, hi, c);
  } else {
    // teame, et lahend asub kuskil lõigus [lo, mid]
    return solve(lo, mid, c);
  }
}

double solve (double c) {
  return solve(1, 1e9, c);
}

int main () {
  double c;
  cin >> c;

  cout << fixed
       << setprecision(15)
       << solve(c) << endl;
}

/* ================================ */

#include <iostream>
#include <vector>

using namespace std;

/* Ülesanne:
 * Kostja kolib Itaaliasse ja pakib rutakalt asju kastidesse. Kuna tal on
 * sellega kiire ja ta on ka üksjagu laisk, siis võtab ta asju sellises järjekorras,
 * nagu kätte juhtub, ja asetab neid järjest kastidesse – kõigepealt ainult esimesse
 * kasti, seejärel ainult teise jne. Kirjuta programm, mis aitab Kostjal valida
 * väikseima võimaliku kasti suuruse, nii et kõik ta M asja mahuksid tema
 * pakkumismeetodi juures ära maksimaalselt N kasti.
 *
 * 1 <= N <= 1e5, 1 <= M <= 1e6, kõikide asjade suurused vahemikus 1...1000
 *
 * Näide:
 * N = 3, M = 6
 * asjad = [2, 16, 3, 7, 10, 12]
 *
 * Vastus:
 * 20 (esimesse kasti 1 ja 2; teise 3, 4, 5; kolmandasse 6. ese.
 */

// Kas n kasti, igaüks suurusega box_size, mahuvad kõik vektori arr elemendid
bool can_fit (int box_size, int n, const vector<int> &arr) {
  int boxes_left = n, current_remaining = box_size;
  for (int u : arr) {
    if (box_size < u) {
      return false;
    }

    if (current_remaining < u) {
      boxes_left--;
      if (boxes_left == 0) {
    return false;
      }
      current_remaining = box_size;
    }

    current_remaining -= u;
  }

  return true;
}

int solve (int lo, int hi, int n, const vector<int> &arr) {
  if (lo == hi) {
    return lo;
  }

  int mid = (lo + hi) / 2;
  if (!can_fit(mid, n, arr)) {
    return solve(mid + 1, hi, n, arr);
  } else {
    return solve(lo, mid, n, arr);
  }
}

int solve (int n, const vector<int> &arr) {
  return solve(1, 1e9, n, arr);
}

int main () {
  ios::sync_with_stdio(false);

  int n, m;
  cin >> n >> m;

  vector<int> arr (m);
  for (int i = 0; i < m; i++) {
    cin >> arr[i];
  }

  cout << solve(n, arr) << '\n';
}

/* ========================================= */

#include <iostream>
#include <cmath>

using namespace std;

/* Ülesanne:
 * On antud reaalmuutuja funktsioon f, mis on unimodaalne:
 * kuni mingi punktini kahanev ja sealt punktist edasi kasvav
 * Leia funktsiooni f haripunkt (x, kus f(x) on minimaalne).
 * Meie näites f(x) = x^4 - 2x^3 - x.
 *
 * Leitud lahend peab olema ülimalt 1e-6 kaugusel tegelikust lahendist.
 */

double f (double x) {
  return pow(x, 4) - 2 * pow(x, 3) - x;
}

const double EPS = 1e-6;

double solve (double lo, double hi) {
  if (hi - lo < EPS) {
    return (lo + hi) / 2;
  }

  double m1 = lo + (hi - lo) / 3;
  double m2 = hi - (hi - lo) / 3;

  if (f(m1) < f(m2)) {
    return solve(lo, m2);
  } else {
    return solve(m1, hi);
  }
}

double solve () {
  return solve(-2, 2);
}

int main () {
  cout << solve() << endl;
}