Шаг 8.
Алгоритмы.
Бинарный поиск. Решение задачи "Космическое поселение". Окончание

    На этом шаге рассмотрим программную реализацию поставленной задачи.

    Рассмотрим реализацию задачи средствами языка C++ в среде Qt Creator.

#include <QCoreApplication>
#include <bits/stdc++.h>
using namespace  std;

typedef long long  int64;

int64 getMax(int64 n, int64 a, int64 b, int64 w, int64 h) {
    int64 L = 0;
    int64 R = min(w, h) + 1;
    while (L + 1 < R) {
        int64 M = (L + R) / 2;
        int64 ad = a + 2 * M;
        int64 bd = b + 2 * M;
        int64 ac = w / ad;
        int64 bc = h / bd;
        if (ac * bc >= n) {
            L = M;
        } else {
            R = M;
        }
    }
    return L;
}
int main(int argc, char *argv[])
{
    QCoreApplication ap(argc, argv);

    freopen("space.in", "r", stdin);
    freopen("space.out", "w", stdout);

    int64 n, a, b, w, h;
    cin >> n >> a >> b >> w >> h;

    int64 p1 = getMax(n, a, b, w, h);
    int64 p2 = getMax(n, b, a, w, h);
    cout << max(p1, p2) << endl;

    return ap.exec();
}

    Архив с примером на языке С++ можно взять здесь.

    Архив с примером на языке Pascal можно взять здесь.

    На следующем шаге вспомним понятия массива и связанного списка.




Предыдущий шаг Содержание Следующий шаг